1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2015-2017
6 * EMAXA Kutato-fejleszto Kft. (EMAXA Research Ltd.)
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.
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
21 ///\ingroup graph_properties
23 ///\brief VF2 algorithm \cite cordella2004sub.
25 #include <lemon/core.h>
26 #include <lemon/concepts/graph.h>
27 #include <lemon/dfs.h>
28 #include <lemon/bfs.h>
29 #include <lemon/bits/vf2_internals.h>
39 template<class T1, class T2>
40 bool operator()(T1&, T2&) const {
45 template<class M1, class M2>
50 MapEq(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) { }
51 bool operator()(typename M1::Key k1, typename M2::Key k2) const {
52 return _m1[k1] == _m2[k2];
57 class DfsLeaveOrder : public DfsVisitor<G> {
59 std::vector<typename G::Node> &_order;
62 DfsLeaveOrder(const G &g, std::vector<typename G::Node> &order)
63 : i(countNodes(g)), _g(g), _order(order) { }
64 void leave(const typename G::Node &node) {
70 class BfsLeaveOrder : public BfsVisitor<G> {
73 std::vector<typename G::Node> &_order;
75 BfsLeaveOrder(const G &g, std::vector<typename G::Node> &order)
76 : i(0), _g(g), _order(order){
78 void process(const typename G::Node &node) {
86 ///%VF2 algorithm class.
88 ///\ingroup graph_isomorphism This class provides an efficient
89 ///implementation of the %VF2 algorithm \cite cordella2004sub
90 ///for variants of the (Sub)graph Isomorphism problem.
92 ///There is also a \ref vf2() "function-type interface" called \ref vf2()
93 ///for the %VF2 algorithm, which is probably more convenient in most
96 ///\tparam G1 The type of the graph to be embedded.
97 ///The default type is \ref ListGraph.
98 ///\tparam G2 The type of the graph g1 will be embedded into.
99 ///The default type is \ref ListGraph.
100 ///\tparam M The type of the NodeMap storing the mapping.
101 ///By default, it is G1::NodeMap<G2::Node>
102 ///\tparam NEQ A bool-valued binary functor determinining whether a node is
103 ///mappable to another. By default, it is an always-true operator.
107 template<class G1, class G2, class M, class NEQ >
109 template<class G1 = ListGraph,
110 class G2 = ListGraph,
111 class M = typename G1::template NodeMap<G2::Node>,
112 class NEQ = bits::vf2::AlwaysEq >
115 //The graph to be embedded
118 //The graph into which g1 is to be embedded
121 //Functor with bool operator()(G1::Node,G2::Node), which returns 1
122 //if and only if the two nodes are equivalent
125 //Current depth in the DFS tree.
128 //The current mapping. _mapping[v1]=v2 iff v1 has been mapped to v2,
129 //where v1 is a node of G1 and v2 is a node of G2
132 //_order[i] is the node of g1 for which a pair is searched if depth=i
133 std::vector<typename G1::Node> _order;
135 //_conn[v2] = number of covered neighbours of v2
136 typename G2::template NodeMap<int> _conn;
138 //_currEdgeIts[i] is the last used edge iterator in the i-th
139 //depth to find a pair for node _order[i]
140 std::vector<typename G2::IncEdgeIt> _currEdgeIts;
142 //lookup tables for cutting the searchtree
143 typename G1::template NodeMap<int> _rNew1t, _rInOut1t;
145 MappingType _mapping_type;
147 bool _deallocMappingAfterUse;
149 //cut the search tree
150 template<MappingType MT>
151 bool cut(const typename G1::Node n1,const typename G2::Node n2) const {
152 int rNew2=0,rInOut2=0;
153 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
154 const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
155 if(_conn[currNode]>0)
157 else if(MT!=SUBGRAPH&&_conn[currNode]==0)
162 return _rInOut1t[n1]<=rInOut2&&_rNew1t[n1]<=rNew2;
164 return _rInOut1t[n1]<=rInOut2;
166 return _rInOut1t[n1]==rInOut2&&_rNew1t[n1]==rNew2;
172 template<MappingType MT>
173 bool feas(const typename G1::Node n1,const typename G2::Node n2) {
177 for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
178 const typename G1::Node& currNode=_g1.oppositeNode(n1,e1);
179 if(_mapping[currNode]!=INVALID)
180 --_conn[_mapping[currNode]];
183 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
184 int& connCurrNode = _conn[_g2.oppositeNode(n2,e2)];
187 else if(MT!=SUBGRAPH&&connCurrNode==-1) {
193 for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
194 const typename G2::Node& currNodePair=_mapping[_g1.oppositeNode(n1,e1)];
195 int& connCurrNodePair=_conn[currNodePair];
196 if(currNodePair!=INVALID&&connCurrNodePair!=-1) {
203 if(connCurrNodePair<-1)
210 return isIso&&cut<MT>(n1,n2);
213 void addPair(const typename G1::Node n1,const typename G2::Node n2) {
216 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
217 int& currConn = _conn[_g2.oppositeNode(n2,e2)];
223 void subPair(const typename G1::Node n1,const typename G2::Node n2) {
225 _mapping.set(n1,INVALID);
226 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
227 int& currConn = _conn[_g2.oppositeNode(n2,e2)];
230 else if(currConn==-1)
236 // we will find pairs for the nodes of g1 in this order
238 // bits::vf2::DfsLeaveOrder<G1> v(_g1,_order);
239 // DfsVisit<G1,bits::vf2::DfsLeaveOrder<G1> >dfs(_g1, v);
242 //it is more efficient in practice than DFS
243 bits::vf2::BfsLeaveOrder<G1> v(_g1,_order);
244 BfsVisit<G1,bits::vf2::BfsLeaveOrder<G1> >bfs(_g1, v);
248 template<MappingType MT>
251 if(_depth==static_cast<int>(_order.size())) {
252 //all nodes of g1 are mapped to nodes of g2
256 typename G1::Node& nodeOfDepth = _order[_depth];
257 const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth];
258 typename G2::IncEdgeIt &edgeItOfDepth = _currEdgeIts[_depth];
259 //the node of g2 whose neighbours are the candidates for
260 //the pair of nodeOfDepth
261 typename G2::Node currPNode;
262 if(edgeItOfDepth==INVALID) {
263 typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth);
264 //if pairOfNodeOfDepth!=INVALID, we don't use fstMatchedE
265 if(pairOfNodeOfDepth==INVALID) {
266 for(; fstMatchedE!=INVALID &&
267 _mapping[_g1.oppositeNode(nodeOfDepth,
268 fstMatchedE)]==INVALID;
269 ++fstMatchedE) ; //find fstMatchedE
271 if(fstMatchedE==INVALID||pairOfNodeOfDepth!=INVALID) {
272 //We found no covered neighbours, this means that
273 //the graph is not connected (or _depth==0). Each
274 //uncovered (and there are some other properties due
275 //to the spec. problem types) node of g2 is
276 //candidate. We can read the iterator of the last
277 //tried node from the match if it is not the first
278 //try (match[nodeOfDepth]!=INVALID)
279 typename G2::NodeIt n2(_g2);
280 //if it's not the first try
281 if(pairOfNodeOfDepth!=INVALID) {
282 n2=++typename G2::NodeIt(_g2,pairOfNodeOfDepth);
283 subPair(nodeOfDepth,pairOfNodeOfDepth);
285 for(; n2!=INVALID; ++n2)
287 if(_conn[n2]==0&&feas<MT>(nodeOfDepth,n2))
290 else if(_conn[n2]>=0&&feas<MT>(nodeOfDepth,n2))
292 // n2 is the next candidate
294 addPair(nodeOfDepth,n2);
297 else // there are no more candidates
302 currPNode=_mapping[_g1.oppositeNode(nodeOfDepth,
304 edgeItOfDepth=typename G2::IncEdgeIt(_g2,currPNode);
308 currPNode=_g2.oppositeNode(pairOfNodeOfDepth,
310 subPair(nodeOfDepth,pairOfNodeOfDepth);
313 for(; edgeItOfDepth!=INVALID; ++edgeItOfDepth) {
314 const typename G2::Node currNode =
315 _g2.oppositeNode(currPNode, edgeItOfDepth);
316 if(_conn[currNode]>0&&feas<MT>(nodeOfDepth,currNode)) {
317 addPair(nodeOfDepth,currNode);
321 edgeItOfDepth==INVALID?--_depth:++_depth;
326 //calculate the lookup table for cutting the search tree
327 void initRNew1tRInOut1t() {
328 typename G1::template NodeMap<int> tmp(_g1,0);
329 for(unsigned int i=0; i<_order.size(); ++i) {
330 const typename G1::Node& orderI = _order[i];
332 for(typename G1::IncEdgeIt e1(_g1,orderI); e1!=INVALID; ++e1) {
333 const typename G1::Node currNode=_g1.oppositeNode(orderI,e1);
336 else if(tmp[currNode]==0)
339 for(typename G1::IncEdgeIt e1(_g1,orderI); e1!=INVALID; ++e1) {
340 const typename G1::Node currNode=_g1.oppositeNode(orderI,e1);
341 if(tmp[currNode]!=-1)
351 ///\param g1 The graph to be embedded into \e g2.
352 ///\param g2 The graph \e g1 will be embedded into.
353 ///\param m \ref concepts::ReadWriteMap "read-write" NodeMap
354 ///storing the found mapping.
355 ///\param neq A bool-valued binary functor determining whether a node is
356 ///mappable to another. By default it is an always true operator.
357 Vf2(const G1 &g1, const G2 &g2, M &m, const NEQ &neq = NEQ() ) :
358 _g1(g1), _g2(g2), _nEq(neq), _depth(0), _mapping(m),
359 _order(countNodes(g1)), _conn(g2,0),
360 _currEdgeIts(countNodes(g1),INVALID), _rNew1t(g1,0), _rInOut1t(g1,0),
361 _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0)
364 initRNew1tRInOut1t();
365 for(typename G1::NodeIt n(g1);n!=INVALID;++n)
375 if(_deallocMappingAfterUse)
379 ///Returns the current mapping type
381 ///Returns the current mapping type
383 MappingType mappingType() const {
384 return _mapping_type;
388 ///Sets mapping type.
390 ///The mapping type is set to \ref SUBGRAPH by default.
392 ///\sa See \ref MappingType for the possible values.
393 void mappingType(MappingType m_type) {
394 _mapping_type = m_type;
399 ///It finds a mapping from g1 into g2 according to the mapping
400 ///type set by \ref mappingType(MappingType) "mappingType()".
402 ///By subsequent calls, it returns all possible mappings one-by-one.
404 ///\retval true if a mapping is found.
405 ///\retval false if there is no (more) mapping.
407 switch(_mapping_type) {
409 return extMatch<SUBGRAPH>();
411 return extMatch<INDUCED>();
413 return extMatch<ISOMORPH>();
420 template<class G1, class G2>
421 class Vf2WizardBase {
429 MappingType _mapping_type;
431 typedef typename G1::template NodeMap<typename G2::Node> Mapping;
434 void createMapping() {
435 _mapping = new Mapping(_g1);
438 void *myVf2; //used in Vf2Wizard::find
441 typedef bits::vf2::AlwaysEq NodeEq;
444 Vf2WizardBase(const G1 &g1,const G2 &g2)
445 : _g1(g1), _g2(g2), _mapping_type(SUBGRAPH), _local_mapping(true) { }
449 /// Auxiliary class for the function-type interface of %VF2 algorithm.
451 /// This auxiliary class implements the named parameters of
452 /// \ref vf2() "function-type interface" of \ref Vf2 algorithm.
454 /// \warning This class is not to be used directly.
456 /// \tparam TR The traits class that defines various types used by the
459 class Vf2Wizard : public TR {
461 typedef typename TR::Graph1 Graph1;
462 typedef typename TR::Graph2 Graph2;
464 typedef typename TR::Mapping Mapping;
465 typedef typename TR::NodeEq NodeEq;
469 using TR::_mapping_type;
475 Vf2Wizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {}
478 Vf2Wizard(const Base &b) : Base(b) {}
481 Vf2Wizard(const Vf2Wizard &b) : Base(b) {}
485 struct SetMappingBase : public Base{
487 SetMappingBase(const Base &b) : Base(b) {}
490 ///\brief \ref named-templ-param "Named parameter" for setting
493 ///\ref named-templ-param "Named parameter" function for setting
494 ///the map that stores the found embedding.
496 Vf2Wizard< SetMappingBase<T> > mapping(const T &t) {
497 Base::_mapping=reinterpret_cast<void*>(const_cast<T*>(&t));
498 Base::_local_mapping = false;
499 return Vf2Wizard<SetMappingBase<T> >(*this);
503 struct SetNodeEqBase : public Base {
506 SetNodeEqBase(const Base &b, const NE &node_eq)
507 : Base(b), _node_eq(node_eq){
511 ///\brief \ref named-templ-param "Named parameter" for setting
512 ///the node equivalence relation.
514 ///\ref named-templ-param "Named parameter" function for setting
515 ///the equivalence relation between the nodes.
517 ///\param node_eq A bool-valued binary functor determinining
518 ///whether a node is mappable to another. By default it is an
519 ///always true operator.
521 Vf2Wizard< SetNodeEqBase<T> > nodeEq(const T &node_eq) {
522 return Vf2Wizard<SetNodeEqBase<T> >(SetNodeEqBase<T>(*this,node_eq));
525 ///\brief \ref named-templ-param "Named parameter" for setting
528 ///\ref named-templ-param "Named parameter" function for setting
529 ///the node labels defining equivalence relation between them.
531 ///\param m1 An arbitrary \ref concepts::ReadMap "readable node map"
533 ///\param m2 An arbitrary \ref concepts::ReadMap "readable node map"
536 ///The value type of these maps must be equal comparable.
537 template<class M1, class M2>
538 Vf2Wizard< SetNodeEqBase<bits::vf2::MapEq<M1,M2> > >
539 nodeLabels(const M1 &m1,const M2 &m2){
540 return nodeEq(bits::vf2::MapEq<M1,M2>(m1,m2));
543 ///\brief \ref named-templ-param "Named parameter" for setting
546 ///\ref named-templ-param "Named parameter" for setting
549 ///The mapping type is set to \ref SUBGRAPH by default.
551 ///\sa See \ref MappingType for the possible values.
552 Vf2Wizard<Base> &mappingType(MappingType m_type) {
553 _mapping_type = m_type;
557 ///\brief \ref named-templ-param "Named parameter" for setting
558 ///the mapping type to \ref INDUCED.
560 ///\ref named-templ-param "Named parameter" for setting
561 ///the mapping type to \ref INDUCED.
562 Vf2Wizard<Base> &induced() {
563 _mapping_type = INDUCED;
567 ///\brief \ref named-templ-param "Named parameter" for setting
568 ///the mapping type to \ref ISOMORPH.
570 ///\ref named-templ-param "Named parameter" for setting
571 ///the mapping type to \ref ISOMORPH.
572 Vf2Wizard<Base> &iso() {
573 _mapping_type = ISOMORPH;
578 ///Runs VF2 algorithm.
580 ///This method runs VF2 algorithm.
582 ///\retval true if a mapping is found.
583 ///\retval false if there is no mapping.
585 if(Base::_local_mapping)
586 Base::createMapping();
588 Vf2<Graph1, Graph2, Mapping, NodeEq >
589 alg(_g1, _g2, *reinterpret_cast<Mapping*>(_mapping), _node_eq);
591 alg.mappingType(_mapping_type);
593 bool ret = alg.find();
595 if(Base::_local_mapping)
596 delete reinterpret_cast<Mapping*>(_mapping);
601 ///Get a pointer to the generated Vf2 object.
603 ///Gives a pointer to the generated Vf2 object.
605 ///\return Pointer to the generated Vf2 object.
606 ///\warning Don't forget to delete the referred Vf2 object after use.
607 Vf2<Graph1, Graph2, Mapping, NodeEq >* getPtrToVf2Object() {
608 if(Base::_local_mapping)
609 Base::createMapping();
610 Vf2<Graph1, Graph2, Mapping, NodeEq >* ptr =
611 new Vf2<Graph1, Graph2, Mapping, NodeEq>
612 (_g1, _g2, *reinterpret_cast<Mapping*>(_mapping), _node_eq);
613 ptr->mappingType(_mapping_type);
614 if(Base::_local_mapping)
615 ptr->_deallocMappingAfterUse = true;
619 ///Counts the number of mappings.
621 ///This method counts the number of mappings.
623 /// \return The number of mappings.
625 if(Base::_local_mapping)
626 Base::createMapping();
628 Vf2<Graph1, Graph2, Mapping, NodeEq>
629 alg(_g1, _g2, *reinterpret_cast<Mapping*>(_mapping), _node_eq);
630 if(Base::_local_mapping)
631 alg._deallocMappingAfterUse = true;
632 alg.mappingType(_mapping_type);
642 ///Function-type interface for VF2 algorithm.
644 /// \ingroup graph_isomorphism
645 ///Function-type interface for VF2 algorithm \cite cordella2004sub.
647 ///This function has several \ref named-func-param "named parameters"
648 ///declared as the members of class \ref Vf2Wizard.
649 ///The following examples show how to use these parameters.
651 /// // Find an embedding of graph g1 into graph g2
652 /// ListGraph::NodeMap<ListGraph::Node> m(g);
653 /// vf2(g1,g2).mapping(m).run();
655 /// // Check whether graphs g1 and g2 are isomorphic
656 /// bool is_iso = vf2(g1,g2).iso().run();
658 /// // Count the number of isomorphisms
659 /// int num_isos = vf2(g1,g2).iso().count();
661 /// // Iterate through all the induced subgraph mappings of graph g1 into g2
662 /// auto* myVf2 = vf2(g1,g2).mapping(m).nodeLabels(c1,c2)
663 /// .induced().getPtrToVf2Object();
664 /// while(myVf2->find()){
665 /// //process the current mapping m
669 ///\warning Don't forget to put the \ref Vf2Wizard::run() "run()",
670 ///\ref Vf2Wizard::count() "count()" or
671 ///the \ref Vf2Wizard::getPtrToVf2Object() "getPtrToVf2Object()"
672 ///to the end of the expression.
675 template<class G1, class G2>
676 Vf2Wizard<Vf2WizardBase<G1,G2> > vf2(const G1 &g1, const G2 &g2) {
677 return Vf2Wizard<Vf2WizardBase<G1,G2> >(g1,g2);