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