COIN-OR::LEMON - Graph Library

source: lemon-main/lemon/vf2.h

Last change on this file was 1194:e68f0ef37e77, checked in by Peter Kovacs <kpeter@…>, 2 years ago

Remove unused auxiliary class in Vf2 (#597)

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