Polaris: SimBiGraph.cc Source File

SimBiGraph.cc Go to the documentation of this file. /// /// \file SimGraph.cc /// #ifdef POLARIS_GNU_PRAGMAS #pragma implementation #endif /// #include "SimBiGraph.h" #include "UEdge.h" #include "utilities/access_util.h" #include "utilities/stmt_util.h" #include "Range/Relation.h" #include "Range/RangeAccessor.h" #include "UBiGraphIterator.h" /// Create an empty graph SimBiGraph::SimBiGraph( ) { #ifdef CLASS_INSTANCE_REGISTRY register_instance(SIM_BIGRAPH, sizeof(SimBiGraph), this); #endif _ptrs1 = new Array< RefElement< AbstractAccess > >; _ptrs2 = new Array< RefElement< AbstractAccess > >; _graph = new Array<Array<SimEdgeKernel> >; _nodes1 = 0; _nodes2 = 0; } /// Create a complete graph with given number of nodes SimBiGraph::SimBiGraph(List<AbstractAccess> & list1, List<AbstractAccess> & list2) { #ifdef CLASS_INSTANCE_REGISTRY register_instance(SIM_BIGRAPH, sizeof(SimBiGraph), this); #endif /// ... Make a complete graph with the proper number of nodes _nodes1 = list1.entries(); _nodes2 = list2.entries(); _ptrs1 = 0; _ptrs2 = 0; _graph = 0; if ((_nodes1 == 0) || (_nodes2 == 0)) return; _ptrs1 = new Array< RefElement< AbstractAccess > >; _ptrs2 = new Array< RefElement< AbstractAccess > >; _graph = new Array<Array<SimEdgeKernel> >; _ptrs1->resize(_nodes1); _graph->resize(_nodes1); _ptrs2->resize(_nodes2); Iterator<AbstractAccess> iter = list1; for (int i = 0; iter.valid(); ++iter,++i) { (*_ptrs1)[i] = iter.current(); (*_graph)[i].resize(_nodes2); } Iterator<AbstractAccess> iter2 = list2; for (int i = 0; iter2.valid(); ++iter2,++i) { (*_ptrs2)[i] = iter2.current(); } /// ... Initialized each edge to SIM_UNKNOWN for (int i=0; i<_nodes1; ++i) { for (int j=0; j<_nodes2; ++j) { (((*_graph)[i])[j]).type(SIM_UNKNOWN); } } Statement * r_stmt = range_stmt(*(list1[0]._summarized_to)); String stmt_tag = r_stmt->tag(); _range_acc = new RangeAccessor(list1[0]._pgm_summarized_to->range_dict_guarded(), *r_stmt ); /// ... Compare each pair of descriptors, building the Similarity graph as we go for (int i=0; i<_nodes1; ++i) { for (int j=0; j<_nodes2; ++j) { calc_similarity( i, j ); } } } void SimBiGraph::print_similarities( ) const { if (_ar_logging && _ar_logging % 5 == 0) { arlog << "BI-Graph" << endl; for (int i=0; i<_nodes1; ++i) { arlog << "[" << i << "]" ; AbstractAccess & aa = *((*_ptrs1)[i]); int ndims1 = aa.number_of_dimensions(); for (int j=0; j<_nodes2; ++j) { AbstractAccess & aa2 = *((*_ptrs2)[j]); SimEdgeKernel & sek = ((*_graph)[i])[j]; int ndims2 = aa2.number_of_dimensions(); arlog << " " << sek.type_name() << "[" ; if ((i != j) && (ndims1 == ndims2) && (sek.type() != SIM_NOT_SIMILAR)) { for (int k=0; k<aa.number_of_dimensions(); ++k) { arlog << (*(sek.stridematch()))[k] << ":" ; if ((*(sek.spanmatch()))[k]) { arlog << "T"; } else { arlog << "F"; } } } arlog << "]"; } arlog << endl; } } } /// Create a copy of a given graph SimBiGraph::SimBiGraph( const SimBiGraph & other ) { #ifdef CLASS_INSTANCE_REGISTRY register_instance(SIM_BIGRAPH, sizeof(SimBiGraph), this); #endif _nodes1 = other._nodes1; _nodes2 = other._nodes2; _ptrs1 = new Array< RefElement< AbstractAccess > >; _ptrs2 = new Array< RefElement< AbstractAccess > >; _graph = new Array< Array< SimEdgeKernel > >; _ptrs1->resize(_nodes1); _ptrs2->resize(_nodes2); _graph->resize(_nodes1); for (int i = 0; i<_nodes1; ++i) { (*_ptrs1)[i] = (*(other._ptrs1))[i]; (*_graph)[i].resize(_nodes2); } for (int i = 0; i<_nodes2; ++i) { (*_ptrs2)[i] = (*(other._ptrs2))[i]; } for (int i=0; i < _nodes1; ++i) { for (int j=0; j < _nodes2; ++j) { ((*_graph)[i])[j] = ((*(other._graph))[i])[j]; } } } /// Return the number of nodes in the graph for list1 int SimBiGraph::nodes1( ) { return _nodes1; } /// Return the number of nodes in the graph for list2 int SimBiGraph::nodes2( ) { return _nodes2; } SimBiGraph::~SimBiGraph( ) { #ifdef CLASS_INSTANCE_REGISTRY unregister_instance(SIM_BIGRAPH, this); #endif if (_ptrs1) { delete _ptrs1; _ptrs1 = 0; } if (_ptrs2) { delete _ptrs2; _ptrs2 = 0; } if (_graph) { delete _graph; _graph = 0; } if (_range_acc) { delete _range_acc; _range_acc = 0; } } /// Calculate the similarity relationship between nodes i and j in the Similarity graph void SimBiGraph::calc_similarity( int i, int j ) { AbstractAccess & descr1 = *((*_ptrs1)[ i ]); int ndims1 = descr1.number_of_dimensions(); AbstractAccess & descr2 = *((*_ptrs2)[ j ]); int ndims2 = descr2.number_of_dimensions(); SimEdgeKernel & kernelij = ((*_graph)[i])[j]; SimilarityType orig_ij_type = kernelij.type(); SimilarityType calc_ij_type; /// ... If already filled in, skip it if ((orig_ij_type != SIM_UNKNOWN ) && (orig_ij_type != SIM_DIM_EQUIV_UP ) && (orig_ij_type != SIM_STRIDE_EQUIV_UP )) return; bool equal_dim_count; if (ndims1 == ndims2) { equal_dim_count = true; } else { equal_dim_count = false; } bool matchoff = false; bool matchstrides, matchspans; Array<int> * stride_match1; Array<int> * stride_match2=0; Array<bool> * span_match1; Array<bool> * span_match2=0; /// ... Do the offsets match? if (is_integer_zero(descr1.start_guarded()) && is_integer_zero(descr2.start_guarded())) { matchoff = true; } else { const Relation & reloff = _range_acc->compare(descr1.start_guarded(), descr2.start_guarded()); if (reloff.is_equal()) { matchoff = true; } } /// ... If these two descriptors were already found dimension-equivalent, /// ... check offsets to see whether they are totally equivalent. Then we /// ... can avoid all the rest of the equivalency checks. if (orig_ij_type == SIM_DIM_EQUIV_UP) { if (matchoff) { calc_ij_type = SIM_EQUIV; } else { calc_ij_type = SIM_DIM_EQUIV; } kernelij.type(calc_ij_type); stride_match1 = kernelij.stridematch(); span_match1 = kernelij.spanmatch(); } else { /// ... Compare one dimension from each descriptor stride_match1 = new Array<int>; stride_match1->resize(ndims1); stride_match2 = new Array<int>; stride_match2->resize(ndims2); span_match1 = new Array<bool>; span_match1->resize(ndims1); span_match2 = new Array<bool>; span_match2->resize(ndims2); if (orig_ij_type == SIM_STRIDE_EQUIV_UP) { /// ... Check only for a span match based on the previous stride match Array<int> * temp1 = kernelij.stridematch(); for (int ii=0; ii<ndims1; ++ii) { (*stride_match1)[ii] = (*temp1)[ii]; } } else { calc_stride_span_match(descr1, descr2, *_range_acc, *stride_match1, *stride_match2, *span_match1, *span_match2); } /// ... Now, check for a match. if (orig_ij_type == SIM_STRIDE_EQUIV_UP) { matchstrides = true; /// ... Already asserted that strides are equiv } else { matchstrides = true; /// ... Check whether all dimensions of at least one descriptor /// ... have a matching dimension. int count1 = 0; for (int ii=0; ii<ndims1; ++ii) { if ((*stride_match1)[ii] != -1) { count1++; } } int count2 = 0; for (int ii=0; ii<ndims2; ++ii) { if ((*stride_match2)[ii] != -1) { count2++; } } p_assert(count1 == count2, "Stride-match is not reflexive"); if ((count1 != ndims1) && (count2 != ndims2)) { matchstrides = false; } } matchspans = true; for (int ii=0; ii<ndims1; ++ii) { if (((*stride_match1)[ii] != -1) && (! (*span_match1)[ii])) { matchspans = false; break; } } if (matchoff && matchstrides && matchspans && equal_dim_count) { calc_ij_type = SIM_EQUIV; } else if (matchoff && matchstrides && matchspans) { calc_ij_type = SIM_EQUIV_SEMI; } else if (matchstrides && matchspans && equal_dim_count) { calc_ij_type = SIM_DIM_EQUIV; } else if (matchstrides && matchspans) { calc_ij_type = SIM_DIM_EQUIV_SEMI; } else if (matchstrides && equal_dim_count) { calc_ij_type = SIM_STRIDE_EQUIV; } else if (matchstrides) { calc_ij_type = SIM_STRIDE_EQUIV_SEMI; } else { calc_ij_type = SIM_NOT_SIMILAR; } kernelij.dump_in_match( calc_ij_type, stride_match1, span_match1 ); } /// ... silvius: if (span_match2){ delete span_match2; } if (stride_match2){ delete stride_match2; } } RangeAccessor * SimBiGraph::range_acc( ) { return _range_acc; } SimBiGraph * SimBiGraph::clone() const { return new SimBiGraph( (SimBiGraph &)*this ); } Listable * SimBiGraph::listable_clone() const { return (Listable *) clone(); } void SimBiGraph::print(ostream & o) const { o << "{ Nodes: (" << _nodes1 << "," << _nodes2 << ")" << "; Ptrs: " << *_ptrs1 << "; Graph: " << *_graph << "}"; } ostream & operator << (ostream & o, const SimBiGraph & graph) { graph.print(o); return o; } SimEdgeKernel & SimBiGraph::kernel(int i, int j) { return ((*_graph)[i])[j]; }

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