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>
40 class DfsLeaveOrder : public DfsVisitor<G> {
43 std::vector<typename G::Node> &_order;
45 DfsLeaveOrder(const G &g, std::vector<typename G::Node> &order)
46 : i(countNodes(g)), _g(g), _order(order) {
48 void leave(const typename G::Node &node) {
54 class BfsLeaveOrder : public BfsVisitor<G> {
57 std::vector<typename G::Node> &_order;
59 BfsLeaveOrder(const G &g, std::vector<typename G::Node> &order) { }
60 void process(const typename G::Node &node) {
68 ///%VF2 Plus Plus algorithm class.
70 ///\ingroup graph_isomorphism This class provides an efficient
71 ///implementation of the %VF2 Plus Plus algorithm
72 ///for variants of the (Sub)graph Isomorphism problem.
74 ///There is also a \ref vf2pp() "function-type interface" called
75 ///\ref vf2pp() for the %VF2 Plus Plus algorithm, which is probably
76 ///more convenient in most use cases.
78 ///\tparam G1 The type of the graph to be embedded.
79 ///The default type is \ref ListDigraph.
80 ///\tparam G2 The type of the graph g1 will be embedded into.
81 ///The default type is \ref ListDigraph.
82 ///\tparam M The type of the NodeMap storing the mapping.
83 ///By default, it is G1::NodeMap<G2::Node>
84 ///\tparam M1 The type of the NodeMap storing the integer node labels of G1.
85 ///The labels must be the numbers {0,1,2,..,K-1}, where K is the number of
86 ///different labels. By default, it is G1::NodeMap<int>.
87 ///\tparam M2 The type of the NodeMap storing the integer node labels of G2.
88 ///The labels must be the numbers {0,1,2,..,K-1}, where K is the number of
89 ///different labels. By default, it is G2::NodeMap<int>.
93 template<class G1, class G2, class M, class M1, class M2 >
95 template<class G1=ListDigraph,
97 class M = typename G1::template NodeMap<G2::Node>,
98 class M1 = typename G1::template NodeMap<int>,
99 class M2 = typename G2::template NodeMap<int> >
102 //The graph to be embedded
105 //The graph into which g1 is to be embedded
108 //Current depth in the search tree.
111 //The current mapping. _mapping[v1]=v2 iff v1 has been mapped to v2,
112 //where v1 is a node of G1 and v2 is a node of G2
115 //_order[i] is a node of g1 for which a pair is searched if depth=i
116 std::vector<typename G1::Node> _order;
118 //_conn[v2] = number of covered neighbours of v2
119 typename G2::template NodeMap<int> _conn;
121 //_currEdgeIts[i] is the last used edge iterator in the i-th
122 //depth to find a pair for node _order[i]
123 std::vector<typename G2::IncEdgeIt> _currEdgeIts;
125 //_rNewLabels1[v] is a pair of form
126 //(label; num. of uncov. nodes with such label and no covered neighbours)
127 typename G1::template NodeMap<std::vector<std::pair<int,int> > >
130 //_rInOutLabels1[v] is the number of covered neighbours of v for each label
131 //in form (label,number of such labels)
132 typename G1::template NodeMap<std::vector<std::pair<int,int> > >
135 //_intLabels1[v]==i means that node v has label i in _g1
136 //(i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
139 //_intLabels2[v]==i means that node v has label i in _g2
140 //(i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
146 //lookup tables for manipulating with label class cardinalities
147 //(after use they have to be reset to 0..0)
148 std::vector<int> _labelTmp1,_labelTmp2;
150 MappingType _mapping_type;
152 //indicates whether the mapping or the labels must be deleted in the destructor
153 bool _deallocMappingAfterUse,_deallocLabelsAfterUse;
156 //improved cutting function
157 template<MappingType MT>
158 bool cutByLabels(const typename G1::Node n1,const typename G2::Node n2) {
159 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
160 const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
161 if(_conn[currNode]>0)
162 --_labelTmp1[_intLabels2[currNode]];
163 else if(MT!=SUBGRAPH&&_conn[currNode]==0)
164 --_labelTmp2[_intLabels2[currNode]];
169 for(unsigned int i = 0; i < _rInOutLabels1[n1].size(); ++i)
170 _labelTmp1[_rInOutLabels1[n1][i].first]+=_rInOutLabels1[n1][i].second;
173 for(unsigned int i = 0; i < _rNewLabels1[n1].size(); ++i)
174 _labelTmp2[_rNewLabels1[n1][i].first]+=_rNewLabels1[n1][i].second;
178 for(unsigned int i = 0; i < _rInOutLabels1[n1].size(); ++i)
179 if(_labelTmp1[_rInOutLabels1[n1][i].first]>0) {
184 for(unsigned int i = 0; i < _rNewLabels1[n1].size(); ++i)
185 if(_labelTmp2[_rNewLabels1[n1][i].first]>0) {
191 for(unsigned int i = 0; i < _rInOutLabels1[n1].size(); ++i)
192 if(_labelTmp1[_rInOutLabels1[n1][i].first]>0) {
198 for(unsigned int i = 0; i < _rInOutLabels1[n1].size(); ++i)
199 if(_labelTmp1[_rInOutLabels1[n1][i].first]!=0) {
204 for(unsigned int i = 0; i < _rNewLabels1[n1].size(); ++i)
205 if(_labelTmp2[_rNewLabels1[n1][i].first]!=0) {
213 for(unsigned int i = 0; i < _rInOutLabels1[n1].size(); ++i)
214 _labelTmp1[_rInOutLabels1[n1][i].first]=0;
217 for(unsigned int i = 0; i < _rNewLabels1[n1].size(); ++i)
218 _labelTmp2[_rNewLabels1[n1][i].first]=0;
221 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
222 const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
223 _labelTmp1[_intLabels2[currNode]]=0;
224 if(MT!=SUBGRAPH&&_conn[currNode]==0)
225 _labelTmp2[_intLabels2[currNode]]=0;
232 //try to exclude the matching of n1 and n2
233 template<MappingType MT>
234 bool feas(const typename G1::Node n1,const typename G2::Node n2) {
235 if(_intLabels1[n1]!=_intLabels2[n2])
238 for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
239 const typename G1::Node& currNode=_g1.oppositeNode(n1,e1);
240 if(_mapping[currNode]!=INVALID)
241 --_conn[_mapping[currNode]];
245 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
246 int& connCurrNode = _conn[_g2.oppositeNode(n2,e2)];
249 else if(MT!=SUBGRAPH&&connCurrNode==-1) {
256 for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
257 const typename G2::Node& currNodePair =
258 _mapping[_g1.oppositeNode(n1,e1)];
259 int& connCurrNodePair=_conn[currNodePair];
260 if(currNodePair!=INVALID&&connCurrNodePair!=-1) {
267 if(connCurrNodePair<-1)
275 for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
276 const typename G2::Node currNode=_mapping[_g1.oppositeNode(n1,e1)];
277 if(currNode!=INVALID/*&&_conn[currNode]!=-1*/)
281 return isIso&&cutByLabels<MT>(n1,n2);
285 void addPair(const typename G1::Node n1,const typename G2::Node n2) {
288 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
289 int& currConn = _conn[_g2.oppositeNode(n2,e2)];
295 //removes mapping of n1 to n2
296 void subPair(const typename G1::Node n1,const typename G2::Node n2) {
298 _mapping.set(n1,INVALID);
299 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2){
300 int& currConn = _conn[_g2.oppositeNode(n2,e2)];
303 else if(currConn==-1)
308 void processBFSLevel(typename G1::Node source,unsigned int& orderIndex,
309 typename G1::template NodeMap<int>& dm1,
310 typename G1::template NodeMap<bool>& added) {
311 _order[orderIndex]=source;
314 unsigned int endPosOfLevel=orderIndex,
315 startPosOfLevel=orderIndex,
316 lastAdded=orderIndex;
318 typename G1::template NodeMap<int> currConn(_g1,0);
320 while(orderIndex<=lastAdded){
321 typename G1::Node currNode = _order[orderIndex];
322 for(typename G1::IncEdgeIt e(_g1,currNode); e!=INVALID; ++e) {
323 typename G1::Node n = _g1.oppositeNode(currNode,e);
325 _order[++lastAdded]=n;
329 if(orderIndex>endPosOfLevel){
330 for(unsigned int j = startPosOfLevel; j <= endPosOfLevel; ++j) {
332 for(unsigned int i = j+1; i <= endPosOfLevel; ++i)
333 if(currConn[_order[i]]>currConn[_order[minInd]]||
334 (currConn[_order[i]]==currConn[_order[minInd]]&&
335 (dm1[_order[i]]>dm1[_order[minInd]]||
336 (dm1[_order[i]]==dm1[_order[minInd]]&&
337 _labelTmp1[_intLabels1[_order[minInd]]]>
338 _labelTmp1[_intLabels1[_order[i]]]))))
341 --_labelTmp1[_intLabels1[_order[minInd]]];
342 for(typename G1::IncEdgeIt e(_g1,_order[minInd]); e!=INVALID; ++e)
343 ++currConn[_g1.oppositeNode(_order[minInd],e)];
344 std::swap(_order[j],_order[minInd]);
346 startPosOfLevel=endPosOfLevel+1;
347 endPosOfLevel=lastAdded;
354 //we will find pairs for the nodes of g1 in this order
356 for(typename G2::NodeIt n2(_g2); n2!=INVALID; ++n2)
357 ++_labelTmp1[_intLabels2[n2]];
359 typename G1::template NodeMap<int> dm1(_g1,0);
360 for(typename G1::EdgeIt e(_g1); e!=INVALID; ++e) {
365 typename G1::template NodeMap<bool> added(_g1,0);
366 unsigned int orderIndex=0;
368 for(typename G1::NodeIt n(_g1); n!=INVALID;) {
370 typename G1::Node minNode = n;
371 for(typename G1::NodeIt n1(_g1,minNode); n1!=INVALID; ++n1)
373 (_labelTmp1[_intLabels1[minNode]]>
374 _labelTmp1[_intLabels1[n1]]||(dm1[minNode]<dm1[n1]&&
375 _labelTmp1[_intLabels1[minNode]]==
376 _labelTmp1[_intLabels1[n1]])))
378 processBFSLevel(minNode,orderIndex,dm1,added);
383 for(unsigned int i = 0; i < _labelTmp1.size(); ++i)
388 template<MappingType MT>
391 if(_depth==static_cast<int>(_order.size())) {
392 //all nodes of g1 are mapped to nodes of g2
396 typename G1::Node& nodeOfDepth = _order[_depth];
397 const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth];
398 typename G2::IncEdgeIt &edgeItOfDepth = _currEdgeIts[_depth];
399 //the node of g2 whose neighbours are the candidates for
400 //the pair of _order[_depth]
401 typename G2::Node currPNode;
402 if(edgeItOfDepth==INVALID){
403 typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth);
404 //if _mapping[_order[_depth]]!=INVALID, we don't need fstMatchedE
405 if(pairOfNodeOfDepth==INVALID) {
406 for(; fstMatchedE!=INVALID &&
407 _mapping[_g1.oppositeNode(nodeOfDepth,
408 fstMatchedE)]==INVALID;
409 ++fstMatchedE); //find fstMatchedE, it could be preprocessed
411 if(fstMatchedE==INVALID||pairOfNodeOfDepth!=INVALID) {
412 //We found no covered neighbours, this means that
413 //the graph is not connected (or _depth==0). Each
414 //uncovered (and there are some other properties due
415 //to the spec. problem types) node of g2 is
416 //candidate. We can read the iterator of the last
417 //tried node from the match if it is not the first
418 //try (match[nodeOfDepth]!=INVALID)
419 typename G2::NodeIt n2(_g2);
420 //if it's not the first try
421 if(pairOfNodeOfDepth!=INVALID) {
422 n2=++typename G2::NodeIt(_g2,pairOfNodeOfDepth);
423 subPair(nodeOfDepth,pairOfNodeOfDepth);
425 for(; n2!=INVALID; ++n2)
427 if(_conn[n2]==0&&feas<MT>(nodeOfDepth,n2))
430 else if(_conn[n2]>=0&&feas<MT>(nodeOfDepth,n2))
432 // n2 is the next candidate
434 addPair(nodeOfDepth,n2);
437 else // there are no more candidates
442 currPNode=_mapping[_g1.oppositeNode(nodeOfDepth,
444 edgeItOfDepth=typename G2::IncEdgeIt(_g2,currPNode);
448 currPNode=_g2.oppositeNode(pairOfNodeOfDepth,
450 subPair(nodeOfDepth,pairOfNodeOfDepth);
453 for(; edgeItOfDepth!=INVALID; ++edgeItOfDepth) {
454 const typename G2::Node currNode =
455 _g2.oppositeNode(currPNode, edgeItOfDepth);
456 if(_conn[currNode]>0&&feas<MT>(nodeOfDepth,currNode)) {
457 addPair(nodeOfDepth,currNode);
461 edgeItOfDepth==INVALID?--_depth:++_depth;
466 //calculate the lookup table for cutting the search tree
467 void initRNew1tRInOut1t(){
468 typename G1::template NodeMap<int> tmp(_g1,0);
469 for(unsigned int i=0; i<_order.size(); ++i) {
471 for(typename G1::IncEdgeIt e1(_g1,_order[i]); e1!=INVALID; ++e1) {
472 const typename G1::Node currNode=_g1.oppositeNode(_order[i],e1);
474 ++_labelTmp1[_intLabels1[currNode]];
475 else if(tmp[currNode]==0)
476 ++_labelTmp2[_intLabels1[currNode]];
478 //_labelTmp1[i]=number of neightbours with label i in set rInOut
479 //_labelTmp2[i]=number of neightbours with label i in set rNew
480 for(typename G1::IncEdgeIt e1(_g1,_order[i]); e1!=INVALID; ++e1) {
481 const int& currIntLabel = _intLabels1[_g1.oppositeNode(_order[i],e1)];
482 if(_labelTmp1[currIntLabel]>0) {
483 _rInOutLabels1[_order[i]]
484 .push_back(std::make_pair(currIntLabel,
485 _labelTmp1[currIntLabel]));
486 _labelTmp1[currIntLabel]=0;
488 else if(_labelTmp2[currIntLabel]>0) {
489 _rNewLabels1[_order[i]].
490 push_back(std::make_pair(currIntLabel,_labelTmp2[currIntLabel]));
491 _labelTmp2[currIntLabel]=0;
495 for(typename G1::IncEdgeIt e1(_g1,_order[i]); e1!=INVALID; ++e1) {
496 int& tmpCurrNode=tmp[_g1.oppositeNode(_order[i],e1)];
503 int getMaxLabel() const{
505 for(typename G1::NodeIt n1(_g1); n1!=INVALID; ++n1) {
506 const int& currIntLabel = _intLabels1[n1];
510 for(typename G2::NodeIt n2(_g2); n2!=INVALID; ++n2) {
511 const int& currIntLabel = _intLabels2[n2];
522 ///\param g1 The graph to be embedded.
523 ///\param g2 The graph \e g1 will be embedded into.
524 ///\param m The type of the NodeMap storing the mapping.
525 ///By default, it is G1::NodeMap<G2::Node>
526 ///\param intLabel1 The NodeMap storing the integer node labels of G1.
527 ///The labels must be the numbers {0,1,2,..,K-1}, where K is the number of
529 ///\param intLabel1 The NodeMap storing the integer node labels of G2.
530 ///The labels must be the numbers {0,1,2,..,K-1}, where K is the number of
532 Vf2pp(const G1 &g1, const G2 &g2,M &m, M1 &intLabels1, M2 &intLabels2) :
533 _g1(g1), _g2(g2), _depth(0), _mapping(m), _order(countNodes(g1),INVALID),
534 _conn(g2,0), _currEdgeIts(countNodes(g1),INVALID), _rNewLabels1(_g1),
535 _rInOutLabels1(_g1), _intLabels1(intLabels1) ,_intLabels2(intLabels2),
536 _maxLabel(getMaxLabel()), _labelTmp1(_maxLabel+1),_labelTmp2(_maxLabel+1),
537 _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0),
538 _deallocLabelsAfterUse(0)
541 initRNew1tRInOut1t();
544 for(typename G1::NodeIt n(g1);n!=INVALID;++n)
554 if(_deallocMappingAfterUse)
556 if(_deallocLabelsAfterUse) {
562 ///Returns the current mapping type.
564 ///Returns the current mapping type.
566 MappingType mappingType() const
568 return _mapping_type;
571 ///Sets the mapping type
573 ///Sets the mapping type.
575 ///The mapping type is set to \ref SUBGRAPH by default.
577 ///\sa See \ref MappingType for the possible values.
578 void mappingType(MappingType m_type)
580 _mapping_type = m_type;
585 ///This method finds a mapping from g1 into g2 according to the mapping
586 ///type set by \ref mappingType(MappingType) "mappingType()".
588 ///By subsequent calls, it returns all possible mappings one-by-one.
590 ///\retval true if a mapping is found.
591 ///\retval false if there is no (more) mapping.
594 switch(_mapping_type)
597 return extMatch<SUBGRAPH>();
599 return extMatch<INDUCED>();
601 return extMatch<ISOMORPH>();
608 template<typename G1, typename G2>
609 class Vf2ppWizardBase {
617 MappingType _mapping_type;
619 typedef typename G1::template NodeMap<typename G2::Node> Mapping;
622 void createMapping() {
623 _mapping = new Mapping(_g1);
626 bool _local_nodeLabels;
627 typedef typename G1::template NodeMap<int> NodeLabels1;
628 typedef typename G2::template NodeMap<int> NodeLabels2;
629 void *_nodeLabels1, *_nodeLabels2;
630 void createNodeLabels() {
631 _nodeLabels1 = new NodeLabels1(_g1,0);
632 _nodeLabels2 = new NodeLabels2(_g2,0);
635 Vf2ppWizardBase(const G1 &g1,const G2 &g2)
636 : _g1(g1), _g2(g2), _mapping_type(SUBGRAPH),
637 _local_mapping(1), _local_nodeLabels(1) { }
641 /// \brief Auxiliary class for the function-type interface of %VF2
642 /// Plus Plus algorithm.
644 /// This auxiliary class implements the named parameters of
645 /// \ref vf2pp() "function-type interface" of \ref Vf2pp algorithm.
647 /// \warning This class is not to be used directly.
649 /// \tparam TR The traits class that defines various types used by the
651 template<typename TR>
652 class Vf2ppWizard : public TR {
654 typedef typename TR::Graph1 Graph1;
655 typedef typename TR::Graph2 Graph2;
656 typedef typename TR::Mapping Mapping;
657 typedef typename TR::NodeLabels1 NodeLabels1;
658 typedef typename TR::NodeLabels2 NodeLabels2;
662 using TR::_mapping_type;
664 using TR::_nodeLabels1;
665 using TR::_nodeLabels2;
669 Vf2ppWizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {}
672 Vf2ppWizard(const Base &b) : Base(b) {}
676 struct SetMappingBase : public Base {
678 SetMappingBase(const Base &b) : Base(b) {}
681 ///\brief \ref named-templ-param "Named parameter" for setting
684 ///\ref named-templ-param "Named parameter" function for setting
685 ///the map that stores the found embedding.
687 Vf2ppWizard< SetMappingBase<T> > mapping(const T &t) {
688 Base::_mapping=reinterpret_cast<void*>(const_cast<T*>(&t));
689 Base::_local_mapping = 0;
690 return Vf2ppWizard<SetMappingBase<T> >(*this);
693 template<typename NL1, typename NL2>
694 struct SetNodeLabelsBase : public Base {
695 typedef NL1 NodeLabels1;
696 typedef NL2 NodeLabels2;
697 SetNodeLabelsBase(const Base &b) : Base(b) { }
700 ///\brief \ref named-templ-param "Named parameter" for setting the
703 ///\ref named-templ-param "Named parameter" function for setting
706 ///\param nodeLabels1 A \ref concepts::ReadMap "readable node map"
707 ///of g1 with integer values. In case of K different labels, the labels
708 ///must be the numbers {0,1,..,K-1}.
709 ///\param nodeLabels2 A \ref concepts::ReadMap "readable node map"
710 ///of g2 with integer values. In case of K different labels, the labels
711 ///must be the numbers {0,1,..,K-1}.
712 template<typename NL1, typename NL2>
713 Vf2ppWizard< SetNodeLabelsBase<NL1,NL2> >
714 nodeLabels(const NL1 &nodeLabels1, const NL2 &nodeLabels2) {
715 Base::_local_nodeLabels = 0;
717 reinterpret_cast<void*>(const_cast<NL1*>(&nodeLabels1));
719 reinterpret_cast<void*>(const_cast<NL2*>(&nodeLabels2));
720 return Vf2ppWizard<SetNodeLabelsBase<NL1,NL2> >
721 (SetNodeLabelsBase<NL1,NL2>(*this));
725 ///\brief \ref named-templ-param "Named parameter" for setting
728 ///\ref named-templ-param "Named parameter" for setting
731 ///The mapping type is set to \ref SUBGRAPH by default.
733 ///\sa See \ref MappingType for the possible values.
734 Vf2ppWizard<Base> &mappingType(MappingType m_type) {
735 _mapping_type = m_type;
739 ///\brief \ref named-templ-param "Named parameter" for setting
740 ///the mapping type to \ref INDUCED.
742 ///\ref named-templ-param "Named parameter" for setting
743 ///the mapping type to \ref INDUCED.
744 Vf2ppWizard<Base> &induced() {
745 _mapping_type = INDUCED;
749 ///\brief \ref named-templ-param "Named parameter" for setting
750 ///the mapping type to \ref ISOMORPH.
752 ///\ref named-templ-param "Named parameter" for setting
753 ///the mapping type to \ref ISOMORPH.
754 Vf2ppWizard<Base> &iso() {
755 _mapping_type = ISOMORPH;
759 ///Runs the %VF2 Plus Plus algorithm.
761 ///This method runs the VF2 Plus Plus algorithm.
763 ///\retval true if a mapping is found.
764 ///\retval false if there is no mapping.
766 if(Base::_local_mapping)
767 Base::createMapping();
768 if(Base::_local_nodeLabels)
769 Base::createNodeLabels();
771 Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2 >
772 alg(_g1, _g2, *reinterpret_cast<Mapping*>(_mapping),
773 *reinterpret_cast<NodeLabels1*>(_nodeLabels1),
774 *reinterpret_cast<NodeLabels2*>(_nodeLabels2));
776 alg.mappingType(_mapping_type);
778 const bool ret = alg.find();
780 if(Base::_local_nodeLabels) {
781 delete reinterpret_cast<NodeLabels1*>(_nodeLabels1);
782 delete reinterpret_cast<NodeLabels2*>(_nodeLabels2);
784 if(Base::_local_mapping)
785 delete reinterpret_cast<Mapping*>(_mapping);
790 ///Get a pointer to the generated Vf2pp object.
792 ///Gives a pointer to the generated Vf2pp object.
794 ///\return Pointer to the generated Vf2pp object.
795 ///\warning Don't forget to delete the referred Vf2pp object after use.
796 Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2 >*
797 getPtrToVf2ppObject(){
798 if(Base::_local_mapping)
799 Base::createMapping();
800 if(Base::_local_nodeLabels)
801 Base::createNodeLabels();
803 Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2 >* ptr =
804 new Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2>
805 (_g1, _g2, *reinterpret_cast<Mapping*>(_mapping),
806 *reinterpret_cast<NodeLabels1*>(_nodeLabels1),
807 *reinterpret_cast<NodeLabels2*>(_nodeLabels2));
808 ptr->mappingType(_mapping_type);
809 if(Base::_local_mapping)
810 ptr->_deallocMappingAfterUse=true;
811 if(Base::_local_nodeLabels)
812 ptr->_deallocLabelMapsAfterUse=true;
817 ///Counts the number of mappings.
819 ///This method counts the number of mappings.
821 /// \return The number of mappings.
823 if(Base::_local_mapping)
824 Base::createMapping();
825 if(Base::_local_nodeLabels)
826 Base::createNodeLabels();
828 Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2>
829 alg(_g1, _g2, *reinterpret_cast<Mapping*>(_mapping),
830 *reinterpret_cast<NodeLabels1*>(_nodeLabels1),
831 *reinterpret_cast<NodeLabels2*>(_nodeLabels2));
833 alg.mappingType(_mapping_type);
839 if(Base::_local_nodeLabels) {
840 delete reinterpret_cast<NodeLabels1*>(_nodeLabels1);
841 delete reinterpret_cast<NodeLabels2*>(_nodeLabels2);
843 if(Base::_local_mapping)
844 delete reinterpret_cast<Mapping*>(_mapping);
851 ///Function-type interface for VF2 Plus Plus algorithm.
853 /// \ingroup graph_isomorphism
854 ///Function-type interface for VF2 Plus Plus algorithm.
856 ///This function has several \ref named-func-param "named parameters"
857 ///declared as the members of class \ref Vf2ppWizard.
858 ///The following examples show how to use these parameters.
860 /// ListGraph::NodeMap<ListGraph::Node> m(g);
861 /// // Find an embedding of graph g1 into graph g2
862 /// vf2pp(g1,g2).mapping(m).run();
864 /// // Check whether graphs g1 and g2 are isomorphic
865 /// bool is_iso = vf2pp(g1,g2).iso().run();
867 /// // Count the number of isomorphisms
868 /// int num_isos = vf2pp(g1,g2).iso().count();
870 /// // Iterate through all the induced subgraph mappings
871 /// // of graph g1 into g2 using the labels c1 and c2
872 /// auto* myVf2pp = vf2pp(g1,g2).mapping(m).nodeLabels(c1,c2)
873 /// .induced().getPtrToVf2Object();
874 /// while(myVf2pp->find()){
875 /// //process the current mapping m
879 ///\warning Don't forget to put the \ref Vf2ppWizard::run() "run()",
880 ///\ref Vf2ppWizard::count() "count()" or
881 ///the \ref Vf2ppWizard::getPtrToVf2ppObject() "getPtrToVf2ppObject()"
882 ///to the end of the expression.
885 template<class G1, class G2>
886 Vf2ppWizard<Vf2ppWizardBase<G1,G2> > vf2pp(const G1 &g1, const G2 &g2) {
887 return Vf2ppWizard<Vf2ppWizardBase<G1,G2> >(g1,g2);