Polaris: SimBiGraphIterator.cc Source File

SimBiGraphIterator.cc Go to the documentation of this file. /// /// \file SimBiGraphIterator.cc /// /// #ifdef POLARIS_GNU_PRAGMAS #pragma implementation #endif /// #include "utilities/access_util.h" #include "SimBiGraphIterator.h" /// Create an empty iterator SimBiGraphIterator::SimBiGraphIterator( ) { #ifdef CLASS_INSTANCE_REGISTRY register_instance(SIM_BIGRAPH_ITERATOR, sizeof(SimBiGraphIterator), this); #endif _graph = NULL; _descr1_exists = NULL; _descr2_exists = NULL; _check_edge = NULL; _list1_valid = false; _list2_valid = false; _node1_pos = -1; _node2_pos = -1; } /// Reset the iteration void SimBiGraphIterator::reset( ) { /// ... For the descrs that exist, set all _check_edge entries true. for (int i=0; i < _graph->_nodes1; ++i) { if ( (*_descr1_exists)[i] ) { for (int j=0; j < _graph->_nodes2; ++j ) { if ( (*_descr2_exists)[j] ) { ((*_check_edge)[i])[j] = true; } } } } /// ... Search for the first valid pair of descriptors for (int i=0; i < _graph->_nodes1; ++i) { if ( (*_descr1_exists)[i] ) { for (int j=0; j < _graph->_nodes2; ++j ) { if ( (*_descr2_exists)[j] ) { _list1_valid = true; _list2_valid = true; _node1_pos = i; _node2_pos = j; return; } } } } _list1_valid = false; _list2_valid = false; _node1_pos = -1; _node2_pos = -1; return; } /// Make an iterator for an explicit graph SimBiGraphIterator::SimBiGraphIterator( SimBiGraph & graph ) : _graph( &graph ) { #ifdef CLASS_INSTANCE_REGISTRY register_instance(SIM_BIGRAPH_ITERATOR, sizeof(SimBiGraphIterator), this); #endif /// ... Mark that all nodes are valid to start with _descr1_exists = new Array< bool >; _descr1_exists->resize( _graph->_nodes1 ); for (int i=0; i < _graph->_nodes1; ++i) { (*_descr1_exists)[i] = true; } _descr2_exists = new Array< bool >; _descr2_exists->resize( _graph->_nodes2 ); for (int i=0; i < _graph->_nodes2; ++i) { (*_descr2_exists)[i] = true; } /// ... Initialize to check every edge _check_edge = new Array< Array< bool > >; _check_edge->resize( _graph->_nodes1 ); for (int i=0; i < _graph->_nodes1; ++i) { (*_check_edge)[i].resize(_graph->_nodes2); } reset( ); } /// Update the Similarity graph due to the change in a single node void SimBiGraphIterator::record_change( SimTypeOfChange change, SimEdge & edge ) { int index1; int index2; switch (change) { case SIM_COALESCE_NODE1: index1 = edge.index1(); for (int i=0; i<_graph->_nodes1; ++i) { ((*(_graph->_graph))[index1])[i].type( SIM_UNKNOWN ); ((*_check_edge)[index1])[i] = true; ((*(_graph->_graph))[i])[index1].type( SIM_UNKNOWN ); ((*_check_edge)[i])[index1] = true; } break; case SIM_COALESCE_NODE2: index2 = edge.index2(); for (int i=0; i<_graph->_nodes1; ++i) { ((*(_graph->_graph))[index2])[i].type( SIM_UNKNOWN ); ((*_check_edge)[index2])[i] = true; ((*(_graph->_graph))[i])[index2].type( SIM_UNKNOWN ); ((*_check_edge)[i])[index2] = true; } break; case SIM_CONTIG_NODE1: index1 = edge.index1(); index2 = edge.index2(); (*_descr2_exists)[index2] = false; /// ... delete node index2 for (int i=0; i<_graph->_nodes1; ++i) { SimEdgeKernel & kernel = ((*(_graph->_graph))[index1])[i]; kernel.type( contig_type( kernel.type( ) ) ); ((*_check_edge)[index1])[i] = true; SimEdgeKernel & kernel2 = ((*(_graph->_graph))[i])[index1]; kernel2.type( contig_type( kernel2.type( ) ) ); ((*_check_edge)[i])[index1] = true; } break; case SIM_CONTIG_NODE2: index1 = edge.index1(); index2 = edge.index2(); (*_descr1_exists)[index1] = false; /// ... delete node index1 for (int i=0; i<_graph->_nodes1; ++i) { SimEdgeKernel & kernel = ((*(_graph->_graph))[index2])[i]; kernel.type( contig_type( kernel.type( ) ) ); ((*_check_edge)[index2])[i] = true; SimEdgeKernel & kernel2 = ((*(_graph->_graph))[i])[index2]; kernel2.type( contig_type ( kernel2.type( ) ) ); ((*_check_edge)[i])[index2] = true; } break; case SIM_EQUIVALENCE: index2 = edge.index2(); (*_descr2_exists)[index2] = false; /// ... delete node index2 break; case SIM_NOCHANGE: break; default: break; } return; } SimBiGraphIterator::~SimBiGraphIterator( ) { #ifdef CLASS_INSTANCE_REGISTRY unregister_instance(SIM_BIGRAPH_ITERATOR, this); #endif if (_descr1_exists) { delete _descr1_exists; _descr1_exists = 0; } if (_descr2_exists) { delete _descr2_exists; _descr2_exists = 0; } if (_check_edge) { delete _check_edge; _check_edge = 0; } } int SimBiGraphIterator::current_list1( ) { return _node1_pos; } int SimBiGraphIterator::current_list2( ) { return _node2_pos; } SimEdge & SimBiGraphIterator::current( ) { p_assert( _list1_valid && _list2_valid, "SimBiGraphIterator not valid on call to current()"); SimEdgeKernel & kernel = ((*(_graph->_graph))[_node1_pos])[_node2_pos]; SimilarityType type = kernel.type(); if ((type == SIM_UNKNOWN) || (type == SIM_DIM_EQUIV_UP) || (type == SIM_STRIDE_EQUIV_UP)) { _graph->calc_similarity( _node1_pos, _node2_pos ); } SimEdge * edge = new SimEdge( _node1_pos, _node2_pos, &(*(*(_graph->_ptrs1))[_node1_pos]), &(*(*(_graph->_ptrs2))[_node2_pos]), &kernel); _created_edges.ins_last(edge); /// ... Mark that this edge has been checked ((*_check_edge)[_node1_pos])[_node2_pos] = false; return *edge; } bool SimBiGraphIterator::list1_valid( ) { return _list1_valid; } bool SimBiGraphIterator::list2_valid( ) { return _list2_valid; } void SimBiGraphIterator::next_list1_node( ) { int nodes1 = _graph->_nodes1; int nodes2 = _graph->_nodes2; /// ... Find the next edge to visit int start_i = _node1_pos+1; /// ... Reset list2 _node2_pos = 0; int start_j = _node2_pos; _list2_valid = false; for (int j=start_j; j < nodes2; ++j) { if ( (*_descr2_exists)[j]) { _list2_valid = true; _node2_pos = j; break; } } if (_list2_valid) { for (int i=start_i; i < nodes1; ++i) { if ( (*_descr1_exists)[i] && ((*_check_edge)[i])[start_j] ) { _list1_valid = true; _node1_pos = i; return; } } } _list1_valid = false; _node1_pos = 0; return; } void SimBiGraphIterator::next_list2_node( ) { int nodes2 = _graph->_nodes2; /// ... Find the next edge to visit int start_i = _node1_pos; int start_j = _node2_pos+1; for (int j=start_j; j < nodes2; ++j) { if ((*_descr2_exists)[j] && ((*_check_edge)[start_i])[j] ) { _list2_valid = true; _node2_pos = j; return; } } _list2_valid = false; _node2_pos = 0; return; } void SimBiGraphIterator::delete_node1( int node ) { (*_descr1_exists)[node] = false; } void SimBiGraphIterator::delete_node2( int node ) { (*_descr2_exists)[node] = false; } void SimBiGraphIterator::print(ostream & o) const { o << "{ "; if (_list1_valid) { o << "LIST1 VALID;"; } if (_list2_valid) { o << "LIST2 VALID;"; } if (!_list1_valid && !_list2_valid) { o << "NOT VALID;"; } o << "(" << _node1_pos << "," << _node2_pos << ") }"; } SimBiGraphIterator * SimBiGraphIterator::clone() const { return new SimBiGraphIterator( (SimBiGraphIterator &) *this ); } Listable * SimBiGraphIterator::listable_clone() const { return (Listable *) clone(); } ostream & operator << (ostream & o, const SimBiGraphIterator & iter) { iter.print(o); return o; }

© 1995-2005 University of Illinois, Urbana-Champaign. All rights reserved.  Fri Mar 25 23:06:07 2005