madarasip@1141: /* -*- mode: C++; indent-tabs-mode: nil; -*-
madarasip@1141:  *
madarasip@1141:  * This file is a part of LEMON, a generic C++ optimization library.
madarasip@1141:  *
madarasip@1141:  * Copyright (C) 2015
madarasip@1141:  * EMAXA Kutato-fejleszto Kft. (EMAXA Research Ltd.)
madarasip@1141:  *
madarasip@1141:  * Permission to use, modify and distribute this software is granted
madarasip@1141:  * provided that this copyright notice appears in all copies. For
madarasip@1141:  * precise terms see the accompanying LICENSE file.
madarasip@1141:  *
madarasip@1141:  * This software is provided "AS IS" with no warranty of any kind,
madarasip@1141:  * express or implied, and with no claim as to its suitability for any
madarasip@1141:  * purpose.
madarasip@1141:  *
madarasip@1141:  */
madarasip@1141: 
madarasip@1141: #ifndef LEMON_VF2_H
madarasip@1141: #define LEMON_VF2_H
madarasip@1141: 
alpar@1142: ///\ingroup graph_properties
alpar@1142: ///\file
alpar@1142: ///\brief VF2 algorithm \cite cordella2004sub.
alpar@1142: 
madarasip@1141: #include <lemon/core.h>
madarasip@1141: #include <lemon/concepts/graph.h>
madarasip@1141: #include <lemon/dfs.h>
madarasip@1141: #include <lemon/bfs.h>
madarasip@1141: #include <test/test_tools.h>
madarasip@1141: 
madarasip@1141: #include <vector>
madarasip@1141: #include <set>
madarasip@1141: 
madarasip@1141: namespace lemon
madarasip@1141: {
madarasip@1141:   namespace bits
madarasip@1141:   {
madarasip@1141:     namespace vf2
madarasip@1141:     {
madarasip@1141:       class AlwaysEq
madarasip@1141:       {
madarasip@1141:       public:
madarasip@1141:         template<class T1, class T2>
madarasip@1141:         bool operator()(T1, T2) const
madarasip@1141:         {
madarasip@1141:           return true;
madarasip@1141:         }
madarasip@1141:       };
madarasip@1141: 
madarasip@1141:       template<class M1, class M2>
madarasip@1141:       class MapEq
madarasip@1141:       {
madarasip@1141:         const M1 &_m1;
madarasip@1141:         const M2 &_m2;
madarasip@1141:       public:
madarasip@1141:         MapEq(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
madarasip@1141:         bool operator()(typename M1::Key k1, typename M2::Key k2) const
madarasip@1141:         {
madarasip@1141:           return _m1[k1] == _m2[k2];
madarasip@1141:         }
madarasip@1141:       };
madarasip@1141: 
madarasip@1141:       template <class G>
madarasip@1141:       class DfsLeaveOrder : public DfsVisitor<G>
madarasip@1141:       {
madarasip@1141:         const G &_g;
madarasip@1141:         std::vector<typename G::Node> &_order;
madarasip@1141:         int i;
madarasip@1141:       public:
madarasip@1141:         DfsLeaveOrder(const G &g, std::vector<typename G::Node> &order)
madarasip@1141:           : i(countNodes(g)), _g(g), _order(order)
madarasip@1141:         {}
madarasip@1141:         void leave(const typename G::Node &node)
madarasip@1141:         {
madarasip@1141:           _order[--i]=node;
madarasip@1141:         }
madarasip@1141:       };
madarasip@1141: 
madarasip@1141:       template <class G>
madarasip@1141:       class BfsLeaveOrder : public BfsVisitor<G>
madarasip@1141:       {
madarasip@1141:         int i;
madarasip@1141:         const G &_g;
madarasip@1141:         std::vector<typename G::Node> &_order;
madarasip@1141:       public:
madarasip@1141:         BfsLeaveOrder(const G &g, std::vector<typename G::Node> &order)
madarasip@1141:           : i(0), _g(g), _order(order)
madarasip@1141:         {}
madarasip@1141:         void process(const typename G::Node &node)
madarasip@1141:         {
madarasip@1141:           _order[i++]=node;
madarasip@1141:         }
madarasip@1141:       };
madarasip@1141:     }
madarasip@1141:   }
madarasip@1141: 
alpar@1142:   ///Graph mapping types.
alpar@1142: 
alpar@1142:   ///\ingroup graph_isomorphism
alpar@1142:   ///The \ref Vf2 "VF2" algorithm is capable of finding different kind of
alpar@1142:   ///embeddings, this enum specifies its type.
alpar@1142:   ///
alpar@1142:   ///See \ref graph_isomorphism for a more detailed description.
alpar@1142:   enum Vf2MappingType {
alpar@1142:     /// Subgraph isomorphism
madarasip@1141:     SUBGRAPH = 0,
alpar@1142:     /// Induced subgraph isomorphism
madarasip@1141:     INDUCED = 1,
alpar@1142:     /// Graph isomorphism
alpar@1142: 
alpar@1142:     /// If the two graph has the same number of nodes, than it is
alpar@1142:     /// equivalent to \ref INDUCED, and if they also have the same
alpar@1142:     /// number of edges, then it is also equivalent to \ref SUBGRAPH.
alpar@1142:     ///
alpar@1142:     /// However, using this setting is faster than the other two
alpar@1142:     /// options.
madarasip@1141:     ISOMORPH = 2
madarasip@1141:   };
madarasip@1141: 
alpar@1142:   ///%VF2 algorithm class.
alpar@1142: 
alpar@1142:   ///\ingroup graph_isomorphism This class provides an efficient
alpar@1142:   ///implementation of the %VF2 algorithm \cite cordella2004sub
alpar@1142:   ///for variants of the (Sub)graph Isomorphism problem.
alpar@1142:   ///
alpar@1142:   ///There is also a \ref vf2() "function-type interface" called \ref vf2()
alpar@1142:   ///for the %VF2 algorithm, which is probably more convenient in most
alpar@1142:   ///use-cases.
alpar@1142:   ///
alpar@1142:   ///\tparam G1 The type of the graph to be embedded.
alpar@1142:   ///The default type is \ref ListDigraph.
alpar@1142:   ///\tparam G2 The type of the graph g1 will be embedded into.
alpar@1142:   ///The default type is \ref ListDigraph.
alpar@1142:   ///\tparam M The type of the NodeMap storing the mapping.
alpar@1142:   ///By default, it is G1::NodeMap<G2::Node>
alpar@1142:   ///\tparam NEQ A bool-valued binary functor determinining whether a node is
alpar@1142:   ///mappable to another. By default it is an always true operator.
alpar@1142:   ///
alpar@1142:   ///\sa vf2()
alpar@1142: #ifdef DOXYGEN
alpar@1142:   template<class G1, class G2, class M, class NEQ >
alpar@1142: #else
alpar@1142:   template<class G1=ListDigraph,
alpar@1142:            class G2=ListDigraph,
alpar@1142:            class M = typename G1::template NodeMap<G2::Node>,
alpar@1142:            class NEQ = bits::vf2::AlwaysEq >
alpar@1142: #endif
madarasip@1141:   class Vf2
madarasip@1141:   {
madarasip@1141:     //Current depth in the DFS tree.
madarasip@1141:     int _depth;
madarasip@1141:     //Functor with bool operator()(G1::Node,G2::Node), which returns 1
madarasip@1141:     //if and only if the 2 nodes are equivalent.
alpar@1142:     NEQ _nEq;
madarasip@1141: 
madarasip@1141:     typename G2::template NodeMap<int> _conn;
alpar@1142:     //Current mapping. We index it by the nodes of g1, and match[v] is
madarasip@1141:     //a node of g2.
alpar@1142:     M &_mapping;
madarasip@1141:     //order[i] is the node of g1, for which we find a pair if depth=i
madarasip@1141:     std::vector<typename G1::Node> order;
madarasip@1141:     //currEdgeIts[i] is an edge iterator, witch is last used in the ith
madarasip@1141:     //depth to find a pair for order[i].
madarasip@1141:     std::vector<typename G2::IncEdgeIt> currEdgeIts;
madarasip@1141:     //The small graph.
madarasip@1141:     const G1 &_g1;
madarasip@1141:     //The big graph.
madarasip@1141:     const G2 &_g2;
madarasip@1141:     //lookup tables for cut the searchtree
madarasip@1141:     typename G1::template NodeMap<int> rNew1t,rInOut1t;
madarasip@1141: 
alpar@1142:     Vf2MappingType _mapping_type;
madarasip@1141: 
madarasip@1141:     //cut the search tree
alpar@1142:     template<Vf2MappingType MT>
madarasip@1141:     bool cut(const typename G1::Node n1,const typename G2::Node n2) const
madarasip@1141:     {
madarasip@1141:       int rNew2=0,rInOut2=0;
madarasip@1141:       for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2)
madarasip@1141:         {
madarasip@1141:           const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
madarasip@1141:           if(_conn[currNode]>0)
madarasip@1141:             ++rInOut2;
madarasip@1141:           else if(MT!=SUBGRAPH&&_conn[currNode]==0)
madarasip@1141:             ++rNew2;
madarasip@1141:         }
madarasip@1141:       switch(MT)
madarasip@1141:         {
madarasip@1141:         case INDUCED:
madarasip@1141:           return rInOut1t[n1]<=rInOut2&&rNew1t[n1]<=rNew2;
madarasip@1141:         case SUBGRAPH:
madarasip@1141:           return rInOut1t[n1]<=rInOut2;
madarasip@1141:         case ISOMORPH:
madarasip@1141:           return rInOut1t[n1]==rInOut2&&rNew1t[n1]==rNew2;
madarasip@1141:         default:
madarasip@1141:           return false;
madarasip@1141:         }
madarasip@1141:     }
madarasip@1141: 
alpar@1142:     template<Vf2MappingType MT>
madarasip@1141:     bool feas(const typename G1::Node n1,const typename G2::Node n2)
madarasip@1141:     {
madarasip@1141:       if(!_nEq(n1,n2))
madarasip@1141:         return 0;
madarasip@1141: 
madarasip@1141:       for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1)
madarasip@1141:         {
madarasip@1141:           const typename G1::Node currNode=_g1.oppositeNode(n1,e1);
alpar@1142:           if(_mapping[currNode]!=INVALID)
alpar@1142:             --_conn[_mapping[currNode]];
madarasip@1141:         }
madarasip@1141:       bool isIso=1;
madarasip@1141:       for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2)
madarasip@1141:         {
madarasip@1141:           const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
madarasip@1141:           if(_conn[currNode]<-1)
madarasip@1141:             ++_conn[currNode];
madarasip@1141:           else if(MT!=SUBGRAPH&&_conn[currNode]==-1)
madarasip@1141:             {
madarasip@1141:               isIso=0;
madarasip@1141:               break;
madarasip@1141:             }
madarasip@1141:         }
madarasip@1141: 
madarasip@1141:       for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1)
madarasip@1141:         {
madarasip@1141:           const typename G1::Node currNode=_g1.oppositeNode(n1,e1);
alpar@1142:           if(_mapping[currNode]!=INVALID&&_conn[_mapping[currNode]]!=-1)
madarasip@1141:             {
madarasip@1141:               switch(MT)
madarasip@1141:                 {
madarasip@1141:                 case INDUCED:
madarasip@1141:                 case ISOMORPH:
madarasip@1141:                   isIso=0;
madarasip@1141:                   break;
madarasip@1141:                 case SUBGRAPH:
alpar@1142:                   if(_conn[_mapping[currNode]]<-1)
madarasip@1141:                     isIso=0;
madarasip@1141:                   break;
madarasip@1141:                 }
alpar@1142:               _conn[_mapping[currNode]]=-1;
madarasip@1141:             }
madarasip@1141:         }
madarasip@1141:       return isIso&&cut<MT>(n1,n2);
madarasip@1141:     }
madarasip@1141: 
madarasip@1141:     void addPair(const typename G1::Node n1,const typename G2::Node n2)
madarasip@1141:     {
madarasip@1141:       _conn[n2]=-1;
alpar@1142:       _mapping.set(n1,n2);
madarasip@1141:       for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2)
madarasip@1141:         if(_conn[_g2.oppositeNode(n2,e2)]!=-1)
madarasip@1141:           ++_conn[_g2.oppositeNode(n2,e2)];
madarasip@1141:     }
madarasip@1141: 
madarasip@1141:     void subPair(const typename G1::Node n1,const typename G2::Node n2)
madarasip@1141:     {
madarasip@1141:       _conn[n2]=0;
alpar@1142:       _mapping.set(n1,INVALID);
madarasip@1141:       for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2)
madarasip@1141:         {
madarasip@1141:           const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
madarasip@1141:           if(_conn[currNode]>0)
madarasip@1141:             --_conn[currNode];
madarasip@1141:           else if(_conn[currNode]==-1)
madarasip@1141:             ++_conn[n2];
madarasip@1141:         }
madarasip@1141:     }
madarasip@1141: 
madarasip@1141:     void setOrder()//we will find pairs for the nodes of g1 in this order
madarasip@1141:     {
madarasip@1141:       // bits::vf2::DfsLeaveOrder<G1> v(_g1,order);
madarasip@1141:       //   DfsVisit<G1,bits::vf2::DfsLeaveOrder<G1> >dfs(_g1, v);
madarasip@1141:       //   dfs.run();
madarasip@1141: 
madarasip@1141:       //it is more efficient in practice than DFS
madarasip@1141:       bits::vf2::BfsLeaveOrder<G1> v(_g1,order);
madarasip@1141:       BfsVisit<G1,bits::vf2::BfsLeaveOrder<G1> >bfs(_g1, v);
madarasip@1141:       bfs.run();
madarasip@1141:     }
madarasip@1141: 
alpar@1142:     template<Vf2MappingType MT>
madarasip@1141:     bool extMatch()
madarasip@1141:     {
madarasip@1141:       while(_depth>=0)
madarasip@1141:         {
madarasip@1141:           //there are not nodes in g1, which has not pair in g2.
madarasip@1141:           if(_depth==static_cast<int>(order.size()))
madarasip@1141:             {
madarasip@1141:               --_depth;
madarasip@1141:               return true;
madarasip@1141:             }
madarasip@1141:           //the node of g2, which neighbours are the candidates for
madarasip@1141:           //the pair of order[_depth]
madarasip@1141:           typename G2::Node currPNode;
madarasip@1141:           if(currEdgeIts[_depth]==INVALID)
madarasip@1141:             {
madarasip@1141:               typename G1::IncEdgeIt fstMatchedE(_g1,order[_depth]);
alpar@1142:               //if _mapping[order[_depth]]!=INVALID, we dont use
madarasip@1141:               //fstMatchedE
alpar@1142:               if(_mapping[order[_depth]]==INVALID)
madarasip@1141:                 for(; fstMatchedE!=INVALID &&
alpar@1142:                       _mapping[_g1.oppositeNode(order[_depth],
madarasip@1141:                                               fstMatchedE)]==INVALID;
madarasip@1141:                     ++fstMatchedE) ; //find fstMatchedE
alpar@1142:               if(fstMatchedE==INVALID||_mapping[order[_depth]]!=INVALID)
madarasip@1141:                 {
madarasip@1141:                   //We did not find an covered neighbour, this means
madarasip@1141:                   //the graph is not connected(or _depth==0).  Every
madarasip@1141:                   //uncovered(and there are some other properties due
madarasip@1141:                   //to the spec. problem types) node of g2 is
madarasip@1141:                   //candidate.  We can read the iterator of the last
madarasip@1141:                   //tryed node from the match if it is not the first
madarasip@1141:                   //try(match[order[_depth]]!=INVALID)
madarasip@1141:                   typename G2::NodeIt n2(_g2);
madarasip@1141:                   //if its not the first try
alpar@1142:                   if(_mapping[order[_depth]]!=INVALID)
madarasip@1141:                     {
alpar@1142:                       n2=++typename G2::NodeIt(_g2,_mapping[order[_depth]]);
alpar@1142:                       subPair(order[_depth],_mapping[order[_depth]]);
madarasip@1141:                     }
madarasip@1141:                   for(; n2!=INVALID; ++n2)
madarasip@1141:                     if(MT!=SUBGRAPH&&_conn[n2]==0)
madarasip@1141:                       {
madarasip@1141:                         if(feas<MT>(order[_depth],n2))
madarasip@1141:                           break;
madarasip@1141:                       }
madarasip@1141:                     else if(MT==SUBGRAPH&&_conn[n2]>=0)
madarasip@1141:                       if(feas<MT>(order[_depth],n2))
madarasip@1141:                         break;
madarasip@1141:                   // n2 is the next candidate
madarasip@1141:                   if(n2!=INVALID)
madarasip@1141:                     {
madarasip@1141:                       addPair(order[_depth],n2);
madarasip@1141:                       ++_depth;
madarasip@1141:                     }
madarasip@1141:                   else // there is no more candidate
madarasip@1141:                     --_depth;
madarasip@1141:                   continue;
madarasip@1141:                 }
madarasip@1141:               else
madarasip@1141:                 {
alpar@1142:                   currPNode=_mapping[_g1.oppositeNode(order[_depth],
alpar@1142:                                                       fstMatchedE)];
madarasip@1141:                   currEdgeIts[_depth]=typename G2::IncEdgeIt(_g2,currPNode);
madarasip@1141:                 }
madarasip@1141:             }
madarasip@1141:           else
madarasip@1141:             {
alpar@1142:               currPNode=_g2.oppositeNode(_mapping[order[_depth]],
madarasip@1141:                                          currEdgeIts[_depth]);
alpar@1142:               subPair(order[_depth],_mapping[order[_depth]]);
madarasip@1141:               ++currEdgeIts[_depth];
madarasip@1141:             }
madarasip@1141:           for(; currEdgeIts[_depth]!=INVALID; ++currEdgeIts[_depth])
madarasip@1141:             {
madarasip@1141:               const typename G2::Node currNode =
madarasip@1141:                 _g2.oppositeNode(currPNode, currEdgeIts[_depth]);
madarasip@1141:               //if currNode is uncovered
madarasip@1141:               if(_conn[currNode]>0&&feas<MT>(order[_depth],currNode))
madarasip@1141:                 {
madarasip@1141:                   addPair(order[_depth],currNode);
madarasip@1141:                   break;
madarasip@1141:                 }
madarasip@1141:             }
madarasip@1141:           currEdgeIts[_depth]==INVALID?--_depth:++_depth;
madarasip@1141:         }
madarasip@1141:       return false;
madarasip@1141:     }
madarasip@1141: 
madarasip@1141:     //calc. the lookup table for cut the searchtree
madarasip@1141:     void setRNew1tRInOut1t()
madarasip@1141:     {
madarasip@1141:       typename G1::template NodeMap<int> tmp(_g1,0);
madarasip@1141:       for(unsigned int i=0; i<order.size(); ++i)
madarasip@1141:         {
madarasip@1141:           tmp[order[i]]=-1;
madarasip@1141:           for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1)
madarasip@1141:             {
madarasip@1141:               const typename G1::Node currNode=_g1.oppositeNode(order[i],e1);
madarasip@1141:               if(tmp[currNode]>0)
madarasip@1141:                 ++rInOut1t[order[i]];
madarasip@1141:               else if(tmp[currNode]==0)
madarasip@1141:                 ++rNew1t[order[i]];
madarasip@1141:             }
madarasip@1141:           for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1)
madarasip@1141:             {
madarasip@1141:               const typename G1::Node currNode=_g1.oppositeNode(order[i],e1);
madarasip@1141:               if(tmp[currNode]!=-1)
madarasip@1141:                 ++tmp[currNode];
madarasip@1141:             }
madarasip@1141:         }
madarasip@1141:     }
madarasip@1141:   public:
alpar@1142:     ///Constructor
alpar@1142: 
alpar@1142:     ///Constructor
alpar@1142: 
alpar@1142:     ///\param g1 The graph to be embedded into \e g2.
alpar@1142:     ///\param g2 The graph \e g1 will be embedded into.
alpar@1142:     ///\param m \ref concepts::ReadWriteMap "read-write" NodeMap
alpar@1142:     ///storing the found mapping.
alpar@1142:     ///\param neq A bool-valued binary functor determinining whether a node is
alpar@1142:     ///mappable to another. By default it is an always true operator.
alpar@1142:     Vf2(const G1 &g1, const G2 &g2,M &m, const NEQ &neq = NEQ() ) :
alpar@1142:       _nEq(neq), _conn(g2,0), _mapping(m), order(countNodes(g1)),
madarasip@1141:       currEdgeIts(countNodes(g1),INVALID), _g1(g1), _g2(g2), rNew1t(g1,0),
madarasip@1141:       rInOut1t(g1,0), _mapping_type(SUBGRAPH)
madarasip@1141:     {
madarasip@1141:       _depth=0;
madarasip@1141:       setOrder();
madarasip@1141:       setRNew1tRInOut1t();
alpar@1143:       for(typename G1::NodeIt n(g1);n!=INVALID;++n)
alpar@1143:         m[n]=INVALID;
madarasip@1141:     }
madarasip@1141: 
alpar@1142:     ///Returns the current mapping type
madarasip@1141: 
alpar@1142:     ///Returns the current mapping type
alpar@1142:     ///
alpar@1142:     Vf2MappingType mappingType() const { return _mapping_type; }
alpar@1142:     ///Sets mapping type
alpar@1142: 
alpar@1142:     ///Sets mapping type.
alpar@1142:     ///
alpar@1142:     ///The mapping type is set to \ref SUBGRAPH by default.
alpar@1142:     ///
alpar@1144:     ///\sa See \ref Vf2MappingType for the possible values.
alpar@1142:     void mappingType(Vf2MappingType m_type) { _mapping_type = m_type; }
alpar@1142: 
kpeter@1152:     ///Finds a mapping
alpar@1142: 
alpar@1142:     ///It finds a mapping between from g1 into g2 according to the mapping
alpar@1142:     ///type set by \ref mappingType(Vf2MappingType) "mappingType()".
alpar@1142:     ///
alpar@1142:     ///By subsequent calls, it returns all possible mappings one-by-one.
alpar@1142:     ///
alpar@1142:     ///\retval true if a mapping is found.
alpar@1142:     ///\retval false if there is no (more) mapping.
madarasip@1141:     bool find()
madarasip@1141:     {
madarasip@1141:       switch(_mapping_type)
madarasip@1141:         {
madarasip@1141:         case SUBGRAPH:
madarasip@1141:           return extMatch<SUBGRAPH>();
madarasip@1141:         case INDUCED:
madarasip@1141:           return extMatch<INDUCED>();
madarasip@1141:         case ISOMORPH:
madarasip@1141:           return extMatch<ISOMORPH>();
madarasip@1141:         default:
madarasip@1141:           return false;
madarasip@1141:         }
madarasip@1141:     }
madarasip@1141:   };
madarasip@1141: 
madarasip@1141:   template<class G1, class G2>
madarasip@1141:   class Vf2WizardBase
madarasip@1141:   {
madarasip@1141:   protected:
madarasip@1141:     typedef G1 Graph1;
madarasip@1141:     typedef G2 Graph2;
madarasip@1141: 
madarasip@1141:     const G1 &_g1;
madarasip@1141:     const G2 &_g2;
madarasip@1141: 
alpar@1142:     Vf2MappingType _mapping_type;
madarasip@1141: 
madarasip@1141:     typedef typename G1::template NodeMap<typename G2::Node> Mapping;
madarasip@1141:     bool _local_mapping;
madarasip@1141:     void *_mapping;
madarasip@1141:     void createMapping()
madarasip@1141:     {
madarasip@1141:       _mapping = new Mapping(_g1);
madarasip@1141:     }
madarasip@1141: 
madarasip@1141:     typedef bits::vf2::AlwaysEq NodeEq;
madarasip@1141:     NodeEq _node_eq;
madarasip@1141: 
madarasip@1141:     Vf2WizardBase(const G1 &g1,const G2 &g2)
madarasip@1141:       : _g1(g1), _g2(g2), _mapping_type(SUBGRAPH), _local_mapping(true) {}
madarasip@1141:   };
madarasip@1141: 
alpar@1142:   /// Auxiliary class for the function-type interface of %VF2 algorithm.
alpar@1142: 
alpar@1142:   /// This auxiliary class implements the named parameters of
alpar@1142:   /// \ref vf2() "function-type interface" of \ref Vf2 algorithm.
alpar@1142:   ///
alpar@1142:   /// \warning This class should only be used through the function \ref vf2().
alpar@1142:   ///
alpar@1142:   /// \tparam TR The traits class that defines various types used by the
alpar@1142:   /// algorithm.
madarasip@1141:   template<class TR>
madarasip@1141:   class Vf2Wizard : public TR
madarasip@1141:   {
madarasip@1141:     typedef TR Base;
madarasip@1141:     typedef typename TR::Graph1 Graph1;
madarasip@1141:     typedef typename TR::Graph2 Graph2;
madarasip@1141: 
madarasip@1141:     typedef typename TR::Mapping Mapping;
madarasip@1141:     typedef typename TR::NodeEq NodeEq;
madarasip@1141: 
madarasip@1141:     using TR::_g1;
madarasip@1141:     using TR::_g2;
madarasip@1141:     using TR::_mapping_type;
madarasip@1141:     using TR::_mapping;
madarasip@1141:     using TR::_node_eq;
madarasip@1141: 
madarasip@1141:   public:
alpar@1142:     ///Constructor
madarasip@1141:     Vf2Wizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {}
madarasip@1141: 
madarasip@1141:     ///Copy constructor
madarasip@1141:     Vf2Wizard(const Base &b) : Base(b) {}
madarasip@1141: 
madarasip@1141: 
madarasip@1141:     template<class T>
madarasip@1141:     struct SetMappingBase : public Base {
madarasip@1141:       typedef T Mapping;
madarasip@1141:       SetMappingBase(const Base &b) : Base(b) {}
madarasip@1141:     };
madarasip@1141: 
madarasip@1141:     ///\brief \ref named-templ-param "Named parameter" for setting
madarasip@1141:     ///the mapping.
madarasip@1141:     ///
madarasip@1141:     ///\ref named-templ-param "Named parameter" function for setting
madarasip@1141:     ///the map that stores the found embedding.
madarasip@1141:     template<class T>
madarasip@1141:     Vf2Wizard< SetMappingBase<T> > mapping(const T &t)
madarasip@1141:     {
madarasip@1141:       Base::_mapping=reinterpret_cast<void*>(const_cast<T*>(&t));
madarasip@1141:       Base::_local_mapping = false;
madarasip@1141:       return Vf2Wizard<SetMappingBase<T> >(*this);
madarasip@1141:     }
madarasip@1141: 
madarasip@1141:     template<class NE>
madarasip@1141:     struct SetNodeEqBase : public Base {
madarasip@1141:       typedef NE NodeEq;
madarasip@1141:       NodeEq _node_eq;
madarasip@1141:       SetNodeEqBase(const Base &b, const NE &node_eq)
madarasip@1141:         : Base(b), _node_eq(node_eq) {}
madarasip@1141:     };
madarasip@1141: 
madarasip@1141:     ///\brief \ref named-templ-param "Named parameter" for setting
madarasip@1141:     ///the node equivalence relation.
madarasip@1141:     ///
madarasip@1141:     ///\ref named-templ-param "Named parameter" function for setting
madarasip@1141:     ///the equivalence relation between the nodes.
alpar@1142:     ///
alpar@1142:     ///\param node_eq A bool-valued binary functor determinining
alpar@1142:     ///whether a node is mappable to another. By default it is an
alpar@1142:     ///always true operator.
madarasip@1141:     template<class T>
madarasip@1141:     Vf2Wizard< SetNodeEqBase<T> > nodeEq(const T &node_eq)
madarasip@1141:     {
madarasip@1141:       return Vf2Wizard<SetNodeEqBase<T> >(SetNodeEqBase<T>(*this,node_eq));
madarasip@1141:     }
madarasip@1141: 
madarasip@1141:     ///\brief \ref named-templ-param "Named parameter" for setting
madarasip@1141:     ///the node labels.
madarasip@1141:     ///
madarasip@1141:     ///\ref named-templ-param "Named parameter" function for setting
madarasip@1141:     ///the node labels defining equivalence relation between them.
alpar@1142:     ///
alpar@1144:     ///\param m1 It is arbitrary \ref concepts::ReadMap "readable node map"
alpar@1144:     ///of g1.
alpar@1144:     ///\param m2 It is arbitrary \ref concepts::ReadMap "readable node map"
alpar@1144:     ///of g2.
alpar@1142:     ///
alpar@1142:     ///The value type of these maps must be equal comparable.
madarasip@1141:     template<class M1, class M2>
madarasip@1141:     Vf2Wizard< SetNodeEqBase<bits::vf2::MapEq<M1,M2> > >
madarasip@1141:     nodeLabels(const M1 &m1,const M2 &m2)
madarasip@1141:     {
madarasip@1141:       return nodeEq(bits::vf2::MapEq<M1,M2>(m1,m2));
madarasip@1141:     }
madarasip@1141: 
alpar@1142:     ///\brief \ref named-templ-param "Named parameter" for setting
alpar@1142:     ///the mapping type.
alpar@1142:     ///
alpar@1142:     ///\ref named-templ-param "Named parameter" for setting
alpar@1142:     ///the mapping type.
alpar@1142:     ///
alpar@1142:     ///The mapping type is set to \ref SUBGRAPH by default.
alpar@1142:     ///
alpar@1144:     ///\sa See \ref Vf2MappingType for the possible values.
alpar@1142:     Vf2Wizard<Base> &mappingType(Vf2MappingType m_type)
madarasip@1141:     {
madarasip@1141:       _mapping_type = m_type;
madarasip@1141:       return *this;
madarasip@1141:     }
madarasip@1141: 
alpar@1142:     ///\brief \ref named-templ-param "Named parameter" for setting
alpar@1142:     ///the mapping type to \ref INDUCED.
alpar@1142:     ///
alpar@1142:     ///\ref named-templ-param "Named parameter" for setting
alpar@1142:     ///the mapping type to \ref INDUCED.
madarasip@1141:     Vf2Wizard<Base> &induced()
madarasip@1141:     {
madarasip@1141:       _mapping_type = INDUCED;
madarasip@1141:       return *this;
madarasip@1141:     }
madarasip@1141: 
alpar@1142:     ///\brief \ref named-templ-param "Named parameter" for setting
alpar@1142:     ///the mapping type to \ref ISOMORPH.
alpar@1142:     ///
alpar@1142:     ///\ref named-templ-param "Named parameter" for setting
alpar@1142:     ///the mapping type to \ref ISOMORPH.
madarasip@1141:     Vf2Wizard<Base> &iso()
madarasip@1141:     {
madarasip@1141:       _mapping_type = ISOMORPH;
madarasip@1141:       return *this;
madarasip@1141:     }
madarasip@1141: 
alpar@1142:     ///Runs VF2 algorithm.
alpar@1142: 
alpar@1142:     ///This method runs VF2 algorithm.
alpar@1142:     ///
alpar@1142:     ///\retval true if a mapping is found.
alpar@1142:     ///\retval false if there is no (more) mapping.
madarasip@1141:     bool run()
madarasip@1141:     {
madarasip@1141:       if(Base::_local_mapping)
madarasip@1141:         Base::createMapping();
madarasip@1141: 
madarasip@1141:       Vf2<Graph1, Graph2, Mapping, NodeEq >
madarasip@1141:         alg(_g1, _g2, *reinterpret_cast<Mapping*>(_mapping), _node_eq);
madarasip@1141: 
madarasip@1141:       alg.mappingType(_mapping_type);
madarasip@1141: 
madarasip@1141:       bool ret = alg.find();
madarasip@1141: 
madarasip@1141:       if(Base::_local_mapping)
madarasip@1141:         delete reinterpret_cast<Mapping*>(_mapping);
madarasip@1141: 
madarasip@1141:       return ret;
madarasip@1141:     }
madarasip@1141:   };
madarasip@1141: 
alpar@1142:   ///Function-type interface for VF2 algorithm.
alpar@1142: 
alpar@1142:   /// \ingroup graph_isomorphism
alpar@1142:   ///Function-type interface for VF2 algorithm \cite cordella2004sub.
alpar@1142:   ///
alpar@1142:   ///This function has several \ref named-func-param "named parameters"
alpar@1142:   ///declared as the members of class \ref Vf2Wizard.
alpar@1142:   ///The following examples show how to use these parameters.
alpar@1142:   ///\code
alpar@1142:   ///  // Find an embedding of graph g into graph h
alpar@1142:   ///  ListGraph::NodeMap<ListGraph::Node> m(g);
alpar@1142:   ///  vf2(g,h).mapping(m).run();
alpar@1142:   ///
alpar@1142:   ///  // Check whether graphs g and h are isomorphic
alpar@1142:   ///  bool is_iso = vf2(g,h).iso().run();
alpar@1142:   ///\endcode
alpar@1142:   ///\warning Don't forget to put the \ref Vf2Wizard::run() "run()"
alpar@1142:   ///to the end of the expression.
alpar@1142:   ///\sa Vf2Wizard
alpar@1142:   ///\sa Vf2
madarasip@1141:   template<class G1, class G2>
madarasip@1141:   Vf2Wizard<Vf2WizardBase<G1,G2> > vf2(const G1 &g1, const G2 &g2)
madarasip@1141:   {
madarasip@1141:     return Vf2Wizard<Vf2WizardBase<G1,G2> >(g1,g2);
madarasip@1141:   }
madarasip@1141: 
madarasip@1141: }
madarasip@1141: 
madarasip@1141: #endif