lemon/vf2pp.h
author Peter Kovacs <kpeter@inf.elte.hu>
Sat, 07 Oct 2017 16:22:04 +0200
changeset 1193 3ca508482e4c
parent 1192 b79ff94e27d9
child 1194 e68f0ef37e77
permissions -rw-r--r--
Change misleading method name in Vf2pp (#597)

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