Polaris: SimGraphIterator.cc Source File

SimGraphIterator.cc Go to the documentation of this file. /// /// \file SimGraphIterator.cc /// /// #ifdef POLARIS_GNU_PRAGMAS #pragma implementation #endif /// #include "SimGraphIterator.h" /// Create an empty iterator SimGraphIterator::SimGraphIterator( ) { #ifdef CLASS_INSTANCE_REGISTRY register_instance(SIM_GRAPH_ITERATOR, sizeof(SimGraphIterator), this); #endif _graph = NULL; _check_edge = NULL; _valid = false; _node1_pos = -1; _node2_pos = -1; } /// Reset the iterator position void SimGraphIterator::reset( ) { /// ... For all descrs which exist, set _check_edge to be true for (int i=0; i < _graph->_nodes; ++i) { if ( (*(_graph->_descr_exists))[i] ) { for (int j=i+1; j < _graph->_nodes; ++j ) { if ( (*(_graph->_descr_exists))[j] ) { ((*_check_edge)[i])[j] = true; } } } } /// ... Search for the first valid pair of descriptors for (int i=0; i < _graph->_nodes; ++i) { if ( (*(_graph->_descr_exists))[i] ) { for (int j=i+1; j < _graph->_nodes; ++j ) { if ( (*(_graph->_descr_exists))[j] ) { _valid = true; _node1_pos = i; _node2_pos = j; return; } } } } _valid = false; _node1_pos = -1; _node2_pos = -1; return; } /// Make an iterator for an explicit graph SimGraphIterator::SimGraphIterator( SimGraph & graph ) : _graph( &graph ) { #ifdef CLASS_INSTANCE_REGISTRY register_instance(SIM_GRAPH_ITERATOR, sizeof(SimGraphIterator), this); #endif /// ... Initialize to check every edge _check_edge = new Array< Array< bool > >; _check_edge->resize( _graph->_nodes ); for (int i=0; i < _graph->_nodes; ++i) { (*_check_edge)[i].resize(_graph->_nodes); } reset( ); } /// Update the Similarity graph due to the change in a single node void SimGraphIterator::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->_nodes; ++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->_nodes; ++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: /// ... Found contiguous, keeping node 1 index1 = edge.index1(); index2 = edge.index2(); (*(_graph->_descr_exists))[index2] = false; /// ... delete node index2 for (int i=0; i<_graph->_nodes; ++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: /// ... Found contiguous, keeping node 2 index1 = edge.index1(); index2 = edge.index2(); (*(_graph->_descr_exists))[index1] = false; /// ... delete node index1 for (int i=0; i<_graph->_nodes; ++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_SUBREG_NODE1: /// ... node 2 is a subregion of node 1 (keep node 1) index2 = edge.index2(); (*(_graph->_descr_exists))[index2] = false; /// ... delete node index2 break; case SIM_SUBREG_NODE2: /// ... node 1 is a subregion of node 2 (keep node 2) index1 = edge.index1(); (*(_graph->_descr_exists))[index1] = false; /// ... delete node index1 break; case SIM_EQUIVALENCE: index2 = edge.index2(); (*(_graph->_descr_exists))[index2] = false; /// ... delete node index2 break; case SIM_NOCHANGE: break; } return; } SimGraphIterator::~SimGraphIterator( ) { #ifdef CLASS_INSTANCE_REGISTRY unregister_instance(SIM_GRAPH_ITERATOR, this); #endif if (_check_edge) delete _check_edge; } SimEdge & SimGraphIterator::current( ) { p_assert( _valid, "SimGraphIterator 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->_ptrs))[_node1_pos]), &(*(*(_graph->_ptrs))[_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 SimGraphIterator::valid( ) { return _valid; } void SimGraphIterator::operator ++( ) { int nodes = _graph->_nodes; /// ... Find the next edge to visit int start_i = _node1_pos; int start_j = _node2_pos+1; /// ... Make a private class for checking termination of the loop class Termination { private: int _limit; int _count; public: Termination(int nodes) { _count = 0; _limit = nodes*nodes;} /// ... At most nodes^2 iters of inner loop ~Termination(){} bool notdone() { ++_count; return (_count >= _limit) ? false : true; } bool done() { return (_count >= _limit) ? true : false; } }; Termination t(nodes); while (1) { for (int i=start_i; i < nodes; ++i,start_j=i+1) { if ( (*(_graph->_descr_exists))[i] ) { for (int j=start_j; t.notdone() && j < nodes; ++j) { if ((*(_graph->_descr_exists))[j] && ((*_check_edge)[i])[j] ) { _valid = true; _node1_pos = i; _node2_pos = j; return; } } /// ... See if we've gone totally around without finding an edge to visit if (t.done()) { _valid = false; _node1_pos = -1; _node2_pos = -1; return; } } } start_i = 0; start_j = 1; } /// Can never reach this point _valid = false; _node1_pos = -1; _node2_pos = -1; return; } /// Same as operator++ void SimGraphIterator::next( ) { ++(*this); } bool SimGraphIterator::end( ) const { return !_valid; } /// Mark all edges from this node as SIM_UNKNOWN void SimGraphIterator::mark_unknown( AbstractAccess & node ) { int node_index = -1; for (int i=0; i < _graph->_nodes; ++i) { if (((*(_graph->_ptrs))[i]).operator -> () == &node) { node_index = i; break; } } p_assert(node_index != -1,"Node not found in Similarity graph"); for (int i=0; i<_graph->_nodes; ++i) { SimEdgeKernel & kernel = ((*(_graph->_graph))[node_index])[i]; kernel.type( SIM_UNKNOWN ); ((*_check_edge)[node_index])[i] = true; SimEdgeKernel & kernel2 = ((*(_graph->_graph))[i])[node_index]; kernel2.type( SIM_UNKNOWN ); ((*_check_edge)[i])[node_index] = true; } } /// Delete the given node from the graph void SimGraphIterator::delete_node( AbstractAccess & node ) { for (int i=0; i < _graph->_nodes; ++i) { if (((*(_graph->_ptrs))[i]).operator -> () == &node) { (*(_graph->_descr_exists))[i] = false; break; } } } void SimGraphIterator::delete_node( int node ) { (*(_graph->_descr_exists))[node] = false; } void SimGraphIterator::print(ostream & o) const { o << "{ "; if (_valid) { o << "VALID;"; } else { o << "NOT VALID;"; } o << "(" << _node1_pos << "," << _node2_pos << ") }"; } SimGraphIterator * SimGraphIterator::clone() const { return new SimGraphIterator( (SimGraphIterator &) *this ); } Listable * SimGraphIterator::listable_clone() const { return (Listable *) clone(); } ostream & operator << (ostream & o, const SimGraphIterator & iter) { iter.print(o); return o; }

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