Changeset 1351:2f479109a71d in lemon for lemon/vf2.h
 Timestamp:
 05/14/15 16:07:38 (9 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/vf2.h
r1350 r1351 19 19 #define LEMON_VF2_H 20 20 21 ///\ingroup graph_properties 22 ///\file 23 ///\brief VF2 algorithm \cite cordella2004sub. 24 21 25 #include <lemon/core.h> 22 26 #include <lemon/concepts/graph.h> … … 91 95 } 92 96 93 enum MappingType { 97 ///Graph mapping types. 98 99 ///\ingroup graph_isomorphism 100 ///The \ref Vf2 "VF2" algorithm is capable of finding different kind of 101 ///embeddings, this enum specifies its type. 102 /// 103 ///See \ref graph_isomorphism for a more detailed description. 104 enum Vf2MappingType { 105 /// Subgraph isomorphism 94 106 SUBGRAPH = 0, 107 /// Induced subgraph isomorphism 95 108 INDUCED = 1, 109 /// Graph isomorphism 110 111 /// If the two graph has the same number of nodes, than it is 112 /// equivalent to \ref INDUCED, and if they also have the same 113 /// number of edges, then it is also equivalent to \ref SUBGRAPH. 114 /// 115 /// However, using this setting is faster than the other two 116 /// options. 96 117 ISOMORPH = 2 97 118 }; 98 119 99 template<class G1, class G2, class I, class NEq = bits::vf2::AlwaysEq > 120 ///%VF2 algorithm class. 121 122 ///\ingroup graph_isomorphism This class provides an efficient 123 ///implementation of the %VF2 algorithm \cite cordella2004sub 124 ///for variants of the (Sub)graph Isomorphism problem. 125 /// 126 ///There is also a \ref vf2() "functiontype interface" called \ref vf2() 127 ///for the %VF2 algorithm, which is probably more convenient in most 128 ///usecases. 129 /// 130 ///\tparam G1 The type of the graph to be embedded. 131 ///The default type is \ref ListDigraph. 132 ///\tparam G2 The type of the graph g1 will be embedded into. 133 ///The default type is \ref ListDigraph. 134 ///\tparam M The type of the NodeMap storing the mapping. 135 ///By default, it is G1::NodeMap<G2::Node> 136 ///\tparam NEQ A boolvalued binary functor determinining whether a node is 137 ///mappable to another. By default it is an always true operator. 138 /// 139 ///\sa vf2() 140 #ifdef DOXYGEN 141 template<class G1, class G2, class M, class NEQ > 142 #else 143 template<class G1=ListDigraph, 144 class G2=ListDigraph, 145 class M = typename G1::template NodeMap<G2::Node>, 146 class NEQ = bits::vf2::AlwaysEq > 147 #endif 100 148 class Vf2 101 149 { … … 104 152 //Functor with bool operator()(G1::Node,G2::Node), which returns 1 105 153 //if and only if the 2 nodes are equivalent. 106 NE q_nEq;154 NEQ _nEq; 107 155 108 156 typename G2::template NodeMap<int> _conn; 109 //Current ma tching. We index it by the nodes of g1, and match[v] is157 //Current mapping. We index it by the nodes of g1, and match[v] is 110 158 //a node of g2. 111 I &_match;159 M &_mapping; 112 160 //order[i] is the node of g1, for which we find a pair if depth=i 113 161 std::vector<typename G1::Node> order; … … 122 170 typename G1::template NodeMap<int> rNew1t,rInOut1t; 123 171 124 MappingType _mapping_type;172 Vf2MappingType _mapping_type; 125 173 126 174 //cut the search tree 127 template< MappingType MT>175 template<Vf2MappingType MT> 128 176 bool cut(const typename G1::Node n1,const typename G2::Node n2) const 129 177 { … … 150 198 } 151 199 152 template< MappingType MT>200 template<Vf2MappingType MT> 153 201 bool feas(const typename G1::Node n1,const typename G2::Node n2) 154 202 { … … 159 207 { 160 208 const typename G1::Node currNode=_g1.oppositeNode(n1,e1); 161 if(_ma tch[currNode]!=INVALID)162 _conn[_ma tch[currNode]];209 if(_mapping[currNode]!=INVALID) 210 _conn[_mapping[currNode]]; 163 211 } 164 212 bool isIso=1; … … 178 226 { 179 227 const typename G1::Node currNode=_g1.oppositeNode(n1,e1); 180 if(_ma tch[currNode]!=INVALID&&_conn[_match[currNode]]!=1)228 if(_mapping[currNode]!=INVALID&&_conn[_mapping[currNode]]!=1) 181 229 { 182 230 switch(MT) … … 187 235 break; 188 236 case SUBGRAPH: 189 if(_conn[_ma tch[currNode]]<1)237 if(_conn[_mapping[currNode]]<1) 190 238 isIso=0; 191 239 break; 192 240 } 193 _conn[_ma tch[currNode]]=1;241 _conn[_mapping[currNode]]=1; 194 242 } 195 243 } … … 200 248 { 201 249 _conn[n2]=1; 202 _ma tch.set(n1,n2);250 _mapping.set(n1,n2); 203 251 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) 204 252 if(_conn[_g2.oppositeNode(n2,e2)]!=1) … … 209 257 { 210 258 _conn[n2]=0; 211 _ma tch.set(n1,INVALID);259 _mapping.set(n1,INVALID); 212 260 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) 213 261 { … … 232 280 } 233 281 234 public: 235 236 template<MappingType MT> 282 template<Vf2MappingType MT> 237 283 bool extMatch() 238 284 { … … 251 297 { 252 298 typename G1::IncEdgeIt fstMatchedE(_g1,order[_depth]); 253 //if _ma tch[order[_depth]]!=INVALID, we dont use299 //if _mapping[order[_depth]]!=INVALID, we dont use 254 300 //fstMatchedE 255 if(_ma tch[order[_depth]]==INVALID)301 if(_mapping[order[_depth]]==INVALID) 256 302 for(; fstMatchedE!=INVALID && 257 _ma tch[_g1.oppositeNode(order[_depth],303 _mapping[_g1.oppositeNode(order[_depth], 258 304 fstMatchedE)]==INVALID; 259 305 ++fstMatchedE) ; //find fstMatchedE 260 if(fstMatchedE==INVALID_ma tch[order[_depth]]!=INVALID)306 if(fstMatchedE==INVALID_mapping[order[_depth]]!=INVALID) 261 307 { 262 308 //We did not find an covered neighbour, this means … … 269 315 typename G2::NodeIt n2(_g2); 270 316 //if its not the first try 271 if(_ma tch[order[_depth]]!=INVALID)317 if(_mapping[order[_depth]]!=INVALID) 272 318 { 273 n2=++typename G2::NodeIt(_g2,_ma tch[order[_depth]]);274 subPair(order[_depth],_ma tch[order[_depth]]);319 n2=++typename G2::NodeIt(_g2,_mapping[order[_depth]]); 320 subPair(order[_depth],_mapping[order[_depth]]); 275 321 } 276 322 for(; n2!=INVALID; ++n2) … … 295 341 else 296 342 { 297 currPNode=_match[_g1.oppositeNode(order[_depth],fstMatchedE)]; 343 currPNode=_mapping[_g1.oppositeNode(order[_depth], 344 fstMatchedE)]; 298 345 currEdgeIts[_depth]=typename G2::IncEdgeIt(_g2,currPNode); 299 346 } … … 301 348 else 302 349 { 303 currPNode=_g2.oppositeNode(_ma tch[order[_depth]],350 currPNode=_g2.oppositeNode(_mapping[order[_depth]], 304 351 currEdgeIts[_depth]); 305 subPair(order[_depth],_ma tch[order[_depth]]);352 subPair(order[_depth],_mapping[order[_depth]]); 306 353 ++currEdgeIts[_depth]; 307 354 } … … 346 393 } 347 394 public: 348 Vf2(const G1 &g1, const G2 &g2,I &i, const NEq &nEq = NEq() ) : 349 _nEq(nEq), _conn(g2,0), _match(i), order(countNodes(g1)), 395 ///Constructor 396 397 ///Constructor 398 399 ///\param g1 The graph to be embedded into \e g2. 400 ///\param g2 The graph \e g1 will be embedded into. 401 ///\param m \ref concepts::ReadWriteMap "readwrite" NodeMap 402 ///storing the found mapping. 403 ///\param neq A boolvalued binary functor determinining whether a node is 404 ///mappable to another. By default it is an always true operator. 405 Vf2(const G1 &g1, const G2 &g2,M &m, const NEQ &neq = NEQ() ) : 406 _nEq(neq), _conn(g2,0), _mapping(m), order(countNodes(g1)), 350 407 currEdgeIts(countNodes(g1),INVALID), _g1(g1), _g2(g2), rNew1t(g1,0), 351 408 rInOut1t(g1,0), _mapping_type(SUBGRAPH) … … 356 413 } 357 414 358 MappingType mappingType() const { return _mapping_type; } 359 void mappingType(MappingType m_type) { _mapping_type = m_type; } 360 415 ///Returns the current mapping type 416 417 ///Returns the current mapping type 418 /// 419 Vf2MappingType mappingType() const { return _mapping_type; } 420 ///Sets mapping type 421 422 ///Sets mapping type. 423 /// 424 ///The mapping type is set to \ref SUBGRAPH by default. 425 /// 426 ///\sa See \ref for the possible values. 427 void mappingType(Vf2MappingType m_type) { _mapping_type = m_type; } 428 429 ///Find a mapping 430 431 ///It finds a mapping between from g1 into g2 according to the mapping 432 ///type set by \ref mappingType(Vf2MappingType) "mappingType()". 433 /// 434 ///By subsequent calls, it returns all possible mappings onebyone. 435 /// 436 ///\retval true if a mapping is found. 437 ///\retval false if there is no (more) mapping. 361 438 bool find() 362 439 { … … 385 462 const G2 &_g2; 386 463 387 MappingType _mapping_type;464 Vf2MappingType _mapping_type; 388 465 389 466 typedef typename G1::template NodeMap<typename G2::Node> Mapping; … … 402 479 }; 403 480 481 /// Auxiliary class for the functiontype interface of %VF2 algorithm. 482 483 /// This auxiliary class implements the named parameters of 484 /// \ref vf2() "functiontype interface" of \ref Vf2 algorithm. 485 /// 486 /// \warning This class should only be used through the function \ref vf2(). 487 /// 488 /// \tparam TR The traits class that defines various types used by the 489 /// algorithm. 404 490 template<class TR> 405 491 class Vf2Wizard : public TR … … 419 505 420 506 public: 421 ///Co py constructor507 ///Constructor 422 508 Vf2Wizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {} 423 509 … … 458 544 ///\ref namedtemplparam "Named parameter" function for setting 459 545 ///the equivalence relation between the nodes. 546 /// 547 ///\param node_eq A boolvalued binary functor determinining 548 ///whether a node is mappable to another. By default it is an 549 ///always true operator. 460 550 template<class T> 461 551 Vf2Wizard< SetNodeEqBase<T> > nodeEq(const T &node_eq) … … 469 559 ///\ref namedtemplparam "Named parameter" function for setting 470 560 ///the node labels defining equivalence relation between them. 561 /// 562 ///\param m1 It is arbitrary \ref ReadMap "readable node map" of g1. 563 ///\param m1 It is arbitrary \ref ReadMap "readable node map" of g2. 564 /// 565 ///The value type of these maps must be equal comparable. 471 566 template<class M1, class M2> 472 567 Vf2Wizard< SetNodeEqBase<bits::vf2::MapEq<M1,M2> > > … … 476 571 } 477 572 478 Vf2Wizard<Base> &mappingType(MappingType m_type) 573 ///\brief \ref namedtemplparam "Named parameter" for setting 574 ///the mapping type. 575 /// 576 ///\ref namedtemplparam "Named parameter" for setting 577 ///the mapping type. 578 /// 579 ///The mapping type is set to \ref SUBGRAPH by default. 580 /// 581 ///\sa See \ref for the possible values. 582 Vf2Wizard<Base> &mappingType(Vf2MappingType m_type) 479 583 { 480 584 _mapping_type = m_type; … … 482 586 } 483 587 588 ///\brief \ref namedtemplparam "Named parameter" for setting 589 ///the mapping type to \ref INDUCED. 590 /// 591 ///\ref namedtemplparam "Named parameter" for setting 592 ///the mapping type to \ref INDUCED. 484 593 Vf2Wizard<Base> &induced() 485 594 { … … 488 597 } 489 598 599 ///\brief \ref namedtemplparam "Named parameter" for setting 600 ///the mapping type to \ref ISOMORPH. 601 /// 602 ///\ref namedtemplparam "Named parameter" for setting 603 ///the mapping type to \ref ISOMORPH. 490 604 Vf2Wizard<Base> &iso() 491 605 { … … 494 608 } 495 609 610 ///Runs VF2 algorithm. 611 612 ///This method runs VF2 algorithm. 613 /// 614 ///\retval true if a mapping is found. 615 ///\retval false if there is no (more) mapping. 496 616 bool run() 497 617 { … … 513 633 }; 514 634 635 ///Functiontype interface for VF2 algorithm. 636 637 /// \ingroup graph_isomorphism 638 ///Functiontype interface for VF2 algorithm \cite cordella2004sub. 639 /// 640 ///This function has several \ref namedfuncparam "named parameters" 641 ///declared as the members of class \ref Vf2Wizard. 642 ///The following examples show how to use these parameters. 643 ///\code 644 /// // Find an embedding of graph g into graph h 645 /// ListGraph::NodeMap<ListGraph::Node> m(g); 646 /// vf2(g,h).mapping(m).run(); 647 /// 648 /// // Check whether graphs g and h are isomorphic 649 /// bool is_iso = vf2(g,h).iso().run(); 650 ///\endcode 651 ///\warning Don't forget to put the \ref Vf2Wizard::run() "run()" 652 ///to the end of the expression. 653 ///\sa Vf2Wizard 654 ///\sa Vf2 515 655 template<class G1, class G2> 516 656 Vf2Wizard<Vf2WizardBase<G1,G2> > vf2(const G1 &g1, const G2 &g2)
Note: See TracChangeset
for help on using the changeset viewer.