73 ///implementation of the %VF2 Plus Plus algorithm |
73 ///implementation of the %VF2 Plus Plus algorithm |
74 ///for variants of the (Sub)graph Isomorphism problem. |
74 ///for variants of the (Sub)graph Isomorphism problem. |
75 /// |
75 /// |
76 ///There is also a \ref vf2pp() "function-type interface" called |
76 ///There is also a \ref vf2pp() "function-type interface" called |
77 ///\ref vf2pp() for the %VF2 Plus Plus algorithm, which is probably |
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 ///\tparam G1 The type of the graph to be embedded. |
80 ///\tparam G1 The type of the graph to be embedded. |
81 ///The default type is \ref ListDigraph. |
81 ///The default type is \ref ListDigraph. |
82 ///\tparam G2 The type of the graph g1 will be embedded into. |
82 ///\tparam G2 The type of the graph g1 will be embedded into. |
83 ///The default type is \ref ListDigraph. |
83 ///The default type is \ref ListDigraph. |
94 #ifdef DOXYGEN |
94 #ifdef DOXYGEN |
95 template<class G1, class G2, class M, class M1, class M2 > |
95 template<class G1, class G2, class M, class M1, class M2 > |
96 #else |
96 #else |
97 template<class G1=ListDigraph, |
97 template<class G1=ListDigraph, |
98 class G2=ListDigraph, |
98 class G2=ListDigraph, |
99 class M = typename G1::template NodeMap<G2::Node>,//the mapping |
99 class M = typename G1::template NodeMap<G2::Node>, |
100 //labels of G1,the labels are the numbers {0,1,2,..,K-1}, |
|
101 //where K is the number of different labels |
|
102 class M1 = typename G1::template NodeMap<int>, |
100 class M1 = typename G1::template NodeMap<int>, |
103 //labels of G2, ... |
|
104 class M2 = typename G2::template NodeMap<int> > |
101 class M2 = typename G2::template NodeMap<int> > |
105 #endif |
102 #endif |
106 class Vf2pp { |
103 class Vf2pp { |
107 //Current depth in the search tree. |
104 //Current depth in the search tree. |
108 int _depth; |
105 int _depth; |
112 |
109 |
113 //The current mapping. _mapping[v1]=v2 iff v1 has been mapped to v2, |
110 //The current mapping. _mapping[v1]=v2 iff v1 has been mapped to v2, |
114 //where v1 is a node of G1 and v2 is a node of G2 |
111 //where v1 is a node of G1 and v2 is a node of G2 |
115 M &_mapping; |
112 M &_mapping; |
116 |
113 |
117 //order[i] is a node of g1, for which a pair is searched if depth=i |
114 //order[i] is a node of g1 for which a pair is searched if depth=i |
118 std::vector<typename G1::Node> order; |
115 std::vector<typename G1::Node> order; |
119 |
116 |
120 //currEdgeIts[i] is the last used edge iterator in the ith |
117 //currEdgeIts[i] is the last used edge iterator in the i-th |
121 //depth to find a pair for node order[i] |
118 //depth to find a pair for node order[i] |
122 std::vector<typename G2::IncEdgeIt> currEdgeIts; |
119 std::vector<typename G2::IncEdgeIt> currEdgeIts; |
123 |
120 |
124 //The small graph. |
121 //The graph to be embedded |
125 const G1 &_g1; |
122 const G1 &_g1; |
126 |
123 |
127 //The large graph. |
124 //The graph into which g1 is to be embedded |
128 const G2 &_g2; |
125 const G2 &_g2; |
129 |
126 |
130 //rNewLabels1[v] is a pair of form |
127 //rNewLabels1[v] is a pair of form |
131 //(label; num. of uncov. nodes with such label and no covered neighbours) |
128 //(label; num. of uncov. nodes with such label and no covered neighbours) |
132 typename G1::template NodeMap<std::vector<std::pair<int,int> > > |
129 typename G1::template NodeMap<std::vector<std::pair<int,int> > > |
135 //rInOutLabels1[v] is the number of covered neighbours of v for each label |
132 //rInOutLabels1[v] is the number of covered neighbours of v for each label |
136 //in form (label,number of such labels) |
133 //in form (label,number of such labels) |
137 typename G1::template NodeMap<std::vector<std::pair<int,int> > > |
134 typename G1::template NodeMap<std::vector<std::pair<int,int> > > |
138 rInOutLabels1; |
135 rInOutLabels1; |
139 |
136 |
140 //_intLabels1[v]==i means that vertex v has the i label in |
137 //_intLabels1[v]==i means that node v has label i in _g1 |
141 //_g1 (i is in {0,1,2,..,K-1}, where K is the number of diff. labels) |
138 //(i is in {0,1,2,..,K-1}, where K is the number of diff. labels) |
142 M1 &_intLabels1; |
139 M1 &_intLabels1; |
143 |
140 |
144 //_intLabels2[v]==i means that vertex v has the i label in |
141 //_intLabels2[v]==i means that node v has label i in _g2 |
145 //_g2 (i is in {0,1,2,..,K-1}, where K is the number of diff. labels) |
142 //(i is in {0,1,2,..,K-1}, where K is the number of diff. labels) |
146 M2 &_intLabels2; |
143 M2 &_intLabels2; |
147 |
144 |
148 //largest label |
145 //largest label |
149 const int maxLabel; |
146 const int maxLabel; |
150 |
147 |
151 //lookup tables for manipulating with label class cardinalities |
148 //lookup tables for manipulating with label class cardinalities |
152 //after use they have to be reset to 0..0 |
149 //(after use they have to be reset to 0..0) |
153 std::vector<int> labelTmp1,labelTmp2; |
150 std::vector<int> labelTmp1,labelTmp2; |
154 |
151 |
155 MappingType _mapping_type; |
152 MappingType _mapping_type; |
156 |
153 |
157 //indicates whether the mapping or the labels must be deleted in the ctor |
154 //indicates whether the mapping or the labels must be deleted in the destructor |
158 bool _deallocMappingAfterUse,_deallocLabelsAfterUse; |
155 bool _deallocMappingAfterUse,_deallocLabelsAfterUse; |
159 |
156 |
160 |
157 |
161 //improved cutting function |
158 //improved cutting function |
162 template<MappingType MT> |
159 template<MappingType MT> |
284 } |
281 } |
285 |
282 |
286 return isIso&&cutByLabels<MT>(n1,n2); |
283 return isIso&&cutByLabels<MT>(n1,n2); |
287 } |
284 } |
288 |
285 |
289 |
286 //maps n1 to n2 |
290 //matches n1 and n2 |
|
291 void addPair(const typename G1::Node n1,const typename G2::Node n2) { |
287 void addPair(const typename G1::Node n1,const typename G2::Node n2) { |
292 _conn[n2]=-1; |
288 _conn[n2]=-1; |
293 _mapping.set(n1,n2); |
289 _mapping.set(n1,n2); |
294 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) { |
290 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) { |
295 int& currConn = _conn[_g2.oppositeNode(n2,e2)]; |
291 int& currConn = _conn[_g2.oppositeNode(n2,e2)]; |
296 if(currConn!=-1) |
292 if(currConn!=-1) |
297 ++currConn; |
293 ++currConn; |
298 } |
294 } |
299 } |
295 } |
300 |
296 |
301 |
297 //removes mapping of n1 to n2 |
302 //dematches n1 and n2 |
|
303 void subPair(const typename G1::Node n1,const typename G2::Node n2) { |
298 void subPair(const typename G1::Node n1,const typename G2::Node n2) { |
304 _conn[n2]=0; |
299 _conn[n2]=0; |
305 _mapping.set(n1,INVALID); |
300 _mapping.set(n1,INVALID); |
306 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2){ |
301 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2){ |
307 int& currConn = _conn[_g2.oppositeNode(n2,e2)]; |
302 int& currConn = _conn[_g2.oppositeNode(n2,e2)]; |
395 |
388 |
396 |
389 |
397 template<MappingType MT> |
390 template<MappingType MT> |
398 bool extMatch(){ |
391 bool extMatch(){ |
399 while(_depth>=0) { |
392 while(_depth>=0) { |
400 //there is no node in g1, which has not pair in g2. |
|
401 if(_depth==static_cast<int>(order.size())) { |
393 if(_depth==static_cast<int>(order.size())) { |
|
394 //all nodes of g1 are mapped to nodes of g2 |
402 --_depth; |
395 --_depth; |
403 return true; |
396 return true; |
404 } |
397 } |
405 typename G1::Node& nodeOfDepth = order[_depth]; |
398 typename G1::Node& nodeOfDepth = order[_depth]; |
406 const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth]; |
399 const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth]; |
407 typename G2::IncEdgeIt &edgeItOfDepth = currEdgeIts[_depth]; |
400 typename G2::IncEdgeIt &edgeItOfDepth = currEdgeIts[_depth]; |
408 //the node of g2, which neighbours are the candidates for |
401 //the node of g2 whose neighbours are the candidates for |
409 //the pair of order[_depth] |
402 //the pair of order[_depth] |
410 typename G2::Node currPNode; |
403 typename G2::Node currPNode; |
411 if(edgeItOfDepth==INVALID){ |
404 if(edgeItOfDepth==INVALID){ |
412 typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth); |
405 typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth); |
413 //if _mapping[order[_depth]]!=INVALID, we dont need |
406 //if _mapping[order[_depth]]!=INVALID, we don't need fstMatchedE |
414 //fstMatchedE |
407 if(pairOfNodeOfDepth==INVALID) { |
415 if(pairOfNodeOfDepth==INVALID) |
|
416 for(; fstMatchedE!=INVALID && |
408 for(; fstMatchedE!=INVALID && |
417 _mapping[_g1.oppositeNode(nodeOfDepth, |
409 _mapping[_g1.oppositeNode(nodeOfDepth, |
418 fstMatchedE)]==INVALID; |
410 fstMatchedE)]==INVALID; |
419 ++fstMatchedE); //find fstMatchedE, it could be preprocessed |
411 ++fstMatchedE); //find fstMatchedE, it could be preprocessed |
|
412 } |
420 if(fstMatchedE==INVALID||pairOfNodeOfDepth!=INVALID) { |
413 if(fstMatchedE==INVALID||pairOfNodeOfDepth!=INVALID) { |
421 //We found no covered neighbours, this means |
414 //We found no covered neighbours, this means that |
422 //the graph is not connected(or _depth==0). Each |
415 //the graph is not connected (or _depth==0). Each |
423 //uncovered(and there are some other properties due |
416 //uncovered (and there are some other properties due |
424 //to the spec. problem types) node of g2 is |
417 //to the spec. problem types) node of g2 is |
425 //candidate. We can read the iterator of the last |
418 //candidate. We can read the iterator of the last |
426 //tried node from the match if it is not the first |
419 //tried node from the match if it is not the first |
427 //try(match[nodeOfDepth]!=INVALID) |
420 //try (match[nodeOfDepth]!=INVALID) |
428 typename G2::NodeIt n2(_g2); |
421 typename G2::NodeIt n2(_g2); |
429 //if it's not the first try |
422 //if it's not the first try |
430 if(pairOfNodeOfDepth!=INVALID) { |
423 if(pairOfNodeOfDepth!=INVALID) { |
431 n2=++typename G2::NodeIt(_g2,pairOfNodeOfDepth); |
424 n2=++typename G2::NodeIt(_g2,pairOfNodeOfDepth); |
432 subPair(nodeOfDepth,pairOfNodeOfDepth); |
425 subPair(nodeOfDepth,pairOfNodeOfDepth); |
470 edgeItOfDepth==INVALID?--_depth:++_depth; |
463 edgeItOfDepth==INVALID?--_depth:++_depth; |
471 } |
464 } |
472 return false; |
465 return false; |
473 } |
466 } |
474 |
467 |
475 //calc. the lookup table for cutting the searchtree |
468 //calculate the lookup table for cutting the search tree |
476 void setRNew1tRInOut1t(){ |
469 void setRNew1tRInOut1t(){ |
477 typename G1::template NodeMap<int> tmp(_g1,0); |
470 typename G1::template NodeMap<int> tmp(_g1,0); |
478 for(unsigned int i=0; i<order.size(); ++i) { |
471 for(unsigned int i=0; i<order.size(); ++i) { |
479 tmp[order[i]]=-1; |
472 tmp[order[i]]=-1; |
480 for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1) { |
473 for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1) { |
673 using TR::_nodeLabels1; |
666 using TR::_nodeLabels1; |
674 using TR::_nodeLabels2; |
667 using TR::_nodeLabels2; |
675 |
668 |
676 public: |
669 public: |
677 ///Constructor |
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 ///Copy constructor |
673 ///Copy constructor |
681 Vf2ppWizard(const Base &b) : Base(b) {} |
674 Vf2ppWizard(const Base &b) : Base(b) {} |
682 |
675 |
683 |
676 |
684 template<typename T> |
677 template<typename T> |
685 struct SetMappingBase : public Base { |
678 struct SetMappingBase : public Base { |
686 typedef T Mapping; |
679 typedef T Mapping; |
687 SetMappingBase(const Base &b) : Base(b) { } |
680 SetMappingBase(const Base &b) : Base(b) {} |
688 }; |
681 }; |
689 |
682 |
690 ///\brief \ref named-templ-param "Named parameter" for setting |
683 ///\brief \ref named-templ-param "Named parameter" for setting |
691 ///the mapping. |
684 ///the mapping. |
692 /// |
685 /// |
711 /// |
704 /// |
712 ///\ref named-templ-param "Named parameter" function for setting |
705 ///\ref named-templ-param "Named parameter" function for setting |
713 ///the node labels. |
706 ///the node labels. |
714 /// |
707 /// |
715 ///\param nodeLabels1 A \ref concepts::ReadMap "readable node map" |
708 ///\param nodeLabels1 A \ref concepts::ReadMap "readable node map" |
716 ///of g1 with integer value. In case of K different labels, the labels |
709 ///of g1 with integer values. In case of K different labels, the labels |
717 ///must be the {0,1,..,K-1} numbers. |
710 ///must be the numbers {0,1,..,K-1}. |
718 ///\param nodeLabels2 A \ref concepts::ReadMap "readable node map" |
711 ///\param nodeLabels2 A \ref concepts::ReadMap "readable node map" |
719 ///of g2 with integer value. In case of K different labels, the labels |
712 ///of g2 with integer values. In case of K different labels, the labels |
720 ///must be the {0,1,..,K-1} numbers. |
713 ///must be the numbers {0,1,..,K-1}. |
721 template<typename NL1, typename NL2> |
714 template<typename NL1, typename NL2> |
722 Vf2ppWizard< SetNodeLabelsBase<NL1,NL2> > |
715 Vf2ppWizard< SetNodeLabelsBase<NL1,NL2> > |
723 nodeLabels(const NL1 &nodeLabels1, const NL2 &nodeLabels2) { |
716 nodeLabels(const NL1 &nodeLabels1, const NL2 &nodeLabels2) { |
724 Base::_local_nodeLabels = 0; |
717 Base::_local_nodeLabels = 0; |
725 Base::_nodeLabels1= |
718 Base::_nodeLabels1= |
875 /// |
868 /// |
876 /// // Count the number of isomorphisms |
869 /// // Count the number of isomorphisms |
877 /// int num_isos = vf2pp(g1,g2).iso().count(); |
870 /// int num_isos = vf2pp(g1,g2).iso().count(); |
878 /// |
871 /// |
879 /// // Iterate through all the induced subgraph mappings |
872 /// // Iterate through all the induced subgraph mappings |
880 /// //of graph g1 into g2 using the labels c1 and c2 |
873 /// // of graph g1 into g2 using the labels c1 and c2 |
881 /// auto* myVf2pp = vf2pp(g1,g2).mapping(m).nodeLabels(c1,c2) |
874 /// auto* myVf2pp = vf2pp(g1,g2).mapping(m).nodeLabels(c1,c2) |
882 /// .induced().getPtrToVf2Object(); |
875 /// .induced().getPtrToVf2Object(); |
883 /// while(myVf2pp->find()){ |
876 /// while(myVf2pp->find()){ |
884 /// //process the current mapping m |
877 /// //process the current mapping m |
885 /// } |
878 /// } |