COIN-OR::LEMON - Graph Library

source: lemon/lemon/vf2.h @ 1351:2f479109a71d

Last change on this file since 1351:2f479109a71d was 1351:2f479109a71d, checked in by Alpar Juttner <alpar@…>, 4 years ago

Documentation for VF2 (#597)

The implementation of this feature was sponsored by QuantumBio? Inc.

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