1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2015-2017
6 * EMAXA Kutato-fejleszto Kft. (EMAXA Research Ltd.)
8 * Permission to use, modify and distribute this software is granted
9 * provided that this copyright notice appears in all copies. For
10 * precise terms see the accompanying LICENSE file.
12 * This software is provided "AS IS" with no warranty of any kind,
13 * express or implied, and with no claim as to its suitability for any
21 ///\ingroup graph_properties
23 ///\brief VF2 Plus Plus algorithm.
25 #include <lemon/core.h>
26 #include <lemon/concepts/graph.h>
27 #include <lemon/dfs.h>
28 #include <lemon/bfs.h>
29 #include <lemon/bits/vf2_internals.h>
42 class DfsLeaveOrder : public DfsVisitor<G> {
45 std::vector<typename G::Node> &_order;
47 DfsLeaveOrder(const G &g, std::vector<typename G::Node> &order)
48 : i(countNodes(g)), _g(g), _order(order) {
50 void leave(const typename G::Node &node) {
56 class BfsLeaveOrder : public BfsVisitor<G> {
59 std::vector<typename G::Node> &_order;
61 BfsLeaveOrder(const G &g, std::vector<typename G::Node> &order) { }
62 void process(const typename G::Node &node) {
70 ///%VF2 Plus Plus algorithm class.
72 ///\ingroup graph_isomorphism This class provides an efficient
73 ///implementation of the %VF2 Plus Plus algorithm
74 ///for variants of the (Sub)graph Isomorphism problem.
76 ///There is also a \ref vf2pp() "function-type interface" called
77 ///\ref vf2pp() for the %VF2 Plus Plus algorithm, which is probably
78 ///more convenient in most use-cases.
80 ///\tparam G1 The type of the graph to be embedded.
81 ///The default type is \ref ListDigraph.
82 ///\tparam G2 The type of the graph g1 will be embedded into.
83 ///The default type is \ref ListDigraph.
84 ///\tparam M The type of the NodeMap storing the mapping.
85 ///By default, it is G1::NodeMap<G2::Node>
86 ///\tparam M1 The type of the NodeMap storing the integer node labels of G1.
87 ///The labels must be the numbers {0,1,2,..,K-1}, where K is the number of
88 ///different labels. By default, it is G1::NodeMap<int>.
89 ///\tparam M2 The type of the NodeMap storing the integer node labels of G2.
90 ///The labels must be the numbers {0,1,2,..,K-1}, where K is the number of
91 ///different labels. By default, it is G2::NodeMap<int>.
95 template<class G1, class G2, class M, class M1, class M2 >
97 template<class G1=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
102 class M1 = typename G1::template NodeMap<int>,
104 class M2 = typename G2::template NodeMap<int> >
107 //Current depth in the search tree.
110 //_conn[v2] = number of covered neighbours of v2
111 typename G2::template NodeMap<int> _conn;
113 //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
117 //order[i] is a node of g1, for which a pair is searched if depth=i
118 std::vector<typename G1::Node> order;
120 //currEdgeIts[i] is the last used edge iterator in the ith
121 //depth to find a pair for node order[i]
122 std::vector<typename G2::IncEdgeIt> currEdgeIts;
130 //rNewLabels1[v] is a pair of form
131 //(label; num. of uncov. nodes with such label and no covered neighbours)
132 typename G1::template NodeMap<std::vector<std::pair<int,int> > >
135 //rInOutLabels1[v] is the number of covered neighbours of v for each label
136 //in form (label,number of such labels)
137 typename G1::template NodeMap<std::vector<std::pair<int,int> > >
140 //_intLabels1[v]==i means that vertex v has the i label in
141 //_g1 (i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
144 //_intLabels2[v]==i means that vertex v has the i label in
145 //_g2 (i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
151 //lookup tables for manipulating with label class cardinalities
152 //after use they have to be reset to 0..0
153 std::vector<int> labelTmp1,labelTmp2;
155 MappingType _mapping_type;
157 //indicates whether the mapping or the labels must be deleted in the ctor
158 bool _deallocMappingAfterUse,_deallocLabelsAfterUse;
161 //improved cutting function
162 template<MappingType MT>
163 bool cutByLabels(const typename G1::Node n1,const typename G2::Node n2) {
164 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
165 const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
166 if(_conn[currNode]>0)
167 --labelTmp1[_intLabels2[currNode]];
168 else if(MT!=SUBGRAPH&&_conn[currNode]==0)
169 --labelTmp2[_intLabels2[currNode]];
174 for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i)
175 labelTmp1[rInOutLabels1[n1][i].first]+=rInOutLabels1[n1][i].second;
178 for(unsigned int i = 0; i < rNewLabels1[n1].size(); ++i)
179 labelTmp2[rNewLabels1[n1][i].first]+=rNewLabels1[n1][i].second;
183 for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i)
184 if(labelTmp1[rInOutLabels1[n1][i].first]>0) {
189 for(unsigned int i = 0; i < rNewLabels1[n1].size(); ++i)
190 if(labelTmp2[rNewLabels1[n1][i].first]>0) {
196 for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i)
197 if(labelTmp1[rInOutLabels1[n1][i].first]>0) {
203 for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i)
204 if(labelTmp1[rInOutLabels1[n1][i].first]!=0) {
209 for(unsigned int i = 0; i < rNewLabels1[n1].size(); ++i)
210 if(labelTmp2[rNewLabels1[n1][i].first]!=0) {
218 for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i)
219 labelTmp1[rInOutLabels1[n1][i].first]=0;
222 for(unsigned int i = 0; i < rNewLabels1[n1].size(); ++i)
223 labelTmp2[rNewLabels1[n1][i].first]=0;
226 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
227 const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
228 labelTmp1[_intLabels2[currNode]]=0;
229 if(MT!=SUBGRAPH&&_conn[currNode]==0)
230 labelTmp2[_intLabels2[currNode]]=0;
237 //try to exclude the matching of n1 and n2
238 template<MappingType MT>
239 bool feas(const typename G1::Node n1,const typename G2::Node n2) {
240 if(_intLabels1[n1]!=_intLabels2[n2])
243 for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
244 const typename G1::Node& currNode=_g1.oppositeNode(n1,e1);
245 if(_mapping[currNode]!=INVALID)
246 --_conn[_mapping[currNode]];
250 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
251 int& connCurrNode = _conn[_g2.oppositeNode(n2,e2)];
254 else if(MT!=SUBGRAPH&&connCurrNode==-1) {
261 for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
262 const typename G2::Node& currNodePair =
263 _mapping[_g1.oppositeNode(n1,e1)];
264 int& connCurrNodePair=_conn[currNodePair];
265 if(currNodePair!=INVALID&&connCurrNodePair!=-1) {
272 if(connCurrNodePair<-1)
280 for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
281 const typename G2::Node currNode=_mapping[_g1.oppositeNode(n1,e1)];
282 if(currNode!=INVALID/*&&_conn[currNode]!=-1*/)
286 return isIso&&cutByLabels<MT>(n1,n2);
291 void addPair(const typename G1::Node n1,const typename G2::Node n2) {
294 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
295 int& currConn = _conn[_g2.oppositeNode(n2,e2)];
302 //dematches n1 and n2
303 void subPair(const typename G1::Node n1,const typename G2::Node n2) {
305 _mapping.set(n1,INVALID);
306 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2){
307 int& currConn = _conn[_g2.oppositeNode(n2,e2)];
310 else if(currConn==-1)
316 void processBFSLevel(typename G1::Node source,unsigned int& orderIndex,
317 typename G1::template NodeMap<int>& dm1,
318 typename G1::template NodeMap<bool>& added) {
319 order[orderIndex]=source;
322 unsigned int endPosOfLevel=orderIndex,
323 startPosOfLevel=orderIndex,
324 lastAdded=orderIndex;
326 typename G1::template NodeMap<int> currConn(_g1,0);
328 while(orderIndex<=lastAdded){
329 typename G1::Node currNode = order[orderIndex];
330 for(typename G1::IncEdgeIt e(_g1,currNode); e!=INVALID; ++e) {
331 typename G1::Node n = _g1.oppositeNode(currNode,e);
333 order[++lastAdded]=n;
337 if(orderIndex>endPosOfLevel){
338 for(unsigned int j = startPosOfLevel; j <= endPosOfLevel; ++j) {
340 for(unsigned int i = j+1; i <= endPosOfLevel; ++i)
341 if(currConn[order[i]]>currConn[order[minInd]]||
342 (currConn[order[i]]==currConn[order[minInd]]&&
343 (dm1[order[i]]>dm1[order[minInd]]||
344 (dm1[order[i]]==dm1[order[minInd]]&&
345 labelTmp1[_intLabels1[order[minInd]]]>
346 labelTmp1[_intLabels1[order[i]]]))))
349 --labelTmp1[_intLabels1[order[minInd]]];
350 for(typename G1::IncEdgeIt e(_g1,order[minInd]); e!=INVALID; ++e)
351 ++currConn[_g1.oppositeNode(order[minInd],e)];
352 std::swap(order[j],order[minInd]);
354 startPosOfLevel=endPosOfLevel+1;
355 endPosOfLevel=lastAdded;
362 //we will find pairs for the nodes of g1 in this order
364 for(typename G2::NodeIt n2(_g2); n2!=INVALID; ++n2)
365 ++labelTmp1[_intLabels2[n2]];
367 // OutDegMap<G1> dm1(_g1);
368 typename G1::template NodeMap<int> dm1(_g1,0);
369 for(typename G1::EdgeIt e(_g1); e!=INVALID; ++e) {
374 typename G1::template NodeMap<bool> added(_g1,0);
375 unsigned int orderIndex=0;
377 for(typename G1::NodeIt n(_g1); n!=INVALID;) {
379 typename G1::Node minNode = n;
380 for(typename G1::NodeIt n1(_g1,minNode); n1!=INVALID; ++n1)
382 (labelTmp1[_intLabels1[minNode]]>
383 labelTmp1[_intLabels1[n1]]||(dm1[minNode]<dm1[n1]&&
384 labelTmp1[_intLabels1[minNode]]==
385 labelTmp1[_intLabels1[n1]])))
387 processBFSLevel(minNode,orderIndex,dm1,added);
392 for(unsigned int i = 0; i < labelTmp1.size(); ++i)
397 template<MappingType MT>
400 //there is no node in g1, which has not pair in g2.
401 if(_depth==static_cast<int>(order.size())) {
405 typename G1::Node& nodeOfDepth = order[_depth];
406 const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth];
407 typename G2::IncEdgeIt &edgeItOfDepth = currEdgeIts[_depth];
408 //the node of g2, which neighbours are the candidates for
409 //the pair of order[_depth]
410 typename G2::Node currPNode;
411 if(edgeItOfDepth==INVALID){
412 typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth);
413 //if _mapping[order[_depth]]!=INVALID, we dont need
415 if(pairOfNodeOfDepth==INVALID)
416 for(; fstMatchedE!=INVALID &&
417 _mapping[_g1.oppositeNode(nodeOfDepth,
418 fstMatchedE)]==INVALID;
419 ++fstMatchedE); //find fstMatchedE, it could be preprocessed
420 if(fstMatchedE==INVALID||pairOfNodeOfDepth!=INVALID) {
421 //We found no covered neighbours, this means
422 //the graph is not connected(or _depth==0). Each
423 //uncovered(and there are some other properties due
424 //to the spec. problem types) node of g2 is
425 //candidate. We can read the iterator of the last
426 //tried node from the match if it is not the first
427 //try(match[nodeOfDepth]!=INVALID)
428 typename G2::NodeIt n2(_g2);
429 //if it's not the first try
430 if(pairOfNodeOfDepth!=INVALID) {
431 n2=++typename G2::NodeIt(_g2,pairOfNodeOfDepth);
432 subPair(nodeOfDepth,pairOfNodeOfDepth);
434 for(; n2!=INVALID; ++n2)
436 if(_conn[n2]==0&&feas<MT>(nodeOfDepth,n2))
439 else if(_conn[n2]>=0&&feas<MT>(nodeOfDepth,n2))
441 // n2 is the next candidate
443 addPair(nodeOfDepth,n2);
446 else // there are no more candidates
451 currPNode=_mapping[_g1.oppositeNode(nodeOfDepth,
453 edgeItOfDepth=typename G2::IncEdgeIt(_g2,currPNode);
457 currPNode=_g2.oppositeNode(pairOfNodeOfDepth,
459 subPair(nodeOfDepth,pairOfNodeOfDepth);
462 for(; edgeItOfDepth!=INVALID; ++edgeItOfDepth) {
463 const typename G2::Node currNode =
464 _g2.oppositeNode(currPNode, edgeItOfDepth);
465 if(_conn[currNode]>0&&feas<MT>(nodeOfDepth,currNode)) {
466 addPair(nodeOfDepth,currNode);
470 edgeItOfDepth==INVALID?--_depth:++_depth;
475 //calc. the lookup table for cutting the searchtree
476 void setRNew1tRInOut1t(){
477 typename G1::template NodeMap<int> tmp(_g1,0);
478 for(unsigned int i=0; i<order.size(); ++i) {
480 for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1) {
481 const typename G1::Node currNode=_g1.oppositeNode(order[i],e1);
483 ++labelTmp1[_intLabels1[currNode]];
484 else if(tmp[currNode]==0)
485 ++labelTmp2[_intLabels1[currNode]];
487 //labelTmp1[i]=number of neightbours with label i in set rInOut
488 //labelTmp2[i]=number of neightbours with label i in set rNew
489 for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1) {
490 const int& currIntLabel = _intLabels1[_g1.oppositeNode(order[i],e1)];
491 if(labelTmp1[currIntLabel]>0) {
492 rInOutLabels1[order[i]]
493 .push_back(std::make_pair(currIntLabel,
494 labelTmp1[currIntLabel]));
495 labelTmp1[currIntLabel]=0;
497 else if(labelTmp2[currIntLabel]>0) {
498 rNewLabels1[order[i]].
499 push_back(std::make_pair(currIntLabel,labelTmp2[currIntLabel]));
500 labelTmp2[currIntLabel]=0;
504 for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1) {
505 int& tmpCurrNode=tmp[_g1.oppositeNode(order[i],e1)];
512 int getMaxLabel() const{
514 for(typename G1::NodeIt n1(_g1); n1!=INVALID; ++n1) {
515 const int& currIntLabel = _intLabels1[n1];
519 for(typename G2::NodeIt n2(_g2); n2!=INVALID; ++n2) {
520 const int& currIntLabel = _intLabels2[n2];
531 ///\param g1 The graph to be embedded.
532 ///\param g2 The graph \e g1 will be embedded into.
533 ///\param m The type of the NodeMap storing the mapping.
534 ///By default, it is G1::NodeMap<G2::Node>
535 ///\param intLabel1 The NodeMap storing the integer node labels of G1.
536 ///The labels must be the numbers {0,1,2,..,K-1}, where K is the number of
538 ///\param intLabel1 The NodeMap storing the integer node labels of G2.
539 ///The labels must be the numbers {0,1,2,..,K-1}, where K is the number of
541 Vf2pp(const G1 &g1, const G2 &g2,M &m, M1 &intLabels1, M2 &intLabels2) :
542 _depth(0), _conn(g2,0), _mapping(m), order(countNodes(g1),INVALID),
543 currEdgeIts(countNodes(g1),INVALID), _g1(g1), _g2(g2), rNewLabels1(_g1),
544 rInOutLabels1(_g1), _intLabels1(intLabels1) ,_intLabels2(intLabels2),
545 maxLabel(getMaxLabel()), labelTmp1(maxLabel+1),labelTmp2(maxLabel+1),
546 _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0),
547 _deallocLabelsAfterUse(0)
553 for(typename G1::NodeIt n(g1);n!=INVALID;++n)
563 if(_deallocMappingAfterUse)
565 if(_deallocLabelsAfterUse) {
571 ///Returns the current mapping type.
573 ///Returns the current mapping type.
575 MappingType mappingType() const
577 return _mapping_type;
580 ///Sets the mapping type
582 ///Sets the mapping type.
584 ///The mapping type is set to \ref SUBGRAPH by default.
586 ///\sa See \ref MappingType for the possible values.
587 void mappingType(MappingType m_type)
589 _mapping_type = m_type;
594 ///This method finds a mapping from g1 into g2 according to the mapping
595 ///type set by \ref mappingType(MappingType) "mappingType()".
597 ///By subsequent calls, it returns all possible mappings one-by-one.
599 ///\retval true if a mapping is found.
600 ///\retval false if there is no (more) mapping.
603 switch(_mapping_type)
606 return extMatch<SUBGRAPH>();
608 return extMatch<INDUCED>();
610 return extMatch<ISOMORPH>();
617 template<typename G1, typename G2>
618 class Vf2ppWizardBase {
626 MappingType _mapping_type;
628 typedef typename G1::template NodeMap<typename G2::Node> Mapping;
631 void createMapping() {
632 _mapping = new Mapping(_g1);
635 bool _local_nodeLabels;
636 typedef typename G1::template NodeMap<int> NodeLabels1;
637 typedef typename G2::template NodeMap<int> NodeLabels2;
638 void *_nodeLabels1, *_nodeLabels2;
639 void createNodeLabels() {
640 _nodeLabels1 = new NodeLabels1(_g1,0);
641 _nodeLabels2 = new NodeLabels2(_g2,0);
644 Vf2ppWizardBase(const G1 &g1,const G2 &g2)
645 : _g1(g1), _g2(g2), _mapping_type(SUBGRAPH),
646 _local_mapping(1), _local_nodeLabels(1) { }
650 /// \brief Auxiliary class for the function-type interface of %VF2
651 /// Plus Plus algorithm.
653 /// This auxiliary class implements the named parameters of
654 /// \ref vf2pp() "function-type interface" of \ref Vf2pp algorithm.
656 /// \warning This class is not to be used directly.
658 /// \tparam TR The traits class that defines various types used by the
660 template<typename TR>
661 class Vf2ppWizard : public TR {
663 typedef typename TR::Graph1 Graph1;
664 typedef typename TR::Graph2 Graph2;
665 typedef typename TR::Mapping Mapping;
666 typedef typename TR::NodeLabels1 NodeLabels1;
667 typedef typename TR::NodeLabels2 NodeLabels2;
671 using TR::_mapping_type;
673 using TR::_nodeLabels1;
674 using TR::_nodeLabels2;
678 Vf2ppWizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) { }
681 Vf2ppWizard(const Base &b) : Base(b) {}
685 struct SetMappingBase : public Base {
687 SetMappingBase(const Base &b) : Base(b) { }
690 ///\brief \ref named-templ-param "Named parameter" for setting
693 ///\ref named-templ-param "Named parameter" function for setting
694 ///the map that stores the found embedding.
696 Vf2ppWizard< SetMappingBase<T> > mapping(const T &t) {
697 Base::_mapping=reinterpret_cast<void*>(const_cast<T*>(&t));
698 Base::_local_mapping = 0;
699 return Vf2ppWizard<SetMappingBase<T> >(*this);
702 template<typename NL1, typename NL2>
703 struct SetNodeLabelsBase : public Base {
704 typedef NL1 NodeLabels1;
705 typedef NL2 NodeLabels2;
706 SetNodeLabelsBase(const Base &b) : Base(b) { }
709 ///\brief \ref named-templ-param "Named parameter" for setting the
712 ///\ref named-templ-param "Named parameter" function for setting
715 ///\param nodeLabels1 A \ref concepts::ReadMap "readable node map"
716 ///of g1 with integer value. In case of K different labels, the labels
717 ///must be the {0,1,..,K-1} numbers.
718 ///\param nodeLabels2 A \ref concepts::ReadMap "readable node map"
719 ///of g2 with integer value. In case of K different labels, the labels
720 ///must be the {0,1,..,K-1} numbers.
721 template<typename NL1, typename NL2>
722 Vf2ppWizard< SetNodeLabelsBase<NL1,NL2> >
723 nodeLabels(const NL1 &nodeLabels1, const NL2 &nodeLabels2) {
724 Base::_local_nodeLabels = 0;
726 reinterpret_cast<void*>(const_cast<NL1*>(&nodeLabels1));
728 reinterpret_cast<void*>(const_cast<NL2*>(&nodeLabels2));
729 return Vf2ppWizard<SetNodeLabelsBase<NL1,NL2> >
730 (SetNodeLabelsBase<NL1,NL2>(*this));
734 ///\brief \ref named-templ-param "Named parameter" for setting
737 ///\ref named-templ-param "Named parameter" for setting
740 ///The mapping type is set to \ref SUBGRAPH by default.
742 ///\sa See \ref MappingType for the possible values.
743 Vf2ppWizard<Base> &mappingType(MappingType m_type) {
744 _mapping_type = m_type;
748 ///\brief \ref named-templ-param "Named parameter" for setting
749 ///the mapping type to \ref INDUCED.
751 ///\ref named-templ-param "Named parameter" for setting
752 ///the mapping type to \ref INDUCED.
753 Vf2ppWizard<Base> &induced() {
754 _mapping_type = INDUCED;
758 ///\brief \ref named-templ-param "Named parameter" for setting
759 ///the mapping type to \ref ISOMORPH.
761 ///\ref named-templ-param "Named parameter" for setting
762 ///the mapping type to \ref ISOMORPH.
763 Vf2ppWizard<Base> &iso() {
764 _mapping_type = ISOMORPH;
768 ///Runs the %VF2 Plus Plus algorithm.
770 ///This method runs the VF2 Plus Plus algorithm.
772 ///\retval true if a mapping is found.
773 ///\retval false if there is no mapping.
775 if(Base::_local_mapping)
776 Base::createMapping();
777 if(Base::_local_nodeLabels)
778 Base::createNodeLabels();
780 Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2 >
781 alg(_g1, _g2, *reinterpret_cast<Mapping*>(_mapping),
782 *reinterpret_cast<NodeLabels1*>(_nodeLabels1),
783 *reinterpret_cast<NodeLabels2*>(_nodeLabels2));
785 alg.mappingType(_mapping_type);
787 const bool ret = alg.find();
789 if(Base::_local_nodeLabels) {
790 delete reinterpret_cast<NodeLabels1*>(_nodeLabels1);
791 delete reinterpret_cast<NodeLabels2*>(_nodeLabels2);
793 if(Base::_local_mapping)
794 delete reinterpret_cast<Mapping*>(_mapping);
799 ///Get a pointer to the generated Vf2pp object.
801 ///Gives a pointer to the generated Vf2pp object.
803 ///\return Pointer to the generated Vf2pp object.
804 ///\warning Don't forget to delete the referred Vf2pp object after use.
805 Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2 >*
806 getPtrToVf2ppObject(){
807 if(Base::_local_mapping)
808 Base::createMapping();
809 if(Base::_local_nodeLabels)
810 Base::createNodeLabels();
812 Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2 >* ptr =
813 new Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2>
814 (_g1, _g2, *reinterpret_cast<Mapping*>(_mapping),
815 *reinterpret_cast<NodeLabels1*>(_nodeLabels1),
816 *reinterpret_cast<NodeLabels2*>(_nodeLabels2));
817 ptr->mappingType(_mapping_type);
818 if(Base::_local_mapping)
819 ptr->_deallocMappingAfterUse=true;
820 if(Base::_local_nodeLabels)
821 ptr->_deallocLabelMapsAfterUse=true;
826 ///Counts the number of mappings.
828 ///This method counts the number of mappings.
830 /// \return The number of mappings.
832 if(Base::_local_mapping)
833 Base::createMapping();
834 if(Base::_local_nodeLabels)
835 Base::createNodeLabels();
837 Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2>
838 alg(_g1, _g2, *reinterpret_cast<Mapping*>(_mapping),
839 *reinterpret_cast<NodeLabels1*>(_nodeLabels1),
840 *reinterpret_cast<NodeLabels2*>(_nodeLabels2));
842 alg.mappingType(_mapping_type);
848 if(Base::_local_nodeLabels) {
849 delete reinterpret_cast<NodeLabels1*>(_nodeLabels1);
850 delete reinterpret_cast<NodeLabels2*>(_nodeLabels2);
852 if(Base::_local_mapping)
853 delete reinterpret_cast<Mapping*>(_mapping);
860 ///Function-type interface for VF2 Plus Plus algorithm.
862 /// \ingroup graph_isomorphism
863 ///Function-type interface for VF2 Plus Plus algorithm.
865 ///This function has several \ref named-func-param "named parameters"
866 ///declared as the members of class \ref Vf2ppWizard.
867 ///The following examples show how to use these parameters.
869 /// ListGraph::NodeMap<ListGraph::Node> m(g);
870 /// // Find an embedding of graph g1 into graph g2
871 /// vf2pp(g1,g2).mapping(m).run();
873 /// // Check whether graphs g1 and g2 are isomorphic
874 /// bool is_iso = vf2pp(g1,g2).iso().run();
876 /// // Count the number of isomorphisms
877 /// int num_isos = vf2pp(g1,g2).iso().count();
879 /// // Iterate through all the induced subgraph mappings
880 /// //of graph g1 into g2 using the labels c1 and c2
881 /// auto* myVf2pp = vf2pp(g1,g2).mapping(m).nodeLabels(c1,c2)
882 /// .induced().getPtrToVf2Object();
883 /// while(myVf2pp->find()){
884 /// //process the current mapping m
888 ///\warning Don't forget to put the \ref Vf2ppWizard::run() "run()",
889 ///\ref Vf2ppWizard::count() "count()" or
890 ///the \ref Vf2ppWizard::getPtrToVf2ppObject() "getPtrToVf2ppObject()"
891 ///to the end of the expression.
894 template<class G1, class G2>
895 Vf2ppWizard<Vf2ppWizardBase<G1,G2> > vf2pp(const G1 &g1, const G2 &g2) {
896 return Vf2ppWizard<Vf2ppWizardBase<G1,G2> >(g1,g2);