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 madarasip@1141: #include madarasip@1141: #include madarasip@1141: #include madarasip@1186: #include madarasip@1141: madarasip@1141: #include 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 madarasip@1186: bool operator()(T1&, T2&) const { madarasip@1141: return true; madarasip@1141: } madarasip@1141: }; madarasip@1141: madarasip@1141: template 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 madarasip@1186: class DfsLeaveOrder : public DfsVisitor { madarasip@1141: const G &_g; madarasip@1141: std::vector &_order; madarasip@1141: int i; madarasip@1141: public: madarasip@1141: DfsLeaveOrder(const G &g, std::vector &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 madarasip@1186: class BfsLeaveOrder : public BfsVisitor { madarasip@1141: int i; madarasip@1141: const G &_g; madarasip@1141: std::vector &_order; madarasip@1141: public: madarasip@1141: BfsLeaveOrder(const G &g, std::vector &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 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 alpar@1142: #else kpeter@1191: template, 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 _order; kpeter@1189: kpeter@1189: //_conn[v2] = number of covered neighbours of v2 kpeter@1189: typename G2::template NodeMap _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 _currEdgeIts; kpeter@1189: madarasip@1186: //lookup tables for cutting the searchtree kpeter@1189: typename G1::template NodeMap _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 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 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(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 v(_g1,_order); madarasip@1141: // DfsVisit >dfs(_g1, v); madarasip@1141: // dfs.run(); madarasip@1141: madarasip@1141: //it is more efficient in practice than DFS kpeter@1189: bits::vf2::BfsLeaveOrder v(_g1,_order); madarasip@1141: BfsVisit >bfs(_g1, v); madarasip@1141: bfs.run(); madarasip@1141: } madarasip@1141: madarasip@1186: template madarasip@1186: bool extMatch() { madarasip@1186: while(_depth>=0) { kpeter@1189: if(_depth==static_cast(_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(nodeOfDepth,n2)) madarasip@1186: break; madarasip@1186: } madarasip@1186: else if(_conn[n2]>=0&&feas(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(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 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(); madarasip@1186: case INDUCED: madarasip@1186: return extMatch(); madarasip@1186: case ISOMORPH: madarasip@1186: return extMatch(); madarasip@1186: default: madarasip@1186: return false; madarasip@1186: } madarasip@1141: } madarasip@1141: }; madarasip@1141: madarasip@1141: template 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 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 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 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 madarasip@1186: Vf2Wizard< SetMappingBase > mapping(const T &t) { madarasip@1141: Base::_mapping=reinterpret_cast(const_cast(&t)); madarasip@1141: Base::_local_mapping = false; madarasip@1141: return Vf2Wizard >(*this); madarasip@1141: } madarasip@1141: madarasip@1141: template 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 madarasip@1186: Vf2Wizard< SetNodeEqBase > nodeEq(const T &node_eq) { madarasip@1141: return Vf2Wizard >(SetNodeEqBase(*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 madarasip@1141: Vf2Wizard< SetNodeEqBase > > madarasip@1186: nodeLabels(const M1 &m1,const M2 &m2){ madarasip@1141: return nodeEq(bits::vf2::MapEq(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 &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 &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 &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 madarasip@1141: alg(_g1, _g2, *reinterpret_cast(_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); 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* getPtrToVf2Object() { madarasip@1186: if(Base::_local_mapping) madarasip@1186: Base::createMapping(); madarasip@1186: Vf2* ptr = madarasip@1186: new Vf2 madarasip@1186: (_g1, _g2, *reinterpret_cast(_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 madarasip@1186: alg(_g1, _g2, *reinterpret_cast(_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 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 madarasip@1186: Vf2Wizard > vf2(const G1 &g1, const G2 &g2) { madarasip@1141: return Vf2Wizard >(g1,g2); madarasip@1141: } madarasip@1141: madarasip@1141: } madarasip@1141: madarasip@1141: #endif