COIN-OR::LEMON - Graph Library

source: lemon-main/lemon/vf2.h @ 1143:f85ee41c84bc

Last change on this file since 1143:f85ee41c84bc was 1143:f85ee41c84bc, checked in by Alpar Juttner <alpar@…>, 9 years ago

Bugfix in Vf2 - missing initialization (#597)

File size: 20.0 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#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
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
106    SUBGRAPH = 0,
107    /// Induced subgraph isomorphism
108    INDUCED = 1,
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.
117    ISOMORPH = 2
118  };
119
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
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.
154    NEQ _nEq;
155
156    typename G2::template NodeMap<int> _conn;
157    //Current mapping. We index it by the nodes of g1, and match[v] is
158    //a node of g2.
159    M &_mapping;
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
172    Vf2MappingType _mapping_type;
173
174    //cut the search tree
175    template<Vf2MappingType MT>
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
200    template<Vf2MappingType MT>
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);
209          if(_mapping[currNode]!=INVALID)
210            --_conn[_mapping[currNode]];
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);
228          if(_mapping[currNode]!=INVALID&&_conn[_mapping[currNode]]!=-1)
229            {
230              switch(MT)
231                {
232                case INDUCED:
233                case ISOMORPH:
234                  isIso=0;
235                  break;
236                case SUBGRAPH:
237                  if(_conn[_mapping[currNode]]<-1)
238                    isIso=0;
239                  break;
240                }
241              _conn[_mapping[currNode]]=-1;
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;
250      _mapping.set(n1,n2);
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;
259      _mapping.set(n1,INVALID);
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
282    template<Vf2MappingType MT>
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]);
299              //if _mapping[order[_depth]]!=INVALID, we dont use
300              //fstMatchedE
301              if(_mapping[order[_depth]]==INVALID)
302                for(; fstMatchedE!=INVALID &&
303                      _mapping[_g1.oppositeNode(order[_depth],
304                                              fstMatchedE)]==INVALID;
305                    ++fstMatchedE) ; //find fstMatchedE
306              if(fstMatchedE==INVALID||_mapping[order[_depth]]!=INVALID)
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
317                  if(_mapping[order[_depth]]!=INVALID)
318                    {
319                      n2=++typename G2::NodeIt(_g2,_mapping[order[_depth]]);
320                      subPair(order[_depth],_mapping[order[_depth]]);
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                {
343                  currPNode=_mapping[_g1.oppositeNode(order[_depth],
344                                                      fstMatchedE)];
345                  currEdgeIts[_depth]=typename G2::IncEdgeIt(_g2,currPNode);
346                }
347            }
348          else
349            {
350              currPNode=_g2.oppositeNode(_mapping[order[_depth]],
351                                         currEdgeIts[_depth]);
352              subPair(order[_depth],_mapping[order[_depth]]);
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:
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)),
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      for(typename G1::NodeIt n(g1);n!=INVALID;++n)
414        m[n]=INVALID;
415    }
416
417    ///Returns the current mapping type
418
419    ///Returns the current mapping type
420    ///
421    Vf2MappingType mappingType() const { return _mapping_type; }
422    ///Sets mapping type
423
424    ///Sets mapping type.
425    ///
426    ///The mapping type is set to \ref SUBGRAPH by default.
427    ///
428    ///\sa See \ref for the possible values.
429    void mappingType(Vf2MappingType m_type) { _mapping_type = m_type; }
430
431    ///Find a mapping
432
433    ///It finds a mapping between from g1 into g2 according to the mapping
434    ///type set by \ref mappingType(Vf2MappingType) "mappingType()".
435    ///
436    ///By subsequent calls, it returns all possible mappings one-by-one.
437    ///
438    ///\retval true if a mapping is found.
439    ///\retval false if there is no (more) mapping.
440    bool find()
441    {
442      switch(_mapping_type)
443        {
444        case SUBGRAPH:
445          return extMatch<SUBGRAPH>();
446        case INDUCED:
447          return extMatch<INDUCED>();
448        case ISOMORPH:
449          return extMatch<ISOMORPH>();
450        default:
451          return false;
452        }
453    }
454  };
455
456  template<class G1, class G2>
457  class Vf2WizardBase
458  {
459  protected:
460    typedef G1 Graph1;
461    typedef G2 Graph2;
462
463    const G1 &_g1;
464    const G2 &_g2;
465
466    Vf2MappingType _mapping_type;
467
468    typedef typename G1::template NodeMap<typename G2::Node> Mapping;
469    bool _local_mapping;
470    void *_mapping;
471    void createMapping()
472    {
473      _mapping = new Mapping(_g1);
474    }
475
476    typedef bits::vf2::AlwaysEq NodeEq;
477    NodeEq _node_eq;
478
479    Vf2WizardBase(const G1 &g1,const G2 &g2)
480      : _g1(g1), _g2(g2), _mapping_type(SUBGRAPH), _local_mapping(true) {}
481  };
482
483  /// Auxiliary class for the function-type interface of %VF2 algorithm.
484
485  /// This auxiliary class implements the named parameters of
486  /// \ref vf2() "function-type interface" of \ref Vf2 algorithm.
487  ///
488  /// \warning This class should only be used through the function \ref vf2().
489  ///
490  /// \tparam TR The traits class that defines various types used by the
491  /// algorithm.
492  template<class TR>
493  class Vf2Wizard : public TR
494  {
495    typedef TR Base;
496    typedef typename TR::Graph1 Graph1;
497    typedef typename TR::Graph2 Graph2;
498
499    typedef typename TR::Mapping Mapping;
500    typedef typename TR::NodeEq NodeEq;
501
502    using TR::_g1;
503    using TR::_g2;
504    using TR::_mapping_type;
505    using TR::_mapping;
506    using TR::_node_eq;
507
508  public:
509    ///Constructor
510    Vf2Wizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {}
511
512    ///Copy constructor
513    Vf2Wizard(const Base &b) : Base(b) {}
514
515
516    template<class T>
517    struct SetMappingBase : public Base {
518      typedef T Mapping;
519      SetMappingBase(const Base &b) : Base(b) {}
520    };
521
522    ///\brief \ref named-templ-param "Named parameter" for setting
523    ///the mapping.
524    ///
525    ///\ref named-templ-param "Named parameter" function for setting
526    ///the map that stores the found embedding.
527    template<class T>
528    Vf2Wizard< SetMappingBase<T> > mapping(const T &t)
529    {
530      Base::_mapping=reinterpret_cast<void*>(const_cast<T*>(&t));
531      Base::_local_mapping = false;
532      return Vf2Wizard<SetMappingBase<T> >(*this);
533    }
534
535    template<class NE>
536    struct SetNodeEqBase : public Base {
537      typedef NE NodeEq;
538      NodeEq _node_eq;
539      SetNodeEqBase(const Base &b, const NE &node_eq)
540        : Base(b), _node_eq(node_eq) {}
541    };
542
543    ///\brief \ref named-templ-param "Named parameter" for setting
544    ///the node equivalence relation.
545    ///
546    ///\ref named-templ-param "Named parameter" function for setting
547    ///the equivalence relation between the nodes.
548    ///
549    ///\param node_eq A bool-valued binary functor determinining
550    ///whether a node is mappable to another. By default it is an
551    ///always true operator.
552    template<class T>
553    Vf2Wizard< SetNodeEqBase<T> > nodeEq(const T &node_eq)
554    {
555      return Vf2Wizard<SetNodeEqBase<T> >(SetNodeEqBase<T>(*this,node_eq));
556    }
557
558    ///\brief \ref named-templ-param "Named parameter" for setting
559    ///the node labels.
560    ///
561    ///\ref named-templ-param "Named parameter" function for setting
562    ///the node labels defining equivalence relation between them.
563    ///
564    ///\param m1 It is arbitrary \ref ReadMap "readable node map" of g1.
565    ///\param m1 It is arbitrary \ref ReadMap "readable node map" of g2.
566    ///
567    ///The value type of these maps must be equal comparable.
568    template<class M1, class M2>
569    Vf2Wizard< SetNodeEqBase<bits::vf2::MapEq<M1,M2> > >
570    nodeLabels(const M1 &m1,const M2 &m2)
571    {
572      return nodeEq(bits::vf2::MapEq<M1,M2>(m1,m2));
573    }
574
575    ///\brief \ref named-templ-param "Named parameter" for setting
576    ///the mapping type.
577    ///
578    ///\ref named-templ-param "Named parameter" for setting
579    ///the mapping type.
580    ///
581    ///The mapping type is set to \ref SUBGRAPH by default.
582    ///
583    ///\sa See \ref for the possible values.
584    Vf2Wizard<Base> &mappingType(Vf2MappingType m_type)
585    {
586      _mapping_type = m_type;
587      return *this;
588    }
589
590    ///\brief \ref named-templ-param "Named parameter" for setting
591    ///the mapping type to \ref INDUCED.
592    ///
593    ///\ref named-templ-param "Named parameter" for setting
594    ///the mapping type to \ref INDUCED.
595    Vf2Wizard<Base> &induced()
596    {
597      _mapping_type = INDUCED;
598      return *this;
599    }
600
601    ///\brief \ref named-templ-param "Named parameter" for setting
602    ///the mapping type to \ref ISOMORPH.
603    ///
604    ///\ref named-templ-param "Named parameter" for setting
605    ///the mapping type to \ref ISOMORPH.
606    Vf2Wizard<Base> &iso()
607    {
608      _mapping_type = ISOMORPH;
609      return *this;
610    }
611
612    ///Runs VF2 algorithm.
613
614    ///This method runs VF2 algorithm.
615    ///
616    ///\retval true if a mapping is found.
617    ///\retval false if there is no (more) mapping.
618    bool run()
619    {
620      if(Base::_local_mapping)
621        Base::createMapping();
622
623      Vf2<Graph1, Graph2, Mapping, NodeEq >
624        alg(_g1, _g2, *reinterpret_cast<Mapping*>(_mapping), _node_eq);
625
626      alg.mappingType(_mapping_type);
627
628      bool ret = alg.find();
629
630      if(Base::_local_mapping)
631        delete reinterpret_cast<Mapping*>(_mapping);
632
633      return ret;
634    }
635  };
636
637  ///Function-type interface for VF2 algorithm.
638
639  /// \ingroup graph_isomorphism
640  ///Function-type interface for VF2 algorithm \cite cordella2004sub.
641  ///
642  ///This function has several \ref named-func-param "named parameters"
643  ///declared as the members of class \ref Vf2Wizard.
644  ///The following examples show how to use these parameters.
645  ///\code
646  ///  // Find an embedding of graph g into graph h
647  ///  ListGraph::NodeMap<ListGraph::Node> m(g);
648  ///  vf2(g,h).mapping(m).run();
649  ///
650  ///  // Check whether graphs g and h are isomorphic
651  ///  bool is_iso = vf2(g,h).iso().run();
652  ///\endcode
653  ///\warning Don't forget to put the \ref Vf2Wizard::run() "run()"
654  ///to the end of the expression.
655  ///\sa Vf2Wizard
656  ///\sa Vf2
657  template<class G1, class G2>
658  Vf2Wizard<Vf2WizardBase<G1,G2> > vf2(const G1 &g1, const G2 &g2)
659  {
660    return Vf2Wizard<Vf2WizardBase<G1,G2> >(g1,g2);
661  }
662
663}
664
665#endif
Note: See TracBrowser for help on using the repository browser.