COIN-OR::LEMON - Graph Library

source: lemon/lemon/vf2pp.h @ 1405:3feba0ea1bda

Last change on this file since 1405:3feba0ea1bda was 1405:3feba0ea1bda, checked in by Peter Madarasi <madarasip@…>, 2 years ago

Vf2 improvements and Vf2pp implementation (#597)

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