COIN-OR::LEMON - Graph Library

source: lemon/lemon/vf2.h @ 1370:f51c01a1b88e

Last change on this file since 1370:f51c01a1b88e was 1370:f51c01a1b88e, checked in by Alpar Juttner <alpar@…>, 8 years ago

Remove unnecessary test include from lemon/vf2.h (#603)

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