Changeset 1407:76349d8212d3 in lemon for lemon/vf2pp.h
- Timestamp:
- 10/07/17 03:18:49 (7 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/vf2pp.h
r1405 r1407 76 76 ///There is also a \ref vf2pp() "function-type interface" called 77 77 ///\ref vf2pp() for the %VF2 Plus Plus algorithm, which is probably 78 ///more convenient in most use -cases.78 ///more convenient in most use cases. 79 79 /// 80 80 ///\tparam G1 The type of the graph to be embedded. … … 97 97 template<class G1=ListDigraph, 98 98 class G2=ListDigraph, 99 class M = typename G1::template NodeMap<G2::Node>,//the mapping 100 //labels of G1,the labels are the numbers {0,1,2,..,K-1}, 101 //where K is the number of different labels 99 class M = typename G1::template NodeMap<G2::Node>, 102 100 class M1 = typename G1::template NodeMap<int>, 103 //labels of G2, ...104 101 class M2 = typename G2::template NodeMap<int> > 105 102 #endif … … 115 112 M &_mapping; 116 113 117 //order[i] is a node of g1 ,for which a pair is searched if depth=i114 //order[i] is a node of g1 for which a pair is searched if depth=i 118 115 std::vector<typename G1::Node> order; 119 116 120 //currEdgeIts[i] is the last used edge iterator in the i th117 //currEdgeIts[i] is the last used edge iterator in the i-th 121 118 //depth to find a pair for node order[i] 122 119 std::vector<typename G2::IncEdgeIt> currEdgeIts; 123 124 //The small graph.120 121 //The graph to be embedded 125 122 const G1 &_g1; 126 123 127 //The large graph.124 //The graph into which g1 is to be embedded 128 125 const G2 &_g2; 129 126 … … 138 135 rInOutLabels1; 139 136 140 //_intLabels1[v]==i means that vertex v has the i label in141 // _g1(i is in {0,1,2,..,K-1}, where K is the number of diff. labels)137 //_intLabels1[v]==i means that node v has label i in _g1 138 //(i is in {0,1,2,..,K-1}, where K is the number of diff. labels) 142 139 M1 &_intLabels1; 143 140 144 //_intLabels2[v]==i means that vertex v has the i label in145 // _g2(i is in {0,1,2,..,K-1}, where K is the number of diff. labels)141 //_intLabels2[v]==i means that node v has label i in _g2 142 //(i is in {0,1,2,..,K-1}, where K is the number of diff. labels) 146 143 M2 &_intLabels2; 147 144 … … 150 147 151 148 //lookup tables for manipulating with label class cardinalities 152 // after use they have to be reset to 0..0149 //(after use they have to be reset to 0..0) 153 150 std::vector<int> labelTmp1,labelTmp2; 154 151 155 152 MappingType _mapping_type; 156 153 157 //indicates whether the mapping or the labels must be deleted in the ctor154 //indicates whether the mapping or the labels must be deleted in the destructor 158 155 bool _deallocMappingAfterUse,_deallocLabelsAfterUse; 159 156 … … 287 284 } 288 285 289 290 //matches n1 and n2 286 //maps n1 to n2 291 287 void addPair(const typename G1::Node n1,const typename G2::Node n2) { 292 288 _conn[n2]=-1; … … 299 295 } 300 296 301 302 //dematches n1 and n2 297 //removes mapping of n1 to n2 303 298 void subPair(const typename G1::Node n1,const typename G2::Node n2) { 304 299 _conn[n2]=0; … … 312 307 } 313 308 } 314 315 309 316 310 void processBFSLevel(typename G1::Node source,unsigned int& orderIndex, … … 365 359 ++labelTmp1[_intLabels2[n2]]; 366 360 367 // OutDegMap<G1> dm1(_g1);368 361 typename G1::template NodeMap<int> dm1(_g1,0); 369 362 for(typename G1::EdgeIt e(_g1); e!=INVALID; ++e) { … … 398 391 bool extMatch(){ 399 392 while(_depth>=0) { 400 //there is no node in g1, which has not pair in g2.401 393 if(_depth==static_cast<int>(order.size())) { 394 //all nodes of g1 are mapped to nodes of g2 402 395 --_depth; 403 396 return true; … … 406 399 const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth]; 407 400 typename G2::IncEdgeIt &edgeItOfDepth = currEdgeIts[_depth]; 408 //the node of g2 , whichneighbours are the candidates for401 //the node of g2 whose neighbours are the candidates for 409 402 //the pair of order[_depth] 410 403 typename G2::Node currPNode; 411 404 if(edgeItOfDepth==INVALID){ 412 405 typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth); 413 //if _mapping[order[_depth]]!=INVALID, we dont need 414 //fstMatchedE 415 if(pairOfNodeOfDepth==INVALID) 406 //if _mapping[order[_depth]]!=INVALID, we don't need fstMatchedE 407 if(pairOfNodeOfDepth==INVALID) { 416 408 for(; fstMatchedE!=INVALID && 417 409 _mapping[_g1.oppositeNode(nodeOfDepth, 418 410 fstMatchedE)]==INVALID; 419 411 ++fstMatchedE); //find fstMatchedE, it could be preprocessed 412 } 420 413 if(fstMatchedE==INVALID||pairOfNodeOfDepth!=INVALID) { 421 //We found no covered neighbours, this means 422 //the graph is not connected (or _depth==0).Each423 //uncovered (and there are some other properties due414 //We found no covered neighbours, this means that 415 //the graph is not connected (or _depth==0). Each 416 //uncovered (and there are some other properties due 424 417 //to the spec. problem types) node of g2 is 425 //candidate. 418 //candidate. We can read the iterator of the last 426 419 //tried node from the match if it is not the first 427 //try (match[nodeOfDepth]!=INVALID)420 //try (match[nodeOfDepth]!=INVALID) 428 421 typename G2::NodeIt n2(_g2); 429 422 //if it's not the first try … … 448 441 continue; 449 442 } 450 else {443 else { 451 444 currPNode=_mapping[_g1.oppositeNode(nodeOfDepth, 452 445 fstMatchedE)]; … … 454 447 } 455 448 } 456 else {449 else { 457 450 currPNode=_g2.oppositeNode(pairOfNodeOfDepth, 458 451 edgeItOfDepth); … … 473 466 } 474 467 475 //calc . the lookup table for cutting the searchtree468 //calculate the lookup table for cutting the search tree 476 469 void setRNew1tRInOut1t(){ 477 470 typename G1::template NodeMap<int> tmp(_g1,0); … … 676 669 public: 677 670 ///Constructor 678 Vf2ppWizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) { 671 Vf2ppWizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {} 679 672 680 673 ///Copy constructor … … 685 678 struct SetMappingBase : public Base { 686 679 typedef T Mapping; 687 SetMappingBase(const Base &b) : Base(b) { 680 SetMappingBase(const Base &b) : Base(b) {} 688 681 }; 689 682 … … 714 707 /// 715 708 ///\param nodeLabels1 A \ref concepts::ReadMap "readable node map" 716 ///of g1 with integer value . In case of K different labels, the labels717 ///must be the {0,1,..,K-1} numbers.709 ///of g1 with integer values. In case of K different labels, the labels 710 ///must be the numbers {0,1,..,K-1}. 718 711 ///\param nodeLabels2 A \ref concepts::ReadMap "readable node map" 719 ///of g2 with integer value . In case of K different labels, the labels720 ///must be the {0,1,..,K-1} numbers.712 ///of g2 with integer values. In case of K different labels, the labels 713 ///must be the numbers {0,1,..,K-1}. 721 714 template<typename NL1, typename NL2> 722 715 Vf2ppWizard< SetNodeLabelsBase<NL1,NL2> > … … 878 871 /// 879 872 /// // Iterate through all the induced subgraph mappings 880 /// // of graph g1 into g2 using the labels c1 and c2873 /// // of graph g1 into g2 using the labels c1 and c2 881 874 /// auto* myVf2pp = vf2pp(g1,g2).mapping(m).nodeLabels(c1,c2) 882 875 /// .induced().getPtrToVf2Object();
Note: See TracChangeset
for help on using the changeset viewer.