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@1186:  * Copyright (C) 2015-2017
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@1186: #include <lemon/bits/vf2_internals.h>
madarasip@1141: 
madarasip@1141: #include <vector>
madarasip@1141: 
madarasip@1186: namespace lemon {
madarasip@1186:   namespace bits {
madarasip@1186:     namespace vf2 {
madarasip@1186: 
madarasip@1186:       class AlwaysEq {
madarasip@1141:       public:
madarasip@1141:         template<class T1, class T2>
madarasip@1186:         bool operator()(T1&, T2&) const {
madarasip@1141:           return true;
madarasip@1141:         }
madarasip@1141:       };
madarasip@1141: 
madarasip@1141:       template<class M1, class M2>
madarasip@1186:       class MapEq{
madarasip@1141:         const M1 &_m1;
madarasip@1141:         const M2 &_m2;
madarasip@1141:       public:
madarasip@1186:         MapEq(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) { }
madarasip@1186:         bool operator()(typename M1::Key k1, typename M2::Key k2) const {
madarasip@1141:           return _m1[k1] == _m2[k2];
madarasip@1141:         }
madarasip@1141:       };
madarasip@1141: 
madarasip@1141:       template <class G>
madarasip@1186:       class DfsLeaveOrder : public DfsVisitor<G> {
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@1186:           : i(countNodes(g)), _g(g), _order(order) { }
madarasip@1186:         void leave(const typename G::Node &node) {
madarasip@1141:           _order[--i]=node;
madarasip@1141:         }
madarasip@1141:       };
madarasip@1141: 
madarasip@1141:       template <class G>
madarasip@1186:       class BfsLeaveOrder : public BfsVisitor<G> {
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@1186:           : i(0), _g(g), _order(order){
madarasip@1186:         }
madarasip@1186:         void process(const typename G::Node &node) {
madarasip@1141:           _order[i++]=node;
madarasip@1141:         }
madarasip@1141:       };
madarasip@1141:     }
madarasip@1141:   }
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
kpeter@1188:   ///use cases.
alpar@1142:   ///
alpar@1142:   ///\tparam G1 The type of the graph to be embedded.
kpeter@1191:   ///The default type is \ref ListGraph.
alpar@1142:   ///\tparam G2 The type of the graph g1 will be embedded into.
kpeter@1191:   ///The default type is \ref ListGraph.
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
kpeter@1188:   ///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
kpeter@1191:   template<class G1 = ListGraph,
kpeter@1191:            class G2 = ListGraph,
alpar@1142:            class M = typename G1::template NodeMap<G2::Node>,
alpar@1142:            class NEQ = bits::vf2::AlwaysEq >
alpar@1142: #endif
madarasip@1186:   class Vf2 {
kpeter@1188:     //The graph to be embedded
madarasip@1141:     const G1 &_g1;
kpeter@1188: 
kpeter@1188:     //The graph into which g1 is to be embedded
madarasip@1141:     const G2 &_g2;
kpeter@1188: 
kpeter@1189:     //Functor with bool operator()(G1::Node,G2::Node), which returns 1
kpeter@1189:     //if and only if the two nodes are equivalent
kpeter@1189:     NEQ _nEq;
kpeter@1189: 
kpeter@1189:     //Current depth in the DFS tree.
kpeter@1189:     int _depth;
kpeter@1189: 
kpeter@1189:     //The current mapping. _mapping[v1]=v2 iff v1 has been mapped to v2,
kpeter@1189:     //where v1 is a node of G1 and v2 is a node of G2
kpeter@1189:     M &_mapping;
kpeter@1189: 
kpeter@1189:     //_order[i] is the node of g1 for which a pair is searched if depth=i
kpeter@1189:     std::vector<typename G1::Node> _order;
kpeter@1189:  
kpeter@1189:     //_conn[v2] = number of covered neighbours of v2
kpeter@1189:     typename G2::template NodeMap<int> _conn;
kpeter@1189: 
kpeter@1189:     //_currEdgeIts[i] is the last used edge iterator in the i-th
kpeter@1189:     //depth to find a pair for node _order[i]
kpeter@1189:     std::vector<typename G2::IncEdgeIt> _currEdgeIts;
kpeter@1189: 
madarasip@1186:     //lookup tables for cutting the searchtree
kpeter@1189:     typename G1::template NodeMap<int> _rNew1t, _rInOut1t;
madarasip@1141: 
madarasip@1186:     MappingType _mapping_type;
madarasip@1186: 
madarasip@1186:     bool _deallocMappingAfterUse;
madarasip@1141: 
madarasip@1141:     //cut the search tree
madarasip@1186:     template<MappingType MT>
madarasip@1186:     bool cut(const typename G1::Node n1,const typename G2::Node n2) const {
madarasip@1141:       int rNew2=0,rInOut2=0;
madarasip@1186:       for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
madarasip@1186:         const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
madarasip@1186:         if(_conn[currNode]>0)
madarasip@1186:           ++rInOut2;
madarasip@1186:         else if(MT!=SUBGRAPH&&_conn[currNode]==0)
madarasip@1186:           ++rNew2;
madarasip@1186:       }
madarasip@1186:       switch(MT) {
madarasip@1186:       case INDUCED:
kpeter@1189:         return _rInOut1t[n1]<=rInOut2&&_rNew1t[n1]<=rNew2;
madarasip@1186:       case SUBGRAPH:
kpeter@1189:         return _rInOut1t[n1]<=rInOut2;
madarasip@1186:       case ISOMORPH:
kpeter@1189:         return _rInOut1t[n1]==rInOut2&&_rNew1t[n1]==rNew2;
madarasip@1186:       default:
madarasip@1186:         return false;
madarasip@1186:       }
madarasip@1141:     }
madarasip@1141: 
madarasip@1186:     template<MappingType MT>
madarasip@1186:     bool feas(const typename G1::Node n1,const typename G2::Node n2) {
madarasip@1141:       if(!_nEq(n1,n2))
madarasip@1141:         return 0;
madarasip@1141: 
madarasip@1186:       for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
madarasip@1186:         const typename G1::Node& currNode=_g1.oppositeNode(n1,e1);
madarasip@1186:         if(_mapping[currNode]!=INVALID)
madarasip@1186:           --_conn[_mapping[currNode]];
madarasip@1186:       }
madarasip@1186:       bool isIso=1;
madarasip@1186:       for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
madarasip@1186:         int& connCurrNode = _conn[_g2.oppositeNode(n2,e2)];
madarasip@1186:         if(connCurrNode<-1)
madarasip@1186:           ++connCurrNode;
madarasip@1186:         else if(MT!=SUBGRAPH&&connCurrNode==-1) {
madarasip@1186:           isIso=0;
madarasip@1186:           break;
madarasip@1141:         }
madarasip@1186:       }
madarasip@1186: 
madarasip@1186:       for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
madarasip@1186:         const typename G2::Node& currNodePair=_mapping[_g1.oppositeNode(n1,e1)];
madarasip@1186:         int& connCurrNodePair=_conn[currNodePair];
madarasip@1186:         if(currNodePair!=INVALID&&connCurrNodePair!=-1) {
madarasip@1186:           switch(MT) {
madarasip@1186:           case INDUCED:
madarasip@1186:           case ISOMORPH:
madarasip@1186:             isIso=0;
madarasip@1186:             break;
madarasip@1186:           case SUBGRAPH:
madarasip@1186:             if(connCurrNodePair<-1)
madarasip@1141:               isIso=0;
madarasip@1186:             break;
madarasip@1186:           }
madarasip@1186:           connCurrNodePair=-1;
madarasip@1141:         }
madarasip@1186:       }
madarasip@1141:       return isIso&&cut<MT>(n1,n2);
madarasip@1141:     }
madarasip@1141: 
madarasip@1186:     void addPair(const typename G1::Node n1,const typename G2::Node n2) {
madarasip@1141:       _conn[n2]=-1;
alpar@1142:       _mapping.set(n1,n2);
madarasip@1186:       for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
madarasip@1186:         int& currConn = _conn[_g2.oppositeNode(n2,e2)];
madarasip@1186:         if(currConn!=-1)
madarasip@1186:           ++currConn;
madarasip@1186:       }
madarasip@1141:     }
madarasip@1141: 
madarasip@1186:     void subPair(const typename G1::Node n1,const typename G2::Node n2) {
madarasip@1141:       _conn[n2]=0;
alpar@1142:       _mapping.set(n1,INVALID);
madarasip@1186:       for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
madarasip@1186:         int& currConn = _conn[_g2.oppositeNode(n2,e2)];
madarasip@1186:         if(currConn>0)
madarasip@1186:           --currConn;
madarasip@1186:         else if(currConn==-1)
madarasip@1186:           ++_conn[n2];
madarasip@1186:       }
madarasip@1141:     }
madarasip@1141: 
kpeter@1190:     void initOrder() {
madarasip@1186:       // we will find pairs for the nodes of g1 in this order
madarasip@1186: 
kpeter@1189:       // 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
kpeter@1189:       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: 
madarasip@1186:     template<MappingType MT>
madarasip@1186:     bool extMatch() {
madarasip@1186:       while(_depth>=0) {
kpeter@1189:         if(_depth==static_cast<int>(_order.size())) {
kpeter@1188:           //all nodes of g1 are mapped to nodes of g2
madarasip@1186:           --_depth;
madarasip@1186:           return true;
madarasip@1186:         }
kpeter@1189:         typename G1::Node& nodeOfDepth = _order[_depth];
madarasip@1186:         const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth];
kpeter@1189:         typename G2::IncEdgeIt &edgeItOfDepth = _currEdgeIts[_depth];
kpeter@1188:         //the node of g2 whose neighbours are the candidates for
madarasip@1186:         //the pair of nodeOfDepth
madarasip@1186:         typename G2::Node currPNode;
madarasip@1186:         if(edgeItOfDepth==INVALID) {
madarasip@1186:           typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth);
kpeter@1188:           //if pairOfNodeOfDepth!=INVALID, we don't use fstMatchedE
kpeter@1188:           if(pairOfNodeOfDepth==INVALID) {
madarasip@1186:             for(; fstMatchedE!=INVALID &&
madarasip@1186:                   _mapping[_g1.oppositeNode(nodeOfDepth,
madarasip@1186:                                             fstMatchedE)]==INVALID;
madarasip@1186:                 ++fstMatchedE) ; //find fstMatchedE
kpeter@1188:           }
madarasip@1186:           if(fstMatchedE==INVALID||pairOfNodeOfDepth!=INVALID) {
kpeter@1188:             //We found no covered neighbours, this means that
kpeter@1188:             //the graph is not connected (or _depth==0). Each
kpeter@1188:             //uncovered (and there are some other properties due
madarasip@1186:             //to the spec. problem types) node of g2 is
kpeter@1188:             //candidate. We can read the iterator of the last
madarasip@1186:             //tried node from the match if it is not the first
kpeter@1188:             //try (match[nodeOfDepth]!=INVALID)
madarasip@1186:             typename G2::NodeIt n2(_g2);
madarasip@1186:             //if it's not the first try
madarasip@1186:             if(pairOfNodeOfDepth!=INVALID) {
madarasip@1186:               n2=++typename G2::NodeIt(_g2,pairOfNodeOfDepth);
madarasip@1186:               subPair(nodeOfDepth,pairOfNodeOfDepth);
madarasip@1186:             }
madarasip@1186:             for(; n2!=INVALID; ++n2)
madarasip@1186:               if(MT!=SUBGRAPH) {
madarasip@1186:                 if(_conn[n2]==0&&feas<MT>(nodeOfDepth,n2))
madarasip@1186:                   break;
madarasip@1186:               }
madarasip@1186:               else if(_conn[n2]>=0&&feas<MT>(nodeOfDepth,n2))
madarasip@1186:                 break;
madarasip@1186:             // n2 is the next candidate
madarasip@1186:             if(n2!=INVALID){
madarasip@1186:               addPair(nodeOfDepth,n2);
madarasip@1186:               ++_depth;
madarasip@1186:             }
madarasip@1186:             else // there are no more candidates
madarasip@1141:               --_depth;
madarasip@1186:             continue;
madarasip@1186:           }
madarasip@1186:           else {
madarasip@1186:             currPNode=_mapping[_g1.oppositeNode(nodeOfDepth,
madarasip@1186:                                                 fstMatchedE)];
madarasip@1186:             edgeItOfDepth=typename G2::IncEdgeIt(_g2,currPNode);
madarasip@1186:           }
madarasip@1141:         }
madarasip@1186:         else {
madarasip@1186:           currPNode=_g2.oppositeNode(pairOfNodeOfDepth,
madarasip@1186:                                      edgeItOfDepth);
madarasip@1186:           subPair(nodeOfDepth,pairOfNodeOfDepth);
madarasip@1186:           ++edgeItOfDepth;
madarasip@1186:         }
madarasip@1186:         for(; edgeItOfDepth!=INVALID; ++edgeItOfDepth) {
madarasip@1186:           const typename G2::Node currNode =
madarasip@1186:             _g2.oppositeNode(currPNode, edgeItOfDepth);
madarasip@1186:           if(_conn[currNode]>0&&feas<MT>(nodeOfDepth,currNode)) {
madarasip@1186:             addPair(nodeOfDepth,currNode);
madarasip@1186:             break;
madarasip@1186:           }
madarasip@1186:         }
madarasip@1186:         edgeItOfDepth==INVALID?--_depth:++_depth;
madarasip@1186:       }
madarasip@1141:       return false;
madarasip@1141:     }
madarasip@1141: 
kpeter@1188:     //calculate the lookup table for cutting the search tree
kpeter@1190:     void initRNew1tRInOut1t() {
madarasip@1141:       typename G1::template NodeMap<int> tmp(_g1,0);
kpeter@1189:       for(unsigned int i=0; i<_order.size(); ++i) {
kpeter@1189:         const typename G1::Node& orderI = _order[i];
madarasip@1186:         tmp[orderI]=-1;
madarasip@1186:         for(typename G1::IncEdgeIt e1(_g1,orderI); e1!=INVALID; ++e1) {
madarasip@1186:           const typename G1::Node currNode=_g1.oppositeNode(orderI,e1);
madarasip@1186:           if(tmp[currNode]>0)
kpeter@1189:             ++_rInOut1t[orderI];
madarasip@1186:           else if(tmp[currNode]==0)
kpeter@1189:             ++_rNew1t[orderI];
madarasip@1141:         }
madarasip@1186:         for(typename G1::IncEdgeIt e1(_g1,orderI); e1!=INVALID; ++e1) {
madarasip@1186:           const typename G1::Node currNode=_g1.oppositeNode(orderI,e1);
madarasip@1186:           if(tmp[currNode]!=-1)
madarasip@1186:             ++tmp[currNode];
madarasip@1186:         }
madarasip@1186:       }
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.
madarasip@1186:     ///\param neq A bool-valued binary functor determining whether a node is
alpar@1142:     ///mappable to another. By default it is an always true operator.
madarasip@1186:     Vf2(const G1 &g1, const G2 &g2, M &m, const NEQ &neq = NEQ() ) :
kpeter@1189:       _g1(g1), _g2(g2), _nEq(neq), _depth(0), _mapping(m),
kpeter@1189:       _order(countNodes(g1)), _conn(g2,0),
kpeter@1189:       _currEdgeIts(countNodes(g1),INVALID), _rNew1t(g1,0), _rInOut1t(g1,0),
kpeter@1189:       _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0)
kpeter@1188:     {
kpeter@1190:       initOrder();
kpeter@1190:       initRNew1tRInOut1t();
alpar@1143:       for(typename G1::NodeIt n(g1);n!=INVALID;++n)
alpar@1143:         m[n]=INVALID;
madarasip@1141:     }
madarasip@1141: 
madarasip@1186:     ///Destructor
madarasip@1186: 
madarasip@1186:     ///Destructor.
madarasip@1186:     ///
madarasip@1186: 
madarasip@1186:     ~Vf2(){
madarasip@1186:       if(_deallocMappingAfterUse)
madarasip@1186:         delete &_mapping;
madarasip@1186:     }
madarasip@1186: 
alpar@1142:     ///Returns the current mapping type
madarasip@1141: 
alpar@1142:     ///Returns the current mapping type
alpar@1142:     ///
madarasip@1186:     MappingType mappingType() const {
madarasip@1186:       return _mapping_type;
madarasip@1186:     }
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:     ///
madarasip@1186:     ///\sa See \ref MappingType for the possible values.
madarasip@1186:     void mappingType(MappingType m_type) {
madarasip@1186:       _mapping_type = m_type;
madarasip@1186:     }
alpar@1142: 
kpeter@1152:     ///Finds a mapping
alpar@1142: 
madarasip@1186:     ///It finds a mapping from g1 into g2 according to the mapping
madarasip@1186:     ///type set by \ref mappingType(MappingType) "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@1186:     bool find() {
madarasip@1186:       switch(_mapping_type) {
madarasip@1186:       case SUBGRAPH:
madarasip@1186:         return extMatch<SUBGRAPH>();
madarasip@1186:       case INDUCED:
madarasip@1186:         return extMatch<INDUCED>();
madarasip@1186:       case ISOMORPH:
madarasip@1186:         return extMatch<ISOMORPH>();
madarasip@1186:       default:
madarasip@1186:         return false;
madarasip@1186:       }
madarasip@1141:     }
madarasip@1141:   };
madarasip@1141: 
madarasip@1141:   template<class G1, class G2>
madarasip@1186:   class Vf2WizardBase {
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: 
madarasip@1186:     MappingType _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@1186:     void createMapping() {
madarasip@1141:       _mapping = new Mapping(_g1);
madarasip@1141:     }
madarasip@1141: 
madarasip@1186:     void *myVf2; //used in Vf2Wizard::find
madarasip@1186: 
madarasip@1186: 
madarasip@1141:     typedef bits::vf2::AlwaysEq NodeEq;
madarasip@1141:     NodeEq _node_eq;
madarasip@1141: 
madarasip@1141:     Vf2WizardBase(const G1 &g1,const G2 &g2)
madarasip@1186:       : _g1(g1), _g2(g2), _mapping_type(SUBGRAPH), _local_mapping(true) { }
madarasip@1141:   };
madarasip@1141: 
madarasip@1186: 
alpar@1142:   /// Auxiliary class for the function-type interface of %VF2 algorithm.
kpeter@1188:   ///
alpar@1142:   /// This auxiliary class implements the named parameters of
alpar@1142:   /// \ref vf2() "function-type interface" of \ref Vf2 algorithm.
alpar@1142:   ///
kpeter@1188:   /// \warning This class is not to be used directly.
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@1186:   class Vf2Wizard : public TR {
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
kpeter@1188:     Vf2Wizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {}
madarasip@1141: 
madarasip@1141:     ///Copy constructor
kpeter@1188:     Vf2Wizard(const Base &b) : Base(b) {}
madarasip@1186: 
madarasip@1186:     ///Copy constructor
madarasip@1186:     Vf2Wizard(const Vf2Wizard &b) : Base(b) {}
madarasip@1141: 
madarasip@1141: 
madarasip@1141:     template<class T>
madarasip@1186:     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@1186:     Vf2Wizard< SetMappingBase<T> > mapping(const T &t) {
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@1186:         : Base(b), _node_eq(node_eq){
madarasip@1186:       }
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@1186:     Vf2Wizard< SetNodeEqBase<T> > nodeEq(const T &node_eq) {
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:     ///
madarasip@1186:     ///\param m1 An arbitrary \ref concepts::ReadMap "readable node map"
alpar@1144:     ///of g1.
madarasip@1186:     ///\param m2 An 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@1186:     nodeLabels(const M1 &m1,const M2 &m2){
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:     ///
madarasip@1186:     ///\sa See \ref MappingType for the possible values.
madarasip@1186:     Vf2Wizard<Base> &mappingType(MappingType m_type) {
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@1186:     Vf2Wizard<Base> &induced() {
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@1186:     Vf2Wizard<Base> &iso() {
madarasip@1141:       _mapping_type = ISOMORPH;
madarasip@1141:       return *this;
madarasip@1141:     }
madarasip@1141: 
madarasip@1186: 
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.
madarasip@1186:     ///\retval false if there is no mapping.
madarasip@1186:     bool run(){
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@1186: 
madarasip@1186:     ///Get a pointer to the generated Vf2 object.
madarasip@1186: 
madarasip@1186:     ///Gives a pointer to the generated Vf2 object.
madarasip@1186:     ///
madarasip@1186:     ///\return Pointer to the generated Vf2 object.
madarasip@1186:     ///\warning Don't forget to delete the referred Vf2 object after use.
madarasip@1186:     Vf2<Graph1, Graph2, Mapping, NodeEq >* getPtrToVf2Object() {
madarasip@1186:       if(Base::_local_mapping)
madarasip@1186:         Base::createMapping();
madarasip@1186:       Vf2<Graph1, Graph2, Mapping, NodeEq >* ptr =
madarasip@1186:         new Vf2<Graph1, Graph2, Mapping, NodeEq>
madarasip@1186:         (_g1, _g2, *reinterpret_cast<Mapping*>(_mapping), _node_eq);
madarasip@1186:       ptr->mappingType(_mapping_type);
madarasip@1186:       if(Base::_local_mapping)
madarasip@1186:         ptr->_deallocMappingAfterUse = true;
madarasip@1186:       return ptr;
madarasip@1186:     }
madarasip@1186: 
madarasip@1186:     ///Counts the number of mappings.
madarasip@1186: 
madarasip@1186:     ///This method counts the number of mappings.
madarasip@1186:     ///
madarasip@1186:     /// \return The number of mappings.
madarasip@1186:     int count() {
madarasip@1186:       if(Base::_local_mapping)
madarasip@1186:         Base::createMapping();
madarasip@1186: 
madarasip@1186:       Vf2<Graph1, Graph2, Mapping, NodeEq>
madarasip@1186:         alg(_g1, _g2, *reinterpret_cast<Mapping*>(_mapping), _node_eq);
madarasip@1186:       if(Base::_local_mapping)
madarasip@1186:         alg._deallocMappingAfterUse = true;
madarasip@1186:       alg.mappingType(_mapping_type);
madarasip@1186: 
madarasip@1186:       int ret = 0;
madarasip@1186:       while(alg.find())
madarasip@1186:         ++ret;
madarasip@1186: 
madarasip@1186:       return ret;
madarasip@1186:     }
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
madarasip@1186:   ///  // Find an embedding of graph g1 into graph g2
alpar@1142:   ///  ListGraph::NodeMap<ListGraph::Node> m(g);
madarasip@1186:   ///  vf2(g1,g2).mapping(m).run();
alpar@1142:   ///
madarasip@1186:   ///  // Check whether graphs g1 and g2 are isomorphic
madarasip@1186:   ///  bool is_iso = vf2(g1,g2).iso().run();
madarasip@1186:   ///
madarasip@1186:   ///  // Count the number of isomorphisms
madarasip@1186:   ///  int num_isos = vf2(g1,g2).iso().count();
madarasip@1186:   ///
madarasip@1186:   ///  // Iterate through all the induced subgraph mappings of graph g1 into g2
madarasip@1186:   ///  auto* myVf2 = vf2(g1,g2).mapping(m).nodeLabels(c1,c2)
madarasip@1186:   ///  .induced().getPtrToVf2Object();
madarasip@1186:   ///  while(myVf2->find()){
madarasip@1186:   ///    //process the current mapping m
madarasip@1186:   ///  }
madarasip@1186:   ///  delete myVf22;
alpar@1142:   ///\endcode
madarasip@1186:   ///\warning Don't forget to put the \ref Vf2Wizard::run() "run()",
madarasip@1186:   ///\ref Vf2Wizard::count() "count()" or
madarasip@1186:   ///the \ref Vf2Wizard::getPtrToVf2Object() "getPtrToVf2Object()"
alpar@1142:   ///to the end of the expression.
alpar@1142:   ///\sa Vf2Wizard
alpar@1142:   ///\sa Vf2
madarasip@1141:   template<class G1, class G2>
madarasip@1186:   Vf2Wizard<Vf2WizardBase<G1,G2> > vf2(const G1 &g1, const G2 &g2) {
madarasip@1141:     return Vf2Wizard<Vf2WizardBase<G1,G2> >(g1,g2);
madarasip@1141:   }
madarasip@1141: 
madarasip@1141: }
madarasip@1141: 
madarasip@1141: #endif