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