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