lemon/vf2pp.h
author Alpar Juttner <alpar@cs.elte.hu>
Wed, 17 Oct 2018 22:55:02 +0200
changeset 1414 73e29215aaa4
parent 1413 e68f0ef37e77
permissions -rw-r--r--
Add citation for 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/bits/vf2_internals.h>
    28 
    29 #include <vector>
    30 #include <algorithm>
    31 #include <utility>
    32 
    33 namespace 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