lemon/vf2.h
author Peter Madarasi <madarasip@caesar.elte.hu>
Tue, 19 Sep 2017 14:08:20 +0200
changeset 1405 3feba0ea1bda
parent 1370 f51c01a1b88e
child 1407 76349d8212d3
permissions -rw-r--r--
Vf2 improvements and Vf2pp implementation (#597)
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2015-2017
     6  * EMAXA Kutato-fejleszto Kft. (EMAXA Research Ltd.)
     7  *
     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.
    11  *
    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
    14  * purpose.
    15  *
    16  */
    17 
    18 #ifndef LEMON_VF2_H
    19 #define LEMON_VF2_H
    20 
    21 ///\ingroup graph_properties
    22 ///\file
    23 ///\brief VF2 algorithm \cite cordella2004sub.
    24 
    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>
    30 
    31 #include <vector>
    32 
    33 namespace lemon {
    34   namespace bits {
    35     namespace vf2 {
    36 
    37       class AlwaysEq {
    38       public:
    39         template<class T1, class T2>
    40         bool operator()(T1&, T2&) const {
    41           return true;
    42         }
    43       };
    44 
    45       template<class M1, class M2>
    46       class MapEq{
    47         const M1 &_m1;
    48         const M2 &_m2;
    49       public:
    50         MapEq(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) { }
    51         bool operator()(typename M1::Key k1, typename M2::Key k2) const {
    52           return _m1[k1] == _m2[k2];
    53         }
    54       };
    55 
    56 
    57 
    58       template <class G>
    59       class DfsLeaveOrder : public DfsVisitor<G> {
    60         const G &_g;
    61         std::vector<typename G::Node> &_order;
    62         int i;
    63       public:
    64         DfsLeaveOrder(const G &g, std::vector<typename G::Node> &order)
    65           : i(countNodes(g)), _g(g), _order(order) { }
    66         void leave(const typename G::Node &node) {
    67           _order[--i]=node;
    68         }
    69       };
    70 
    71       template <class G>
    72       class BfsLeaveOrder : public BfsVisitor<G> {
    73         int i;
    74         const G &_g;
    75         std::vector<typename G::Node> &_order;
    76       public:
    77         BfsLeaveOrder(const G &g, std::vector<typename G::Node> &order)
    78           : i(0), _g(g), _order(order){
    79         }
    80         void process(const typename G::Node &node) {
    81           _order[i++]=node;
    82         }
    83       };
    84     }
    85   }
    86 
    87 
    88   ///%VF2 algorithm class.
    89 
    90   ///\ingroup graph_isomorphism This class provides an efficient
    91   ///implementation of the %VF2 algorithm \cite cordella2004sub
    92   ///for variants of the (Sub)graph Isomorphism problem.
    93   ///
    94   ///There is also a \ref vf2() "function-type interface" called \ref vf2()
    95   ///for the %VF2 algorithm, which is probably more convenient in most
    96   ///use-cases.
    97   ///
    98   ///\tparam G1 The type of the graph to be embedded.
    99   ///The default type is \ref ListDigraph.
   100   ///\tparam G2 The type of the graph g1 will be embedded into.
   101   ///The default type is \ref ListDigraph.
   102   ///\tparam M The type of the NodeMap storing the mapping.
   103   ///By default, it is G1::NodeMap<G2::Node>
   104   ///\tparam NEQ A bool-valued binary functor determinining whether a node is
   105   ///mappable to another. By default it is an always true operator.
   106   ///
   107   ///\sa vf2()
   108 #ifdef DOXYGEN
   109   template<class G1, class G2, class M, class NEQ >
   110 #else
   111   template<class G1=ListDigraph,
   112            class G2=ListDigraph,
   113            class M = typename G1::template NodeMap<G2::Node>,
   114            class NEQ = bits::vf2::AlwaysEq >
   115 #endif
   116   class Vf2 {
   117     //Current depth in the DFS tree.
   118     int _depth;
   119     //Functor with bool operator()(G1::Node,G2::Node), which returns 1
   120     //ifff the two nodes are equivalent.
   121     NEQ _nEq;
   122 
   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.
   126     M &_mapping;
   127     //order[i] is the node of g1, for which we search a pair if depth=i
   128     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     std::vector<typename G2::IncEdgeIt> currEdgeIts;
   132     //The small graph.
   133     const G1 &_g1;
   134     //The large graph.
   135     const G2 &_g2;
   136     //lookup tables for cutting the searchtree
   137     typename G1::template NodeMap<int> rNew1t,rInOut1t;
   138 
   139     MappingType _mapping_type;
   140 
   141     bool _deallocMappingAfterUse;
   142 
   143     //cut the search tree
   144     template<MappingType MT>
   145     bool cut(const typename G1::Node n1,const typename G2::Node n2) const {
   146       int rNew2=0,rInOut2=0;
   147       for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
   148         const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
   149         if(_conn[currNode]>0)
   150           ++rInOut2;
   151         else if(MT!=SUBGRAPH&&_conn[currNode]==0)
   152           ++rNew2;
   153       }
   154       switch(MT) {
   155       case INDUCED:
   156         return rInOut1t[n1]<=rInOut2&&rNew1t[n1]<=rNew2;
   157       case SUBGRAPH:
   158         return rInOut1t[n1]<=rInOut2;
   159       case ISOMORPH:
   160         return rInOut1t[n1]==rInOut2&&rNew1t[n1]==rNew2;
   161       default:
   162         return false;
   163       }
   164     }
   165 
   166     template<MappingType MT>
   167     bool feas(const typename G1::Node n1,const typename G2::Node n2) {
   168       if(!_nEq(n1,n2))
   169         return 0;
   170 
   171       for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
   172         const typename G1::Node& currNode=_g1.oppositeNode(n1,e1);
   173         if(_mapping[currNode]!=INVALID)
   174           --_conn[_mapping[currNode]];
   175       }
   176       bool isIso=1;
   177       for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
   178         int& connCurrNode = _conn[_g2.oppositeNode(n2,e2)];
   179         if(connCurrNode<-1)
   180           ++connCurrNode;
   181         else if(MT!=SUBGRAPH&&connCurrNode==-1) {
   182           isIso=0;
   183           break;
   184         }
   185       }
   186 
   187       for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
   188         const typename G2::Node& currNodePair=_mapping[_g1.oppositeNode(n1,e1)];
   189         int& connCurrNodePair=_conn[currNodePair];
   190         if(currNodePair!=INVALID&&connCurrNodePair!=-1) {
   191           switch(MT) {
   192           case INDUCED:
   193           case ISOMORPH:
   194             isIso=0;
   195             break;
   196           case SUBGRAPH:
   197             if(connCurrNodePair<-1)
   198               isIso=0;
   199             break;
   200           }
   201           connCurrNodePair=-1;
   202         }
   203       }
   204       return isIso&&cut<MT>(n1,n2);
   205     }
   206 
   207     void addPair(const typename G1::Node n1,const typename G2::Node n2) {
   208       _conn[n2]=-1;
   209       _mapping.set(n1,n2);
   210       for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
   211         int& currConn = _conn[_g2.oppositeNode(n2,e2)];
   212         if(currConn!=-1)
   213           ++currConn;
   214       }
   215     }
   216 
   217     void subPair(const typename G1::Node n1,const typename G2::Node n2) {
   218       _conn[n2]=0;
   219       _mapping.set(n1,INVALID);
   220       for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
   221         int& currConn = _conn[_g2.oppositeNode(n2,e2)];
   222         if(currConn>0)
   223           --currConn;
   224         else if(currConn==-1)
   225           ++_conn[n2];
   226       }
   227     }
   228 
   229     void setOrder() {
   230       // we will find pairs for the nodes of g1 in this order
   231 
   232       // bits::vf2::DfsLeaveOrder<G1> v(_g1,order);
   233       //   DfsVisit<G1,bits::vf2::DfsLeaveOrder<G1> >dfs(_g1, v);
   234       //   dfs.run();
   235 
   236       //it is more efficient in practice than DFS
   237       bits::vf2::BfsLeaveOrder<G1> v(_g1,order);
   238       BfsVisit<G1,bits::vf2::BfsLeaveOrder<G1> >bfs(_g1, v);
   239       bfs.run();
   240     }
   241 
   242     template<MappingType MT>
   243     bool extMatch() {
   244       while(_depth>=0) {
   245         //there are not nodes in g1, which has not pair in g2.
   246         if(_depth==static_cast<int>(order.size())) {
   247           --_depth;
   248           return true;
   249         }
   250         typename G1::Node& nodeOfDepth = order[_depth];
   251         const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth];
   252         typename G2::IncEdgeIt &edgeItOfDepth = currEdgeIts[_depth];
   253         //the node of g2, which neighbours are the candidates for
   254         //the pair of nodeOfDepth
   255         typename G2::Node currPNode;
   256         if(edgeItOfDepth==INVALID) {
   257           typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth);
   258           //if pairOfNodeOfDepth!=INVALID, we dont use
   259           //fstMatchedE
   260           if(pairOfNodeOfDepth==INVALID)
   261             for(; fstMatchedE!=INVALID &&
   262                   _mapping[_g1.oppositeNode(nodeOfDepth,
   263                                             fstMatchedE)]==INVALID;
   264                 ++fstMatchedE) ; //find fstMatchedE
   265           if(fstMatchedE==INVALID||pairOfNodeOfDepth!=INVALID) {
   266             //We found no covered neighbours, this means
   267             //the graph is not connected(or _depth==0).  Each
   268             //uncovered(and there are some other properties due
   269             //to the spec. problem types) node of g2 is
   270             //candidate.  We can read the iterator of the last
   271             //tried node from the match if it is not the first
   272             //try(match[nodeOfDepth]!=INVALID)
   273             typename G2::NodeIt n2(_g2);
   274             //if it's not the first try
   275             if(pairOfNodeOfDepth!=INVALID) {
   276               n2=++typename G2::NodeIt(_g2,pairOfNodeOfDepth);
   277               subPair(nodeOfDepth,pairOfNodeOfDepth);
   278             }
   279             for(; n2!=INVALID; ++n2)
   280               if(MT!=SUBGRAPH) {
   281                 if(_conn[n2]==0&&feas<MT>(nodeOfDepth,n2))
   282                   break;
   283               }
   284               else if(_conn[n2]>=0&&feas<MT>(nodeOfDepth,n2))
   285                 break;
   286             // n2 is the next candidate
   287             if(n2!=INVALID){
   288               addPair(nodeOfDepth,n2);
   289               ++_depth;
   290             }
   291             else // there are no more candidates
   292               --_depth;
   293             continue;
   294           }
   295           else {
   296             currPNode=_mapping[_g1.oppositeNode(nodeOfDepth,
   297                                                 fstMatchedE)];
   298             edgeItOfDepth=typename G2::IncEdgeIt(_g2,currPNode);
   299           }
   300         }
   301         else {
   302           currPNode=_g2.oppositeNode(pairOfNodeOfDepth,
   303                                      edgeItOfDepth);
   304           subPair(nodeOfDepth,pairOfNodeOfDepth);
   305           ++edgeItOfDepth;
   306         }
   307         for(; edgeItOfDepth!=INVALID; ++edgeItOfDepth) {
   308           const typename G2::Node currNode =
   309             _g2.oppositeNode(currPNode, edgeItOfDepth);
   310           if(_conn[currNode]>0&&feas<MT>(nodeOfDepth,currNode)) {
   311             addPair(nodeOfDepth,currNode);
   312             break;
   313           }
   314         }
   315         edgeItOfDepth==INVALID?--_depth:++_depth;
   316       }
   317       return false;
   318     }
   319 
   320     //calc. the lookup table for cut the searchtree
   321     void setRNew1tRInOut1t() {
   322       typename G1::template NodeMap<int> tmp(_g1,0);
   323       for(unsigned int i=0; i<order.size(); ++i) {
   324         const typename G1::Node& orderI = order[i];
   325         tmp[orderI]=-1;
   326         for(typename G1::IncEdgeIt e1(_g1,orderI); e1!=INVALID; ++e1) {
   327           const typename G1::Node currNode=_g1.oppositeNode(orderI,e1);
   328           if(tmp[currNode]>0)
   329             ++rInOut1t[orderI];
   330           else if(tmp[currNode]==0)
   331             ++rNew1t[orderI];
   332         }
   333         for(typename G1::IncEdgeIt e1(_g1,orderI); e1!=INVALID; ++e1) {
   334           const typename G1::Node currNode=_g1.oppositeNode(orderI,e1);
   335           if(tmp[currNode]!=-1)
   336             ++tmp[currNode];
   337         }
   338       }
   339     }
   340   public:
   341     ///Constructor
   342 
   343     ///Constructor
   344 
   345     ///\param g1 The graph to be embedded into \e g2.
   346     ///\param g2 The graph \e g1 will be embedded into.
   347     ///\param m \ref concepts::ReadWriteMap "read-write" NodeMap
   348     ///storing the found mapping.
   349     ///\param neq A bool-valued binary functor determining whether a node is
   350     ///mappable to another. By default it is an always true operator.
   351     Vf2(const G1 &g1, const G2 &g2, M &m, const NEQ &neq = NEQ() ) :
   352       _nEq(neq), _conn(g2,0), _mapping(m), order(countNodes(g1)),
   353       currEdgeIts(countNodes(g1),INVALID), _g1(g1), _g2(g2), rNew1t(g1,0),
   354       rInOut1t(g1,0), _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0) {
   355       _depth=0;
   356       setOrder();
   357       setRNew1tRInOut1t();
   358       for(typename G1::NodeIt n(g1);n!=INVALID;++n)
   359         m[n]=INVALID;
   360     }
   361 
   362     ///Destructor
   363 
   364     ///Destructor.
   365     ///
   366 
   367     ~Vf2(){
   368       if(_deallocMappingAfterUse)
   369         delete &_mapping;
   370     }
   371 
   372     ///Returns the current mapping type
   373 
   374     ///Returns the current mapping type
   375     ///
   376     MappingType mappingType() const {
   377       return _mapping_type;
   378     }
   379     ///Sets mapping type
   380 
   381     ///Sets mapping type.
   382     ///
   383     ///The mapping type is set to \ref SUBGRAPH by default.
   384     ///
   385     ///\sa See \ref MappingType for the possible values.
   386     void mappingType(MappingType m_type) {
   387       _mapping_type = m_type;
   388     }
   389 
   390     ///Finds a mapping
   391 
   392     ///It finds a mapping from g1 into g2 according to the mapping
   393     ///type set by \ref mappingType(MappingType) "mappingType()".
   394     ///
   395     ///By subsequent calls, it returns all possible mappings one-by-one.
   396     ///
   397     ///\retval true if a mapping is found.
   398     ///\retval false if there is no (more) mapping.
   399     bool find() {
   400       switch(_mapping_type) {
   401       case SUBGRAPH:
   402         return extMatch<SUBGRAPH>();
   403       case INDUCED:
   404         return extMatch<INDUCED>();
   405       case ISOMORPH:
   406         return extMatch<ISOMORPH>();
   407       default:
   408         return false;
   409       }
   410     }
   411   };
   412 
   413   template<class G1, class G2>
   414   class Vf2WizardBase {
   415   protected:
   416     typedef G1 Graph1;
   417     typedef G2 Graph2;
   418 
   419     const G1 &_g1;
   420     const G2 &_g2;
   421 
   422     MappingType _mapping_type;
   423 
   424     typedef typename G1::template NodeMap<typename G2::Node> Mapping;
   425     bool _local_mapping;
   426     void *_mapping;
   427     void createMapping() {
   428       _mapping = new Mapping(_g1);
   429     }
   430 
   431     void *myVf2; //used in Vf2Wizard::find
   432 
   433 
   434     typedef bits::vf2::AlwaysEq NodeEq;
   435     NodeEq _node_eq;
   436 
   437     Vf2WizardBase(const G1 &g1,const G2 &g2)
   438       : _g1(g1), _g2(g2), _mapping_type(SUBGRAPH), _local_mapping(true) { }
   439   };
   440 
   441 
   442   /// Auxiliary class for the function-type interface of %VF2 algorithm.
   443 
   444   /// This auxiliary class implements the named parameters of
   445   /// \ref vf2() "function-type interface" of \ref Vf2 algorithm.
   446   ///
   447   /// \warning This class should only be used through the function \ref vf2().
   448   ///
   449   /// \tparam TR The traits class that defines various types used by the
   450   /// algorithm.
   451   template<class TR>
   452   class Vf2Wizard : public TR {
   453     typedef TR Base;
   454     typedef typename TR::Graph1 Graph1;
   455     typedef typename TR::Graph2 Graph2;
   456 
   457     typedef typename TR::Mapping Mapping;
   458     typedef typename TR::NodeEq NodeEq;
   459 
   460     using TR::_g1;
   461     using TR::_g2;
   462     using TR::_mapping_type;
   463     using TR::_mapping;
   464     using TR::_node_eq;
   465 
   466   public:
   467     ///Constructor
   468     Vf2Wizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {
   469     }
   470 
   471     ///Copy constructor
   472     Vf2Wizard(const Base &b) : Base(b) { }
   473 
   474     ///Copy constructor
   475     Vf2Wizard(const Vf2Wizard &b) : Base(b) {}
   476 
   477 
   478     template<class T>
   479     struct SetMappingBase : public Base{
   480       typedef T Mapping;
   481       SetMappingBase(const Base &b) : Base(b) {}
   482     };
   483 
   484     ///\brief \ref named-templ-param "Named parameter" for setting
   485     ///the mapping.
   486     ///
   487     ///\ref named-templ-param "Named parameter" function for setting
   488     ///the map that stores the found embedding.
   489     template<class T>
   490     Vf2Wizard< SetMappingBase<T> > mapping(const T &t) {
   491       Base::_mapping=reinterpret_cast<void*>(const_cast<T*>(&t));
   492       Base::_local_mapping = false;
   493       return Vf2Wizard<SetMappingBase<T> >(*this);
   494     }
   495 
   496     template<class NE>
   497     struct SetNodeEqBase : public Base {
   498       typedef NE NodeEq;
   499       NodeEq _node_eq;
   500       SetNodeEqBase(const Base &b, const NE &node_eq)
   501         : Base(b), _node_eq(node_eq){
   502       }
   503     };
   504 
   505     ///\brief \ref named-templ-param "Named parameter" for setting
   506     ///the node equivalence relation.
   507     ///
   508     ///\ref named-templ-param "Named parameter" function for setting
   509     ///the equivalence relation between the nodes.
   510     ///
   511     ///\param node_eq A bool-valued binary functor determinining
   512     ///whether a node is mappable to another. By default it is an
   513     ///always true operator.
   514     template<class T>
   515     Vf2Wizard< SetNodeEqBase<T> > nodeEq(const T &node_eq) {
   516       return Vf2Wizard<SetNodeEqBase<T> >(SetNodeEqBase<T>(*this,node_eq));
   517     }
   518 
   519     ///\brief \ref named-templ-param "Named parameter" for setting
   520     ///the node labels.
   521     ///
   522     ///\ref named-templ-param "Named parameter" function for setting
   523     ///the node labels defining equivalence relation between them.
   524     ///
   525     ///\param m1 An arbitrary \ref concepts::ReadMap "readable node map"
   526     ///of g1.
   527     ///\param m2 An arbitrary \ref concepts::ReadMap "readable node map"
   528     ///of g2.
   529     ///
   530     ///The value type of these maps must be equal comparable.
   531     template<class M1, class M2>
   532     Vf2Wizard< SetNodeEqBase<bits::vf2::MapEq<M1,M2> > >
   533     nodeLabels(const M1 &m1,const M2 &m2){
   534       return nodeEq(bits::vf2::MapEq<M1,M2>(m1,m2));
   535     }
   536 
   537     ///\brief \ref named-templ-param "Named parameter" for setting
   538     ///the mapping type.
   539     ///
   540     ///\ref named-templ-param "Named parameter" for setting
   541     ///the mapping type.
   542     ///
   543     ///The mapping type is set to \ref SUBGRAPH by default.
   544     ///
   545     ///\sa See \ref MappingType for the possible values.
   546     Vf2Wizard<Base> &mappingType(MappingType m_type) {
   547       _mapping_type = m_type;
   548       return *this;
   549     }
   550 
   551     ///\brief \ref named-templ-param "Named parameter" for setting
   552     ///the mapping type to \ref INDUCED.
   553     ///
   554     ///\ref named-templ-param "Named parameter" for setting
   555     ///the mapping type to \ref INDUCED.
   556     Vf2Wizard<Base> &induced() {
   557       _mapping_type = INDUCED;
   558       return *this;
   559     }
   560 
   561     ///\brief \ref named-templ-param "Named parameter" for setting
   562     ///the mapping type to \ref ISOMORPH.
   563     ///
   564     ///\ref named-templ-param "Named parameter" for setting
   565     ///the mapping type to \ref ISOMORPH.
   566     Vf2Wizard<Base> &iso() {
   567       _mapping_type = ISOMORPH;
   568       return *this;
   569     }
   570 
   571 
   572     ///Runs VF2 algorithm.
   573 
   574     ///This method runs VF2 algorithm.
   575     ///
   576     ///\retval true if a mapping is found.
   577     ///\retval false if there is no mapping.
   578     bool run(){
   579       if(Base::_local_mapping)
   580         Base::createMapping();
   581 
   582       Vf2<Graph1, Graph2, Mapping, NodeEq >
   583         alg(_g1, _g2, *reinterpret_cast<Mapping*>(_mapping), _node_eq);
   584 
   585       alg.mappingType(_mapping_type);
   586 
   587       bool ret = alg.find();
   588 
   589       if(Base::_local_mapping)
   590         delete reinterpret_cast<Mapping*>(_mapping);
   591 
   592       return ret;
   593     }
   594 
   595     ///Get a pointer to the generated Vf2 object.
   596 
   597     ///Gives a pointer to the generated Vf2 object.
   598     ///
   599     ///\return Pointer to the generated Vf2 object.
   600     ///\warning Don't forget to delete the referred Vf2 object after use.
   601     Vf2<Graph1, Graph2, Mapping, NodeEq >* getPtrToVf2Object() {
   602       if(Base::_local_mapping)
   603         Base::createMapping();
   604       Vf2<Graph1, Graph2, Mapping, NodeEq >* ptr =
   605         new Vf2<Graph1, Graph2, Mapping, NodeEq>
   606         (_g1, _g2, *reinterpret_cast<Mapping*>(_mapping), _node_eq);
   607       ptr->mappingType(_mapping_type);
   608       if(Base::_local_mapping)
   609         ptr->_deallocMappingAfterUse = true;
   610       return ptr;
   611     }
   612 
   613     ///Counts the number of mappings.
   614 
   615     ///This method counts the number of mappings.
   616     ///
   617     /// \return The number of mappings.
   618     int count() {
   619       if(Base::_local_mapping)
   620         Base::createMapping();
   621 
   622       Vf2<Graph1, Graph2, Mapping, NodeEq>
   623         alg(_g1, _g2, *reinterpret_cast<Mapping*>(_mapping), _node_eq);
   624       if(Base::_local_mapping)
   625         alg._deallocMappingAfterUse = true;
   626       alg.mappingType(_mapping_type);
   627 
   628       int ret = 0;
   629       while(alg.find())
   630         ++ret;
   631 
   632       return ret;
   633     }
   634   };
   635 
   636   ///Function-type interface for VF2 algorithm.
   637 
   638   /// \ingroup graph_isomorphism
   639   ///Function-type interface for VF2 algorithm \cite cordella2004sub.
   640   ///
   641   ///This function has several \ref named-func-param "named parameters"
   642   ///declared as the members of class \ref Vf2Wizard.
   643   ///The following examples show how to use these parameters.
   644   ///\code
   645   ///  // Find an embedding of graph g1 into graph g2
   646   ///  ListGraph::NodeMap<ListGraph::Node> m(g);
   647   ///  vf2(g1,g2).mapping(m).run();
   648   ///
   649   ///  // Check whether graphs g1 and g2 are isomorphic
   650   ///  bool is_iso = vf2(g1,g2).iso().run();
   651   ///
   652   ///  // Count the number of isomorphisms
   653   ///  int num_isos = vf2(g1,g2).iso().count();
   654   ///
   655   ///  // Iterate through all the induced subgraph mappings of graph g1 into g2
   656   ///  auto* myVf2 = vf2(g1,g2).mapping(m).nodeLabels(c1,c2)
   657   ///  .induced().getPtrToVf2Object();
   658   ///  while(myVf2->find()){
   659   ///    //process the current mapping m
   660   ///  }
   661   ///  delete myVf22;
   662   ///\endcode
   663   ///\warning Don't forget to put the \ref Vf2Wizard::run() "run()",
   664   ///\ref Vf2Wizard::count() "count()" or
   665   ///the \ref Vf2Wizard::getPtrToVf2Object() "getPtrToVf2Object()"
   666   ///to the end of the expression.
   667   ///\sa Vf2Wizard
   668   ///\sa Vf2
   669   template<class G1, class G2>
   670   Vf2Wizard<Vf2WizardBase<G1,G2> > vf2(const G1 &g1, const G2 &g2) {
   671     return Vf2Wizard<Vf2WizardBase<G1,G2> >(g1,g2);
   672   }
   673 
   674 }
   675 
   676 #endif