Changeset 1407:76349d8212d3 in lemon
- Timestamp:
- 10/07/17 03:18:49 (7 years ago)
- Branch:
- default
- Phase:
- public
- Location:
- lemon
- Files:
-
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bits/vf2_internals.h
r1405 r1407 27 27 ///\ingroup graph_isomorphism 28 28 ///The \ref Vf2 "VF2" algorithm is capable of finding different kind of 29 /// embeddings, this enum specifies its type.29 ///graph embeddings, this enum specifies their types. 30 30 /// 31 31 ///See \ref graph_isomorphism for a more detailed description. … … 36 36 INDUCED = 1, 37 37 /// Graph isomorphism 38 39 /// If the two graph hasthe same number of nodes, than it is38 /// 39 /// If the two graphs have the same number of nodes, than it is 40 40 /// equivalent to \ref INDUCED, and if they also have the same 41 41 /// number of edges, then it is also equivalent to \ref SUBGRAPH. 42 42 /// 43 /// However, using this setting is faster than the other two 44 /// options. 43 /// However, using this setting is faster than the other two options. 45 44 ISOMORPH = 2 46 45 }; -
lemon/vf2.h
r1405 r1407 54 54 }; 55 55 56 57 58 56 template <class G> 59 57 class DfsLeaveOrder : public DfsVisitor<G> { … … 94 92 ///There is also a \ref vf2() "function-type interface" called \ref vf2() 95 93 ///for the %VF2 algorithm, which is probably more convenient in most 96 ///use -cases.94 ///use cases. 97 95 /// 98 96 ///\tparam G1 The type of the graph to be embedded. … … 103 101 ///By default, it is G1::NodeMap<G2::Node> 104 102 ///\tparam NEQ A bool-valued binary functor determinining whether a node is 105 ///mappable to another. By default it is an alwaystrue operator.103 ///mappable to another. By default, it is an always-true operator. 106 104 /// 107 105 ///\sa vf2() … … 117 115 //Current depth in the DFS tree. 118 116 int _depth; 117 119 118 //Functor with bool operator()(G1::Node,G2::Node), which returns 1 120 //if ff the two nodes are equivalent.119 //if and only if the two nodes are equivalent 121 120 NEQ _nEq; 122 121 122 //_conn[v2] = number of covered neighbours of v2 123 123 typename G2::template NodeMap<int> _conn; 124 //Current mapping. We index it by the nodes of g1, and match[v] is 125 //a node of g2. 124 125 //The current mapping. _mapping[v1]=v2 iff v1 has been mapped to v2, 126 //where v1 is a node of G1 and v2 is a node of G2 126 127 M &_mapping; 127 //order[i] is the node of g1, for which we search a pair if depth=i 128 129 //order[i] is the node of g1 for which a pair is searched if depth=i 128 130 std::vector<typename G1::Node> order; 129 //currEdgeIts[i] is an edge iterator, witch is last used in the ith 130 //depth to find a pair for order[i]. 131 132 //currEdgeIts[i] is the last used edge iterator in the i-th 133 //depth to find a pair for node order[i] 131 134 std::vector<typename G2::IncEdgeIt> currEdgeIts; 132 //The small graph. 135 136 //The graph to be embedded 133 137 const G1 &_g1; 134 //The large graph. 138 139 //The graph into which g1 is to be embedded 135 140 const G2 &_g2; 141 136 142 //lookup tables for cutting the searchtree 137 143 typename G1::template NodeMap<int> rNew1t,rInOut1t; … … 243 249 bool extMatch() { 244 250 while(_depth>=0) { 245 //there are not nodes in g1, which has not pair in g2.246 251 if(_depth==static_cast<int>(order.size())) { 252 //all nodes of g1 are mapped to nodes of g2 247 253 --_depth; 248 254 return true; … … 251 257 const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth]; 252 258 typename G2::IncEdgeIt &edgeItOfDepth = currEdgeIts[_depth]; 253 //the node of g2 , whichneighbours are the candidates for259 //the node of g2 whose neighbours are the candidates for 254 260 //the pair of nodeOfDepth 255 261 typename G2::Node currPNode; 256 262 if(edgeItOfDepth==INVALID) { 257 263 typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth); 258 //if pairOfNodeOfDepth!=INVALID, we dont use 259 //fstMatchedE 260 if(pairOfNodeOfDepth==INVALID) 264 //if pairOfNodeOfDepth!=INVALID, we don't use fstMatchedE 265 if(pairOfNodeOfDepth==INVALID) { 261 266 for(; fstMatchedE!=INVALID && 262 267 _mapping[_g1.oppositeNode(nodeOfDepth, 263 268 fstMatchedE)]==INVALID; 264 269 ++fstMatchedE) ; //find fstMatchedE 270 } 265 271 if(fstMatchedE==INVALID||pairOfNodeOfDepth!=INVALID) { 266 //We found no covered neighbours, this means 267 //the graph is not connected (or _depth==0).Each268 //uncovered (and there are some other properties due272 //We found no covered neighbours, this means that 273 //the graph is not connected (or _depth==0). Each 274 //uncovered (and there are some other properties due 269 275 //to the spec. problem types) node of g2 is 270 //candidate. 276 //candidate. We can read the iterator of the last 271 277 //tried node from the match if it is not the first 272 //try (match[nodeOfDepth]!=INVALID)278 //try (match[nodeOfDepth]!=INVALID) 273 279 typename G2::NodeIt n2(_g2); 274 280 //if it's not the first try … … 318 324 } 319 325 320 //calc . the lookup table for cut the searchtree326 //calculate the lookup table for cutting the search tree 321 327 void setRNew1tRInOut1t() { 322 328 typename G1::template NodeMap<int> tmp(_g1,0); … … 352 358 _nEq(neq), _conn(g2,0), _mapping(m), order(countNodes(g1)), 353 359 currEdgeIts(countNodes(g1),INVALID), _g1(g1), _g2(g2), rNew1t(g1,0), 354 rInOut1t(g1,0), _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0) { 360 rInOut1t(g1,0), _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0) 361 { 355 362 _depth=0; 356 363 setOrder(); … … 441 448 442 449 /// Auxiliary class for the function-type interface of %VF2 algorithm. 443 450 /// 444 451 /// This auxiliary class implements the named parameters of 445 452 /// \ref vf2() "function-type interface" of \ref Vf2 algorithm. 446 453 /// 447 /// \warning This class should only be used through the function \ref vf2().454 /// \warning This class is not to be used directly. 448 455 /// 449 456 /// \tparam TR The traits class that defines various types used by the … … 466 473 public: 467 474 ///Constructor 468 Vf2Wizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) { 469 } 475 Vf2Wizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {} 470 476 471 477 ///Copy constructor 472 Vf2Wizard(const Base &b) : Base(b) { 478 Vf2Wizard(const Base &b) : Base(b) {} 473 479 474 480 ///Copy constructor -
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.