COIN-OR::LEMON - Graph Library

source: lemon-main/lemon/vf2pp.h

Last change on this file was 1195:73e29215aaa4, checked in by Alpar Juttner <alpar@…>, 5 years ago

Add citation for Vf2pp (#597)

File size: 28.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_VF2PP_H
19#define LEMON_VF2PP_H
20
21///\ingroup graph_properties
22///\file
23///\brief VF2 Plus Plus algorithm.
24
25#include <lemon/core.h>
26#include <lemon/concepts/graph.h>
27#include <lemon/bits/vf2_internals.h>
28
29#include <vector>
30#include <algorithm>
31#include <utility>
32
33namespace lemon {
34
35  ///%VF2 Plus Plus algorithm class \cite VF2PP.
36
37  ///\ingroup graph_isomorphism This class provides an efficient
38  ///implementation of the %VF2 Plus Plus algorithm \cite VF2PP
39  ///for variants of the (Sub)graph Isomorphism problem.
40  ///
41  ///There is also a \ref vf2pp() "function-type interface" called
42  ///\ref vf2pp() for the %VF2 Plus Plus algorithm, which is probably
43  ///more convenient in most use cases.
44  ///
45  ///\tparam G1 The type of the graph to be embedded.
46  ///The default type is \ref ListGraph.
47  ///\tparam G2 The type of the graph g1 will be embedded into.
48  ///The default type is \ref ListGraph.
49  ///\tparam M The type of the NodeMap storing the mapping.
50  ///By default, it is G1::NodeMap<G2::Node>
51  ///\tparam M1 The type of the NodeMap storing the integer node labels of G1.
52  ///The labels must be the numbers {0,1,2,..,K-1}, where K is the number of
53  ///different labels. By default, it is G1::NodeMap<int>.
54  ///\tparam M2 The type of the NodeMap storing the integer node labels of G2.
55  ///The labels must be the numbers {0,1,2,..,K-1}, where K is the number of
56  ///different labels. By default, it is G2::NodeMap<int>.
57  ///
58  ///\sa vf2pp()
59#ifdef DOXYGEN
60  template<class G1, class G2, class M, class M1, class M2 >
61#else
62  template<class G1 = ListGraph,
63           class G2 = ListGraph,
64           class M = typename G1::template NodeMap<G2::Node>,
65           class M1 = typename G1::template NodeMap<int>,
66           class M2 = typename G2::template NodeMap<int> >
67#endif
68  class Vf2pp {
69    //The graph to be embedded
70    const G1 &_g1;
71
72    //The graph into which g1 is to be embedded
73    const G2 &_g2;
74
75    //Current depth in the search tree
76    int _depth;
77
78    //The current mapping. _mapping[v1]=v2 iff v1 has been mapped to v2,
79    //where v1 is a node of G1 and v2 is a node of G2
80    M &_mapping;
81
82    //_order[i] is a node of g1 for which a pair is searched if depth=i
83    std::vector<typename G1::Node> _order;
84
85    //_conn[v2] = number of covered neighbours of v2
86    typename G2::template NodeMap<int> _conn;
87
88    //_currEdgeIts[i] is the last used edge iterator in the i-th
89    //depth to find a pair for node _order[i]
90    std::vector<typename G2::IncEdgeIt> _currEdgeIts;
91 
92    //_rNewLabels1[v] is a pair of form
93    //(label; num. of uncov. nodes with such label and no covered neighbours)
94    typename G1::template NodeMap<std::vector<std::pair<int,int> > >
95    _rNewLabels1;
96
97    //_rInOutLabels1[v] is the number of covered neighbours of v for each label
98    //in form (label,number of such labels)
99    typename G1::template NodeMap<std::vector<std::pair<int,int> > >
100    _rInOutLabels1;
101
102    //_intLabels1[v]==i means that node v has label i in _g1
103    //(i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
104    M1 &_intLabels1;
105
106    //_intLabels2[v]==i means that node v has label i in _g2
107    //(i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
108    M2 &_intLabels2;
109
110    //largest label
111    const int _maxLabel;
112
113    //lookup tables for manipulating with label class cardinalities
114    //(after use they have to be reset to 0..0)
115    std::vector<int> _labelTmp1,_labelTmp2;
116
117    MappingType _mapping_type;
118
119    //indicates whether the mapping or the labels must be deleted in the destructor
120    bool _deallocMappingAfterUse,_deallocLabelsAfterUse;
121
122
123    //improved cutting function
124    template<MappingType MT>
125    bool cutByLabels(const typename G1::Node n1,const typename G2::Node n2) {
126      for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
127        const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
128        if(_conn[currNode]>0)
129          --_labelTmp1[_intLabels2[currNode]];
130        else if(MT!=SUBGRAPH&&_conn[currNode]==0)
131          --_labelTmp2[_intLabels2[currNode]];
132      }
133
134      bool ret=1;
135      if(ret) {
136        for(unsigned int i = 0; i < _rInOutLabels1[n1].size(); ++i)
137          _labelTmp1[_rInOutLabels1[n1][i].first]+=_rInOutLabels1[n1][i].second;
138
139        if(MT!=SUBGRAPH)
140          for(unsigned int i = 0; i < _rNewLabels1[n1].size(); ++i)
141            _labelTmp2[_rNewLabels1[n1][i].first]+=_rNewLabels1[n1][i].second;
142
143        switch(MT) {
144        case INDUCED:
145          for(unsigned int i = 0; i < _rInOutLabels1[n1].size(); ++i)
146            if(_labelTmp1[_rInOutLabels1[n1][i].first]>0) {
147              ret=0;
148              break;
149            }
150          if(ret)
151            for(unsigned int i = 0; i < _rNewLabels1[n1].size(); ++i)
152              if(_labelTmp2[_rNewLabels1[n1][i].first]>0) {
153                ret=0;
154                break;
155              }
156          break;
157        case SUBGRAPH:
158          for(unsigned int i = 0; i < _rInOutLabels1[n1].size(); ++i)
159            if(_labelTmp1[_rInOutLabels1[n1][i].first]>0) {
160              ret=0;
161              break;
162            }
163          break;
164        case ISOMORPH:
165          for(unsigned int i = 0; i < _rInOutLabels1[n1].size(); ++i)
166            if(_labelTmp1[_rInOutLabels1[n1][i].first]!=0) {
167              ret=0;
168              break;
169            }
170          if(ret)
171            for(unsigned int i = 0; i < _rNewLabels1[n1].size(); ++i)
172              if(_labelTmp2[_rNewLabels1[n1][i].first]!=0) {
173                ret=0;
174                break;
175              }
176          break;
177        default:
178          return false;
179        }
180        for(unsigned int i = 0; i < _rInOutLabels1[n1].size(); ++i)
181          _labelTmp1[_rInOutLabels1[n1][i].first]=0;
182
183        if(MT!=SUBGRAPH)
184          for(unsigned int i = 0; i < _rNewLabels1[n1].size(); ++i)
185            _labelTmp2[_rNewLabels1[n1][i].first]=0;
186      }
187
188      for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
189        const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
190        _labelTmp1[_intLabels2[currNode]]=0;
191        if(MT!=SUBGRAPH&&_conn[currNode]==0)
192          _labelTmp2[_intLabels2[currNode]]=0;
193      }
194
195      return ret;
196    }
197
198
199    //try to exclude the matching of n1 and n2
200    template<MappingType MT>
201    bool feas(const typename G1::Node n1,const typename G2::Node n2) {
202      if(_intLabels1[n1]!=_intLabels2[n2])
203        return 0;
204
205      for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
206        const typename G1::Node& currNode=_g1.oppositeNode(n1,e1);
207        if(_mapping[currNode]!=INVALID)
208          --_conn[_mapping[currNode]];
209      }
210
211      bool isIso=1;
212      for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
213        int& connCurrNode = _conn[_g2.oppositeNode(n2,e2)];
214        if(connCurrNode<-1)
215          ++connCurrNode;
216        else if(MT!=SUBGRAPH&&connCurrNode==-1) {
217          isIso=0;
218          break;
219        }
220      }
221
222      if(isIso)
223        for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
224          const typename G2::Node& currNodePair =
225            _mapping[_g1.oppositeNode(n1,e1)];
226          int& connCurrNodePair=_conn[currNodePair];
227          if(currNodePair!=INVALID&&connCurrNodePair!=-1) {
228            switch(MT){
229            case INDUCED:
230            case ISOMORPH:
231              isIso=0;
232              break;
233            case SUBGRAPH:
234              if(connCurrNodePair<-1)
235                isIso=0;
236              break;
237            }
238            connCurrNodePair=-1;
239          }
240        }
241      else
242        for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
243          const typename G2::Node currNode=_mapping[_g1.oppositeNode(n1,e1)];
244          if(currNode!=INVALID/*&&_conn[currNode]!=-1*/)
245            _conn[currNode]=-1;
246        }
247
248      return isIso&&cutByLabels<MT>(n1,n2);
249    }
250
251    //maps n1 to n2
252    void addPair(const typename G1::Node n1,const typename G2::Node n2) {
253      _conn[n2]=-1;
254      _mapping.set(n1,n2);
255      for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
256        int& currConn = _conn[_g2.oppositeNode(n2,e2)];
257        if(currConn!=-1)
258          ++currConn;
259      }
260    }
261
262    //removes mapping of n1 to n2
263    void subPair(const typename G1::Node n1,const typename G2::Node n2) {
264      _conn[n2]=0;
265      _mapping.set(n1,INVALID);
266      for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2){
267        int& currConn = _conn[_g2.oppositeNode(n2,e2)];
268        if(currConn>0)
269          --currConn;
270        else if(currConn==-1)
271          ++_conn[n2];
272      }
273    }
274
275    void processBfsTree(typename G1::Node source,unsigned int& orderIndex,
276                         typename G1::template NodeMap<int>& dm1,
277                         typename G1::template NodeMap<bool>& added) {
278      _order[orderIndex]=source;
279      added[source]=1;
280
281      unsigned int endPosOfLevel=orderIndex,
282        startPosOfLevel=orderIndex,
283        lastAdded=orderIndex;
284
285      typename G1::template NodeMap<int> currConn(_g1,0);
286
287      while(orderIndex<=lastAdded){
288        typename G1::Node currNode = _order[orderIndex];
289        for(typename G1::IncEdgeIt e(_g1,currNode); e!=INVALID; ++e) {
290          typename G1::Node n = _g1.oppositeNode(currNode,e);
291          if(!added[n]) {
292            _order[++lastAdded]=n;
293            added[n]=1;
294          }
295        }
296        if(orderIndex>endPosOfLevel){
297          for(unsigned int j = startPosOfLevel; j <= endPosOfLevel; ++j) {
298            int minInd=j;
299            for(unsigned int i = j+1; i <= endPosOfLevel; ++i)
300              if(currConn[_order[i]]>currConn[_order[minInd]]||
301                 (currConn[_order[i]]==currConn[_order[minInd]]&&
302                  (dm1[_order[i]]>dm1[_order[minInd]]||
303                   (dm1[_order[i]]==dm1[_order[minInd]]&&
304                    _labelTmp1[_intLabels1[_order[minInd]]]>
305                    _labelTmp1[_intLabels1[_order[i]]]))))
306                minInd=i;
307
308            --_labelTmp1[_intLabels1[_order[minInd]]];
309            for(typename G1::IncEdgeIt e(_g1,_order[minInd]); e!=INVALID; ++e)
310              ++currConn[_g1.oppositeNode(_order[minInd],e)];
311            std::swap(_order[j],_order[minInd]);
312          }
313          startPosOfLevel=endPosOfLevel+1;
314          endPosOfLevel=lastAdded;
315        }
316        ++orderIndex;
317      }
318    }
319
320
321    //we will find pairs for the nodes of g1 in this order
322    void initOrder(){
323      for(typename G2::NodeIt n2(_g2); n2!=INVALID; ++n2)
324        ++_labelTmp1[_intLabels2[n2]];
325
326      typename G1::template NodeMap<int> dm1(_g1,0);
327      for(typename G1::EdgeIt e(_g1); e!=INVALID; ++e) {
328        ++dm1[_g1.u(e)];
329        ++dm1[_g1.v(e)];
330      }
331
332      typename G1::template NodeMap<bool> added(_g1,0);
333      unsigned int orderIndex=0;
334
335      for(typename G1::NodeIt n(_g1); n!=INVALID;) {
336        if(!added[n]){
337          typename G1::Node minNode = n;
338          for(typename G1::NodeIt n1(_g1,minNode); n1!=INVALID; ++n1)
339            if(!added[n1] &&
340               (_labelTmp1[_intLabels1[minNode]]>
341                _labelTmp1[_intLabels1[n1]]||(dm1[minNode]<dm1[n1]&&
342                                             _labelTmp1[_intLabels1[minNode]]==
343                                             _labelTmp1[_intLabels1[n1]])))
344              minNode=n1;
345          processBfsTree(minNode,orderIndex,dm1,added);
346        }
347        else
348          ++n;
349      }
350      for(unsigned int i = 0; i < _labelTmp1.size(); ++i)
351        _labelTmp1[i]=0;
352    }
353
354
355    template<MappingType MT>
356    bool extMatch(){
357      while(_depth>=0) {
358        if(_depth==static_cast<int>(_order.size())) {
359          //all nodes of g1 are mapped to nodes of g2
360          --_depth;
361          return true;
362        }
363        typename G1::Node& nodeOfDepth = _order[_depth];
364        const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth];
365        typename G2::IncEdgeIt &edgeItOfDepth = _currEdgeIts[_depth];
366        //the node of g2 whose neighbours are the candidates for
367        //the pair of _order[_depth]
368        typename G2::Node currPNode;
369        if(edgeItOfDepth==INVALID){
370          typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth);
371          //if _mapping[_order[_depth]]!=INVALID, we don't need fstMatchedE
372          if(pairOfNodeOfDepth==INVALID) {
373            for(; fstMatchedE!=INVALID &&
374                  _mapping[_g1.oppositeNode(nodeOfDepth,
375                                            fstMatchedE)]==INVALID;
376                ++fstMatchedE); //find fstMatchedE, it could be preprocessed
377          }
378          if(fstMatchedE==INVALID||pairOfNodeOfDepth!=INVALID) {
379            //We found no covered neighbours, this means that
380            //the graph is not connected (or _depth==0). Each
381            //uncovered (and there are some other properties due
382            //to the spec. problem types) node of g2 is
383            //candidate. We can read the iterator of the last
384            //tried node from the match if it is not the first
385            //try (match[nodeOfDepth]!=INVALID)
386            typename G2::NodeIt n2(_g2);
387            //if it's not the first try
388            if(pairOfNodeOfDepth!=INVALID) {
389              n2=++typename G2::NodeIt(_g2,pairOfNodeOfDepth);
390              subPair(nodeOfDepth,pairOfNodeOfDepth);
391            }
392            for(; n2!=INVALID; ++n2)
393              if(MT!=SUBGRAPH) {
394                if(_conn[n2]==0&&feas<MT>(nodeOfDepth,n2))
395                  break;
396              }
397              else if(_conn[n2]>=0&&feas<MT>(nodeOfDepth,n2))
398                break;
399            // n2 is the next candidate
400            if(n2!=INVALID) {
401              addPair(nodeOfDepth,n2);
402              ++_depth;
403            }
404            else // there are no more candidates
405              --_depth;
406            continue;
407          }
408          else {
409            currPNode=_mapping[_g1.oppositeNode(nodeOfDepth,
410                                                fstMatchedE)];
411            edgeItOfDepth=typename G2::IncEdgeIt(_g2,currPNode);
412          }
413        }
414        else {
415          currPNode=_g2.oppositeNode(pairOfNodeOfDepth,
416                                     edgeItOfDepth);
417          subPair(nodeOfDepth,pairOfNodeOfDepth);
418          ++edgeItOfDepth;
419        }
420        for(; edgeItOfDepth!=INVALID; ++edgeItOfDepth) {
421          const typename G2::Node currNode =
422            _g2.oppositeNode(currPNode, edgeItOfDepth);
423          if(_conn[currNode]>0&&feas<MT>(nodeOfDepth,currNode)) {
424            addPair(nodeOfDepth,currNode);
425            break;
426          }
427        }
428        edgeItOfDepth==INVALID?--_depth:++_depth;
429      }
430      return false;
431    }
432
433    //calculate the lookup table for cutting the search tree
434    void initRNew1tRInOut1t(){
435      typename G1::template NodeMap<int> tmp(_g1,0);
436      for(unsigned int i=0; i<_order.size(); ++i) {
437        tmp[_order[i]]=-1;
438        for(typename G1::IncEdgeIt e1(_g1,_order[i]); e1!=INVALID; ++e1) {
439          const typename G1::Node currNode=_g1.oppositeNode(_order[i],e1);
440          if(tmp[currNode]>0)
441            ++_labelTmp1[_intLabels1[currNode]];
442          else if(tmp[currNode]==0)
443            ++_labelTmp2[_intLabels1[currNode]];
444        }
445        //_labelTmp1[i]=number of neightbours with label i in set rInOut
446        //_labelTmp2[i]=number of neightbours with label i in set rNew
447        for(typename G1::IncEdgeIt e1(_g1,_order[i]); e1!=INVALID; ++e1) {
448          const int& currIntLabel = _intLabels1[_g1.oppositeNode(_order[i],e1)];
449          if(_labelTmp1[currIntLabel]>0) {
450            _rInOutLabels1[_order[i]]
451              .push_back(std::make_pair(currIntLabel,
452                                        _labelTmp1[currIntLabel]));
453            _labelTmp1[currIntLabel]=0;
454          }
455          else if(_labelTmp2[currIntLabel]>0) {
456            _rNewLabels1[_order[i]].
457              push_back(std::make_pair(currIntLabel,_labelTmp2[currIntLabel]));
458            _labelTmp2[currIntLabel]=0;
459          }
460        }
461
462        for(typename G1::IncEdgeIt e1(_g1,_order[i]); e1!=INVALID; ++e1) {
463          int& tmpCurrNode=tmp[_g1.oppositeNode(_order[i],e1)];
464          if(tmpCurrNode!=-1)
465            ++tmpCurrNode;
466        }
467      }
468    }
469
470    int getMaxLabel() const{
471      int m=-1;
472      for(typename G1::NodeIt n1(_g1); n1!=INVALID; ++n1) {
473        const int& currIntLabel = _intLabels1[n1];
474        if(currIntLabel>m)
475          m=currIntLabel;
476      }
477      for(typename G2::NodeIt n2(_g2); n2!=INVALID; ++n2) {
478        const int& currIntLabel = _intLabels2[n2];
479        if(currIntLabel>m)
480          m=currIntLabel;
481      }
482      return m;
483    }
484
485  public:
486    ///Constructor
487
488    ///Constructor.
489    ///\param g1 The graph to be embedded.
490    ///\param g2 The graph \e g1 will be embedded into.
491    ///\param m The type of the NodeMap storing the mapping.
492    ///By default, it is G1::NodeMap<G2::Node>
493    ///\param intLabel1 The NodeMap storing the integer node labels of G1.
494    ///The labels must be the numbers {0,1,2,..,K-1}, where K is the number of
495    ///different labels.
496    ///\param intLabel1 The NodeMap storing the integer node labels of G2.
497    ///The labels must be the numbers {0,1,2,..,K-1}, where K is the number of
498    ///different labels.
499    Vf2pp(const G1 &g1, const G2 &g2,M &m, M1 &intLabels1, M2 &intLabels2) :
500      _g1(g1), _g2(g2), _depth(0), _mapping(m), _order(countNodes(g1),INVALID),
501      _conn(g2,0), _currEdgeIts(countNodes(g1),INVALID), _rNewLabels1(_g1),
502      _rInOutLabels1(_g1), _intLabels1(intLabels1) ,_intLabels2(intLabels2),
503      _maxLabel(getMaxLabel()), _labelTmp1(_maxLabel+1),_labelTmp2(_maxLabel+1),
504      _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0),
505      _deallocLabelsAfterUse(0)
506    {
507      initOrder();
508      initRNew1tRInOut1t();
509
510      //reset mapping
511      for(typename G1::NodeIt n(g1);n!=INVALID;++n)
512        m[n]=INVALID;
513    }
514
515    ///Destructor
516
517    ///Destructor.
518    ///
519    ~Vf2pp()
520    {
521      if(_deallocMappingAfterUse)
522        delete &_mapping;
523      if(_deallocLabelsAfterUse) {
524        delete &_intLabels1;
525        delete &_intLabels2;
526      }
527    }
528
529    ///Returns the current mapping type.
530
531    ///Returns the current mapping type.
532    ///
533    MappingType mappingType() const
534    {
535      return _mapping_type;
536    }
537
538    ///Sets the mapping type
539
540    ///Sets the mapping type.
541    ///
542    ///The mapping type is set to \ref SUBGRAPH by default.
543    ///
544    ///\sa See \ref MappingType for the possible values.
545    void mappingType(MappingType m_type)
546    {
547      _mapping_type = m_type;
548    }
549
550    ///Finds a mapping.
551
552    ///This method finds a mapping from g1 into g2 according to the mapping
553    ///type set by \ref mappingType(MappingType) "mappingType()".
554    ///
555    ///By subsequent calls, it returns all possible mappings one-by-one.
556    ///
557    ///\retval true if a mapping is found.
558    ///\retval false if there is no (more) mapping.
559    bool find()
560    {
561      switch(_mapping_type)
562        {
563        case SUBGRAPH:
564          return extMatch<SUBGRAPH>();
565        case INDUCED:
566          return extMatch<INDUCED>();
567        case ISOMORPH:
568          return extMatch<ISOMORPH>();
569        default:
570          return false;
571        }
572    }
573  };
574
575  template<typename G1, typename G2>
576  class Vf2ppWizardBase {
577  protected:
578    typedef G1 Graph1;
579    typedef G2 Graph2;
580
581    const G1 &_g1;
582    const G2 &_g2;
583
584    MappingType _mapping_type;
585
586    typedef typename G1::template NodeMap<typename G2::Node> Mapping;
587    bool _local_mapping;
588    void *_mapping;
589    void createMapping() {
590      _mapping = new Mapping(_g1);
591    }
592
593    bool _local_nodeLabels;
594    typedef typename G1::template NodeMap<int> NodeLabels1;
595    typedef typename G2::template NodeMap<int> NodeLabels2;
596    void *_nodeLabels1, *_nodeLabels2;
597    void createNodeLabels() {
598      _nodeLabels1 = new NodeLabels1(_g1,0);
599      _nodeLabels2 = new NodeLabels2(_g2,0);
600    }
601
602    Vf2ppWizardBase(const G1 &g1,const G2 &g2)
603      : _g1(g1), _g2(g2), _mapping_type(SUBGRAPH),
604        _local_mapping(1), _local_nodeLabels(1) { }
605  };
606
607
608  /// \brief Auxiliary class for the function-type interface of %VF2
609  /// Plus Plus algorithm.
610  ///
611  /// This auxiliary class implements the named parameters of
612  /// \ref vf2pp() "function-type interface" of \ref Vf2pp algorithm.
613  ///
614  /// \warning This class is not to be used directly.
615  ///
616  /// \tparam TR The traits class that defines various types used by the
617  /// algorithm.
618  template<typename TR>
619  class Vf2ppWizard : public TR {
620    typedef TR Base;
621    typedef typename TR::Graph1 Graph1;
622    typedef typename TR::Graph2 Graph2;
623    typedef typename TR::Mapping Mapping;
624    typedef typename TR::NodeLabels1 NodeLabels1;
625    typedef typename TR::NodeLabels2 NodeLabels2;
626
627    using TR::_g1;
628    using TR::_g2;
629    using TR::_mapping_type;
630    using TR::_mapping;
631    using TR::_nodeLabels1;
632    using TR::_nodeLabels2;
633
634  public:
635    ///Constructor
636    Vf2ppWizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {}
637
638    ///Copy constructor
639    Vf2ppWizard(const Base &b) : Base(b) {}
640
641
642    template<typename T>
643    struct SetMappingBase : public Base {
644      typedef T Mapping;
645      SetMappingBase(const Base &b) : Base(b) {}
646    };
647
648    ///\brief \ref named-templ-param "Named parameter" for setting
649    ///the mapping.
650    ///
651    ///\ref named-templ-param "Named parameter" function for setting
652    ///the map that stores the found embedding.
653    template<typename T>
654    Vf2ppWizard< SetMappingBase<T> > mapping(const T &t) {
655      Base::_mapping=reinterpret_cast<void*>(const_cast<T*>(&t));
656      Base::_local_mapping = 0;
657      return Vf2ppWizard<SetMappingBase<T> >(*this);
658    }
659
660    template<typename NL1, typename NL2>
661    struct SetNodeLabelsBase : public Base {
662      typedef NL1 NodeLabels1;
663      typedef NL2 NodeLabels2;
664      SetNodeLabelsBase(const Base &b) : Base(b) { }
665    };
666
667    ///\brief \ref named-templ-param "Named parameter" for setting the
668    ///node labels.
669    ///
670    ///\ref named-templ-param "Named parameter" function for setting
671    ///the node labels.
672    ///
673    ///\param nodeLabels1 A \ref concepts::ReadMap "readable node map"
674    ///of g1 with integer values. In case of K different labels, the labels
675    ///must be the numbers {0,1,..,K-1}.
676    ///\param nodeLabels2 A \ref concepts::ReadMap "readable node map"
677    ///of g2 with integer values. In case of K different labels, the labels
678    ///must be the numbers {0,1,..,K-1}.
679    template<typename NL1, typename NL2>
680    Vf2ppWizard< SetNodeLabelsBase<NL1,NL2> >
681    nodeLabels(const NL1 &nodeLabels1, const NL2 &nodeLabels2) {
682      Base::_local_nodeLabels = 0;
683      Base::_nodeLabels1=
684        reinterpret_cast<void*>(const_cast<NL1*>(&nodeLabels1));
685      Base::_nodeLabels2=
686        reinterpret_cast<void*>(const_cast<NL2*>(&nodeLabels2));
687      return Vf2ppWizard<SetNodeLabelsBase<NL1,NL2> >
688        (SetNodeLabelsBase<NL1,NL2>(*this));
689    }
690
691
692    ///\brief \ref named-templ-param "Named parameter" for setting
693    ///the mapping type.
694    ///
695    ///\ref named-templ-param "Named parameter" for setting
696    ///the mapping type.
697    ///
698    ///The mapping type is set to \ref SUBGRAPH by default.
699    ///
700    ///\sa See \ref MappingType for the possible values.
701    Vf2ppWizard<Base> &mappingType(MappingType m_type) {
702      _mapping_type = m_type;
703      return *this;
704    }
705
706    ///\brief \ref named-templ-param "Named parameter" for setting
707    ///the mapping type to \ref INDUCED.
708    ///
709    ///\ref named-templ-param "Named parameter" for setting
710    ///the mapping type to \ref INDUCED.
711    Vf2ppWizard<Base> &induced() {
712      _mapping_type = INDUCED;
713      return *this;
714    }
715
716    ///\brief \ref named-templ-param "Named parameter" for setting
717    ///the mapping type to \ref ISOMORPH.
718    ///
719    ///\ref named-templ-param "Named parameter" for setting
720    ///the mapping type to \ref ISOMORPH.
721    Vf2ppWizard<Base> &iso() {
722      _mapping_type = ISOMORPH;
723      return *this;
724    }
725
726    ///Runs the %VF2 Plus Plus algorithm.
727
728    ///This method runs the VF2 Plus Plus algorithm.
729    ///
730    ///\retval true if a mapping is found.
731    ///\retval false if there is no mapping.
732    bool run() {
733      if(Base::_local_mapping)
734        Base::createMapping();
735      if(Base::_local_nodeLabels)
736        Base::createNodeLabels();
737
738      Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2 >
739        alg(_g1, _g2, *reinterpret_cast<Mapping*>(_mapping),
740            *reinterpret_cast<NodeLabels1*>(_nodeLabels1),
741            *reinterpret_cast<NodeLabels2*>(_nodeLabels2));
742
743      alg.mappingType(_mapping_type);
744
745      const bool ret = alg.find();
746
747      if(Base::_local_nodeLabels) {
748        delete reinterpret_cast<NodeLabels1*>(_nodeLabels1);
749        delete reinterpret_cast<NodeLabels2*>(_nodeLabels2);
750      }
751      if(Base::_local_mapping)
752        delete reinterpret_cast<Mapping*>(_mapping);
753
754      return ret;
755    }
756
757    ///Get a pointer to the generated Vf2pp object.
758
759    ///Gives a pointer to the generated Vf2pp object.
760    ///
761    ///\return Pointer to the generated Vf2pp object.
762    ///\warning Don't forget to delete the referred Vf2pp object after use.
763    Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2 >*
764    getPtrToVf2ppObject(){
765      if(Base::_local_mapping)
766        Base::createMapping();
767      if(Base::_local_nodeLabels)
768        Base::createNodeLabels();
769
770      Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2 >* ptr =
771        new Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2>
772        (_g1, _g2, *reinterpret_cast<Mapping*>(_mapping),
773         *reinterpret_cast<NodeLabels1*>(_nodeLabels1),
774         *reinterpret_cast<NodeLabels2*>(_nodeLabels2));
775      ptr->mappingType(_mapping_type);
776      if(Base::_local_mapping)
777        ptr->_deallocMappingAfterUse=true;
778      if(Base::_local_nodeLabels)
779        ptr->_deallocLabelMapsAfterUse=true;
780
781      return ptr;
782    }
783
784    ///Counts the number of mappings.
785
786    ///This method counts the number of mappings.
787    ///
788    /// \return The number of mappings.
789    int count() {
790      if(Base::_local_mapping)
791        Base::createMapping();
792      if(Base::_local_nodeLabels)
793        Base::createNodeLabels();
794
795      Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2>
796        alg(_g1, _g2, *reinterpret_cast<Mapping*>(_mapping),
797            *reinterpret_cast<NodeLabels1*>(_nodeLabels1),
798            *reinterpret_cast<NodeLabels2*>(_nodeLabels2));
799
800      alg.mappingType(_mapping_type);
801
802      int ret = 0;
803      while(alg.find())
804        ++ret;
805
806      if(Base::_local_nodeLabels) {
807        delete reinterpret_cast<NodeLabels1*>(_nodeLabels1);
808        delete reinterpret_cast<NodeLabels2*>(_nodeLabels2);
809      }
810      if(Base::_local_mapping)
811        delete reinterpret_cast<Mapping*>(_mapping);
812
813      return ret;
814    }
815  };
816
817
818  ///Function-type interface for VF2 Plus Plus algorithm.
819
820  /// \ingroup graph_isomorphism
821  ///Function-type interface for VF2 Plus Plus algorithm.
822  ///
823  ///This function has several \ref named-func-param "named parameters"
824  ///declared as the members of class \ref Vf2ppWizard.
825  ///The following examples show how to use these parameters.
826  ///\code
827  ///  ListGraph::NodeMap<ListGraph::Node> m(g);
828  ///  // Find an embedding of graph g1 into graph g2
829  ///  vf2pp(g1,g2).mapping(m).run();
830  ///
831  ///  // Check whether graphs g1 and g2 are isomorphic
832  ///  bool is_iso = vf2pp(g1,g2).iso().run();
833  ///
834  ///  // Count the number of isomorphisms
835  ///  int num_isos = vf2pp(g1,g2).iso().count();
836  ///
837  ///  // Iterate through all the induced subgraph mappings
838  ///  // of graph g1 into g2 using the labels c1 and c2
839  ///  auto* myVf2pp = vf2pp(g1,g2).mapping(m).nodeLabels(c1,c2)
840  ///  .induced().getPtrToVf2Object();
841  ///  while(myVf2pp->find()){
842  ///    //process the current mapping m
843  ///  }
844  ///  delete myVf22pp;
845  ///\endcode
846  ///\warning Don't forget to put the \ref Vf2ppWizard::run() "run()",
847  ///\ref Vf2ppWizard::count() "count()" or
848  ///the \ref Vf2ppWizard::getPtrToVf2ppObject() "getPtrToVf2ppObject()"
849  ///to the end of the expression.
850  ///\sa Vf2ppWizard
851  ///\sa Vf2pp
852  template<class G1, class G2>
853  Vf2ppWizard<Vf2ppWizardBase<G1,G2> > vf2pp(const G1 &g1, const G2 &g2) {
854    return Vf2ppWizard<Vf2ppWizardBase<G1,G2> >(g1,g2);
855  }
856
857}
858
859#endif
860
Note: See TracBrowser for help on using the repository browser.