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