lemon/vf2.h
author Peter Kovacs <kpeter@inf.elte.hu>
Sat, 07 Oct 2017 15:48:00 +0200
changeset 1410 d9f79b81ef6c
parent 1409 c89884c1737b
child 1413 e68f0ef37e77
permissions -rw-r--r--
Change the default graph type of Vf2 and Vf2pp (#597)
madarasip@1350
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
madarasip@1350
     2
 *
madarasip@1350
     3
 * This file is a part of LEMON, a generic C++ optimization library.
madarasip@1350
     4
 *
madarasip@1405
     5
 * Copyright (C) 2015-2017
madarasip@1350
     6
 * EMAXA Kutato-fejleszto Kft. (EMAXA Research Ltd.)
madarasip@1350
     7
 *
madarasip@1350
     8
 * Permission to use, modify and distribute this software is granted
madarasip@1350
     9
 * provided that this copyright notice appears in all copies. For
madarasip@1350
    10
 * precise terms see the accompanying LICENSE file.
madarasip@1350
    11
 *
madarasip@1350
    12
 * This software is provided "AS IS" with no warranty of any kind,
madarasip@1350
    13
 * express or implied, and with no claim as to its suitability for any
madarasip@1350
    14
 * purpose.
madarasip@1350
    15
 *
madarasip@1350
    16
 */
madarasip@1350
    17
madarasip@1350
    18
#ifndef LEMON_VF2_H
madarasip@1350
    19
#define LEMON_VF2_H
madarasip@1350
    20
alpar@1351
    21
///\ingroup graph_properties
alpar@1351
    22
///\file
alpar@1351
    23
///\brief VF2 algorithm \cite cordella2004sub.
alpar@1351
    24
madarasip@1350
    25
#include <lemon/core.h>
madarasip@1350
    26
#include <lemon/concepts/graph.h>
madarasip@1350
    27
#include <lemon/dfs.h>
madarasip@1350
    28
#include <lemon/bfs.h>
madarasip@1405
    29
#include <lemon/bits/vf2_internals.h>
madarasip@1350
    30
madarasip@1350
    31
#include <vector>
madarasip@1350
    32
madarasip@1405
    33
namespace lemon {
madarasip@1405
    34
  namespace bits {
madarasip@1405
    35
    namespace vf2 {
madarasip@1405
    36
madarasip@1405
    37
      class AlwaysEq {
madarasip@1350
    38
      public:
madarasip@1350
    39
        template<class T1, class T2>
madarasip@1405
    40
        bool operator()(T1&, T2&) const {
madarasip@1350
    41
          return true;
madarasip@1350
    42
        }
madarasip@1350
    43
      };
madarasip@1350
    44
madarasip@1350
    45
      template<class M1, class M2>
madarasip@1405
    46
      class MapEq{
madarasip@1350
    47
        const M1 &_m1;
madarasip@1350
    48
        const M2 &_m2;
madarasip@1350
    49
      public:
madarasip@1405
    50
        MapEq(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) { }
madarasip@1405
    51
        bool operator()(typename M1::Key k1, typename M2::Key k2) const {
madarasip@1350
    52
          return _m1[k1] == _m2[k2];
madarasip@1350
    53
        }
madarasip@1350
    54
      };
madarasip@1350
    55
madarasip@1350
    56
      template <class G>
madarasip@1405
    57
      class DfsLeaveOrder : public DfsVisitor<G> {
madarasip@1350
    58
        const G &_g;
madarasip@1350
    59
        std::vector<typename G::Node> &_order;
madarasip@1350
    60
        int i;
madarasip@1350
    61
      public:
madarasip@1350
    62
        DfsLeaveOrder(const G &g, std::vector<typename G::Node> &order)
madarasip@1405
    63
          : i(countNodes(g)), _g(g), _order(order) { }
madarasip@1405
    64
        void leave(const typename G::Node &node) {
madarasip@1350
    65
          _order[--i]=node;
madarasip@1350
    66
        }
madarasip@1350
    67
      };
madarasip@1350
    68
madarasip@1350
    69
      template <class G>
madarasip@1405
    70
      class BfsLeaveOrder : public BfsVisitor<G> {
madarasip@1350
    71
        int i;
madarasip@1350
    72
        const G &_g;
madarasip@1350
    73
        std::vector<typename G::Node> &_order;
madarasip@1350
    74
      public:
madarasip@1350
    75
        BfsLeaveOrder(const G &g, std::vector<typename G::Node> &order)
madarasip@1405
    76
          : i(0), _g(g), _order(order){
madarasip@1405
    77
        }
madarasip@1405
    78
        void process(const typename G::Node &node) {
madarasip@1350
    79
          _order[i++]=node;
madarasip@1350
    80
        }
madarasip@1350
    81
      };
madarasip@1350
    82
    }
madarasip@1350
    83
  }
madarasip@1350
    84
madarasip@1350
    85
alpar@1351
    86
  ///%VF2 algorithm class.
alpar@1351
    87
alpar@1351
    88
  ///\ingroup graph_isomorphism This class provides an efficient
alpar@1351
    89
  ///implementation of the %VF2 algorithm \cite cordella2004sub
alpar@1351
    90
  ///for variants of the (Sub)graph Isomorphism problem.
alpar@1351
    91
  ///
alpar@1351
    92
  ///There is also a \ref vf2() "function-type interface" called \ref vf2()
alpar@1351
    93
  ///for the %VF2 algorithm, which is probably more convenient in most
kpeter@1407
    94
  ///use cases.
alpar@1351
    95
  ///
alpar@1351
    96
  ///\tparam G1 The type of the graph to be embedded.
kpeter@1410
    97
  ///The default type is \ref ListGraph.
alpar@1351
    98
  ///\tparam G2 The type of the graph g1 will be embedded into.
kpeter@1410
    99
  ///The default type is \ref ListGraph.
alpar@1351
   100
  ///\tparam M The type of the NodeMap storing the mapping.
alpar@1351
   101
  ///By default, it is G1::NodeMap<G2::Node>
alpar@1351
   102
  ///\tparam NEQ A bool-valued binary functor determinining whether a node is
kpeter@1407
   103
  ///mappable to another. By default, it is an always-true operator.
alpar@1351
   104
  ///
alpar@1351
   105
  ///\sa vf2()
alpar@1351
   106
#ifdef DOXYGEN
alpar@1351
   107
  template<class G1, class G2, class M, class NEQ >
alpar@1351
   108
#else
kpeter@1410
   109
  template<class G1 = ListGraph,
kpeter@1410
   110
           class G2 = ListGraph,
alpar@1351
   111
           class M = typename G1::template NodeMap<G2::Node>,
alpar@1351
   112
           class NEQ = bits::vf2::AlwaysEq >
alpar@1351
   113
#endif
madarasip@1405
   114
  class Vf2 {
kpeter@1407
   115
    //The graph to be embedded
madarasip@1350
   116
    const G1 &_g1;
kpeter@1407
   117
kpeter@1407
   118
    //The graph into which g1 is to be embedded
madarasip@1350
   119
    const G2 &_g2;
kpeter@1407
   120
kpeter@1408
   121
    //Functor with bool operator()(G1::Node,G2::Node), which returns 1
kpeter@1408
   122
    //if and only if the two nodes are equivalent
kpeter@1408
   123
    NEQ _nEq;
kpeter@1408
   124
kpeter@1408
   125
    //Current depth in the DFS tree.
kpeter@1408
   126
    int _depth;
kpeter@1408
   127
kpeter@1408
   128
    //The current mapping. _mapping[v1]=v2 iff v1 has been mapped to v2,
kpeter@1408
   129
    //where v1 is a node of G1 and v2 is a node of G2
kpeter@1408
   130
    M &_mapping;
kpeter@1408
   131
kpeter@1408
   132
    //_order[i] is the node of g1 for which a pair is searched if depth=i
kpeter@1408
   133
    std::vector<typename G1::Node> _order;
kpeter@1408
   134
 
kpeter@1408
   135
    //_conn[v2] = number of covered neighbours of v2
kpeter@1408
   136
    typename G2::template NodeMap<int> _conn;
kpeter@1408
   137
kpeter@1408
   138
    //_currEdgeIts[i] is the last used edge iterator in the i-th
kpeter@1408
   139
    //depth to find a pair for node _order[i]
kpeter@1408
   140
    std::vector<typename G2::IncEdgeIt> _currEdgeIts;
kpeter@1408
   141
madarasip@1405
   142
    //lookup tables for cutting the searchtree
kpeter@1408
   143
    typename G1::template NodeMap<int> _rNew1t, _rInOut1t;
madarasip@1350
   144
madarasip@1405
   145
    MappingType _mapping_type;
madarasip@1405
   146
madarasip@1405
   147
    bool _deallocMappingAfterUse;
madarasip@1350
   148
madarasip@1350
   149
    //cut the search tree
madarasip@1405
   150
    template<MappingType MT>
madarasip@1405
   151
    bool cut(const typename G1::Node n1,const typename G2::Node n2) const {
madarasip@1350
   152
      int rNew2=0,rInOut2=0;
madarasip@1405
   153
      for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
madarasip@1405
   154
        const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
madarasip@1405
   155
        if(_conn[currNode]>0)
madarasip@1405
   156
          ++rInOut2;
madarasip@1405
   157
        else if(MT!=SUBGRAPH&&_conn[currNode]==0)
madarasip@1405
   158
          ++rNew2;
madarasip@1405
   159
      }
madarasip@1405
   160
      switch(MT) {
madarasip@1405
   161
      case INDUCED:
kpeter@1408
   162
        return _rInOut1t[n1]<=rInOut2&&_rNew1t[n1]<=rNew2;
madarasip@1405
   163
      case SUBGRAPH:
kpeter@1408
   164
        return _rInOut1t[n1]<=rInOut2;
madarasip@1405
   165
      case ISOMORPH:
kpeter@1408
   166
        return _rInOut1t[n1]==rInOut2&&_rNew1t[n1]==rNew2;
madarasip@1405
   167
      default:
madarasip@1405
   168
        return false;
madarasip@1405
   169
      }
madarasip@1350
   170
    }
madarasip@1350
   171
madarasip@1405
   172
    template<MappingType MT>
madarasip@1405
   173
    bool feas(const typename G1::Node n1,const typename G2::Node n2) {
madarasip@1350
   174
      if(!_nEq(n1,n2))
madarasip@1350
   175
        return 0;
madarasip@1350
   176
madarasip@1405
   177
      for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
madarasip@1405
   178
        const typename G1::Node& currNode=_g1.oppositeNode(n1,e1);
madarasip@1405
   179
        if(_mapping[currNode]!=INVALID)
madarasip@1405
   180
          --_conn[_mapping[currNode]];
madarasip@1405
   181
      }
madarasip@1405
   182
      bool isIso=1;
madarasip@1405
   183
      for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
madarasip@1405
   184
        int& connCurrNode = _conn[_g2.oppositeNode(n2,e2)];
madarasip@1405
   185
        if(connCurrNode<-1)
madarasip@1405
   186
          ++connCurrNode;
madarasip@1405
   187
        else if(MT!=SUBGRAPH&&connCurrNode==-1) {
madarasip@1405
   188
          isIso=0;
madarasip@1405
   189
          break;
madarasip@1350
   190
        }
madarasip@1405
   191
      }
madarasip@1405
   192
madarasip@1405
   193
      for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
madarasip@1405
   194
        const typename G2::Node& currNodePair=_mapping[_g1.oppositeNode(n1,e1)];
madarasip@1405
   195
        int& connCurrNodePair=_conn[currNodePair];
madarasip@1405
   196
        if(currNodePair!=INVALID&&connCurrNodePair!=-1) {
madarasip@1405
   197
          switch(MT) {
madarasip@1405
   198
          case INDUCED:
madarasip@1405
   199
          case ISOMORPH:
madarasip@1405
   200
            isIso=0;
madarasip@1405
   201
            break;
madarasip@1405
   202
          case SUBGRAPH:
madarasip@1405
   203
            if(connCurrNodePair<-1)
madarasip@1350
   204
              isIso=0;
madarasip@1405
   205
            break;
madarasip@1405
   206
          }
madarasip@1405
   207
          connCurrNodePair=-1;
madarasip@1350
   208
        }
madarasip@1405
   209
      }
madarasip@1350
   210
      return isIso&&cut<MT>(n1,n2);
madarasip@1350
   211
    }
madarasip@1350
   212
madarasip@1405
   213
    void addPair(const typename G1::Node n1,const typename G2::Node n2) {
madarasip@1350
   214
      _conn[n2]=-1;
alpar@1351
   215
      _mapping.set(n1,n2);
madarasip@1405
   216
      for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
madarasip@1405
   217
        int& currConn = _conn[_g2.oppositeNode(n2,e2)];
madarasip@1405
   218
        if(currConn!=-1)
madarasip@1405
   219
          ++currConn;
madarasip@1405
   220
      }
madarasip@1350
   221
    }
madarasip@1350
   222
madarasip@1405
   223
    void subPair(const typename G1::Node n1,const typename G2::Node n2) {
madarasip@1350
   224
      _conn[n2]=0;
alpar@1351
   225
      _mapping.set(n1,INVALID);
madarasip@1405
   226
      for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
madarasip@1405
   227
        int& currConn = _conn[_g2.oppositeNode(n2,e2)];
madarasip@1405
   228
        if(currConn>0)
madarasip@1405
   229
          --currConn;
madarasip@1405
   230
        else if(currConn==-1)
madarasip@1405
   231
          ++_conn[n2];
madarasip@1405
   232
      }
madarasip@1350
   233
    }
madarasip@1350
   234
kpeter@1409
   235
    void initOrder() {
madarasip@1405
   236
      // we will find pairs for the nodes of g1 in this order
madarasip@1405
   237
kpeter@1408
   238
      // bits::vf2::DfsLeaveOrder<G1> v(_g1,_order);
madarasip@1350
   239
      //   DfsVisit<G1,bits::vf2::DfsLeaveOrder<G1> >dfs(_g1, v);
madarasip@1350
   240
      //   dfs.run();
madarasip@1350
   241
madarasip@1350
   242
      //it is more efficient in practice than DFS
kpeter@1408
   243
      bits::vf2::BfsLeaveOrder<G1> v(_g1,_order);
madarasip@1350
   244
      BfsVisit<G1,bits::vf2::BfsLeaveOrder<G1> >bfs(_g1, v);
madarasip@1350
   245
      bfs.run();
madarasip@1350
   246
    }
madarasip@1350
   247
madarasip@1405
   248
    template<MappingType MT>
madarasip@1405
   249
    bool extMatch() {
madarasip@1405
   250
      while(_depth>=0) {
kpeter@1408
   251
        if(_depth==static_cast<int>(_order.size())) {
kpeter@1407
   252
          //all nodes of g1 are mapped to nodes of g2
madarasip@1405
   253
          --_depth;
madarasip@1405
   254
          return true;
madarasip@1405
   255
        }
kpeter@1408
   256
        typename G1::Node& nodeOfDepth = _order[_depth];
madarasip@1405
   257
        const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth];
kpeter@1408
   258
        typename G2::IncEdgeIt &edgeItOfDepth = _currEdgeIts[_depth];
kpeter@1407
   259
        //the node of g2 whose neighbours are the candidates for
madarasip@1405
   260
        //the pair of nodeOfDepth
madarasip@1405
   261
        typename G2::Node currPNode;
madarasip@1405
   262
        if(edgeItOfDepth==INVALID) {
madarasip@1405
   263
          typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth);
kpeter@1407
   264
          //if pairOfNodeOfDepth!=INVALID, we don't use fstMatchedE
kpeter@1407
   265
          if(pairOfNodeOfDepth==INVALID) {
madarasip@1405
   266
            for(; fstMatchedE!=INVALID &&
madarasip@1405
   267
                  _mapping[_g1.oppositeNode(nodeOfDepth,
madarasip@1405
   268
                                            fstMatchedE)]==INVALID;
madarasip@1405
   269
                ++fstMatchedE) ; //find fstMatchedE
kpeter@1407
   270
          }
madarasip@1405
   271
          if(fstMatchedE==INVALID||pairOfNodeOfDepth!=INVALID) {
kpeter@1407
   272
            //We found no covered neighbours, this means that
kpeter@1407
   273
            //the graph is not connected (or _depth==0). Each
kpeter@1407
   274
            //uncovered (and there are some other properties due
madarasip@1405
   275
            //to the spec. problem types) node of g2 is
kpeter@1407
   276
            //candidate. We can read the iterator of the last
madarasip@1405
   277
            //tried node from the match if it is not the first
kpeter@1407
   278
            //try (match[nodeOfDepth]!=INVALID)
madarasip@1405
   279
            typename G2::NodeIt n2(_g2);
madarasip@1405
   280
            //if it's not the first try
madarasip@1405
   281
            if(pairOfNodeOfDepth!=INVALID) {
madarasip@1405
   282
              n2=++typename G2::NodeIt(_g2,pairOfNodeOfDepth);
madarasip@1405
   283
              subPair(nodeOfDepth,pairOfNodeOfDepth);
madarasip@1405
   284
            }
madarasip@1405
   285
            for(; n2!=INVALID; ++n2)
madarasip@1405
   286
              if(MT!=SUBGRAPH) {
madarasip@1405
   287
                if(_conn[n2]==0&&feas<MT>(nodeOfDepth,n2))
madarasip@1405
   288
                  break;
madarasip@1405
   289
              }
madarasip@1405
   290
              else if(_conn[n2]>=0&&feas<MT>(nodeOfDepth,n2))
madarasip@1405
   291
                break;
madarasip@1405
   292
            // n2 is the next candidate
madarasip@1405
   293
            if(n2!=INVALID){
madarasip@1405
   294
              addPair(nodeOfDepth,n2);
madarasip@1405
   295
              ++_depth;
madarasip@1405
   296
            }
madarasip@1405
   297
            else // there are no more candidates
madarasip@1350
   298
              --_depth;
madarasip@1405
   299
            continue;
madarasip@1405
   300
          }
madarasip@1405
   301
          else {
madarasip@1405
   302
            currPNode=_mapping[_g1.oppositeNode(nodeOfDepth,
madarasip@1405
   303
                                                fstMatchedE)];
madarasip@1405
   304
            edgeItOfDepth=typename G2::IncEdgeIt(_g2,currPNode);
madarasip@1405
   305
          }
madarasip@1350
   306
        }
madarasip@1405
   307
        else {
madarasip@1405
   308
          currPNode=_g2.oppositeNode(pairOfNodeOfDepth,
madarasip@1405
   309
                                     edgeItOfDepth);
madarasip@1405
   310
          subPair(nodeOfDepth,pairOfNodeOfDepth);
madarasip@1405
   311
          ++edgeItOfDepth;
madarasip@1405
   312
        }
madarasip@1405
   313
        for(; edgeItOfDepth!=INVALID; ++edgeItOfDepth) {
madarasip@1405
   314
          const typename G2::Node currNode =
madarasip@1405
   315
            _g2.oppositeNode(currPNode, edgeItOfDepth);
madarasip@1405
   316
          if(_conn[currNode]>0&&feas<MT>(nodeOfDepth,currNode)) {
madarasip@1405
   317
            addPair(nodeOfDepth,currNode);
madarasip@1405
   318
            break;
madarasip@1405
   319
          }
madarasip@1405
   320
        }
madarasip@1405
   321
        edgeItOfDepth==INVALID?--_depth:++_depth;
madarasip@1405
   322
      }
madarasip@1350
   323
      return false;
madarasip@1350
   324
    }
madarasip@1350
   325
kpeter@1407
   326
    //calculate the lookup table for cutting the search tree
kpeter@1409
   327
    void initRNew1tRInOut1t() {
madarasip@1350
   328
      typename G1::template NodeMap<int> tmp(_g1,0);
kpeter@1408
   329
      for(unsigned int i=0; i<_order.size(); ++i) {
kpeter@1408
   330
        const typename G1::Node& orderI = _order[i];
madarasip@1405
   331
        tmp[orderI]=-1;
madarasip@1405
   332
        for(typename G1::IncEdgeIt e1(_g1,orderI); e1!=INVALID; ++e1) {
madarasip@1405
   333
          const typename G1::Node currNode=_g1.oppositeNode(orderI,e1);
madarasip@1405
   334
          if(tmp[currNode]>0)
kpeter@1408
   335
            ++_rInOut1t[orderI];
madarasip@1405
   336
          else if(tmp[currNode]==0)
kpeter@1408
   337
            ++_rNew1t[orderI];
madarasip@1350
   338
        }
madarasip@1405
   339
        for(typename G1::IncEdgeIt e1(_g1,orderI); e1!=INVALID; ++e1) {
madarasip@1405
   340
          const typename G1::Node currNode=_g1.oppositeNode(orderI,e1);
madarasip@1405
   341
          if(tmp[currNode]!=-1)
madarasip@1405
   342
            ++tmp[currNode];
madarasip@1405
   343
        }
madarasip@1405
   344
      }
madarasip@1350
   345
    }
madarasip@1350
   346
  public:
alpar@1351
   347
    ///Constructor
alpar@1351
   348
alpar@1351
   349
    ///Constructor
alpar@1351
   350
alpar@1351
   351
    ///\param g1 The graph to be embedded into \e g2.
alpar@1351
   352
    ///\param g2 The graph \e g1 will be embedded into.
alpar@1351
   353
    ///\param m \ref concepts::ReadWriteMap "read-write" NodeMap
alpar@1351
   354
    ///storing the found mapping.
madarasip@1405
   355
    ///\param neq A bool-valued binary functor determining whether a node is
alpar@1351
   356
    ///mappable to another. By default it is an always true operator.
madarasip@1405
   357
    Vf2(const G1 &g1, const G2 &g2, M &m, const NEQ &neq = NEQ() ) :
kpeter@1408
   358
      _g1(g1), _g2(g2), _nEq(neq), _depth(0), _mapping(m),
kpeter@1408
   359
      _order(countNodes(g1)), _conn(g2,0),
kpeter@1408
   360
      _currEdgeIts(countNodes(g1),INVALID), _rNew1t(g1,0), _rInOut1t(g1,0),
kpeter@1408
   361
      _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0)
kpeter@1407
   362
    {
kpeter@1409
   363
      initOrder();
kpeter@1409
   364
      initRNew1tRInOut1t();
alpar@1352
   365
      for(typename G1::NodeIt n(g1);n!=INVALID;++n)
alpar@1352
   366
        m[n]=INVALID;
madarasip@1350
   367
    }
madarasip@1350
   368
madarasip@1405
   369
    ///Destructor
madarasip@1405
   370
madarasip@1405
   371
    ///Destructor.
madarasip@1405
   372
    ///
madarasip@1405
   373
madarasip@1405
   374
    ~Vf2(){
madarasip@1405
   375
      if(_deallocMappingAfterUse)
madarasip@1405
   376
        delete &_mapping;
madarasip@1405
   377
    }
madarasip@1405
   378
alpar@1351
   379
    ///Returns the current mapping type
madarasip@1350
   380
alpar@1351
   381
    ///Returns the current mapping type
alpar@1351
   382
    ///
madarasip@1405
   383
    MappingType mappingType() const {
madarasip@1405
   384
      return _mapping_type;
madarasip@1405
   385
    }
alpar@1351
   386
    ///Sets mapping type
alpar@1351
   387
alpar@1351
   388
    ///Sets mapping type.
alpar@1351
   389
    ///
alpar@1351
   390
    ///The mapping type is set to \ref SUBGRAPH by default.
alpar@1351
   391
    ///
madarasip@1405
   392
    ///\sa See \ref MappingType for the possible values.
madarasip@1405
   393
    void mappingType(MappingType m_type) {
madarasip@1405
   394
      _mapping_type = m_type;
madarasip@1405
   395
    }
alpar@1351
   396
kpeter@1366
   397
    ///Finds a mapping
alpar@1351
   398
madarasip@1405
   399
    ///It finds a mapping from g1 into g2 according to the mapping
madarasip@1405
   400
    ///type set by \ref mappingType(MappingType) "mappingType()".
alpar@1351
   401
    ///
alpar@1351
   402
    ///By subsequent calls, it returns all possible mappings one-by-one.
alpar@1351
   403
    ///
alpar@1351
   404
    ///\retval true if a mapping is found.
alpar@1351
   405
    ///\retval false if there is no (more) mapping.
madarasip@1405
   406
    bool find() {
madarasip@1405
   407
      switch(_mapping_type) {
madarasip@1405
   408
      case SUBGRAPH:
madarasip@1405
   409
        return extMatch<SUBGRAPH>();
madarasip@1405
   410
      case INDUCED:
madarasip@1405
   411
        return extMatch<INDUCED>();
madarasip@1405
   412
      case ISOMORPH:
madarasip@1405
   413
        return extMatch<ISOMORPH>();
madarasip@1405
   414
      default:
madarasip@1405
   415
        return false;
madarasip@1405
   416
      }
madarasip@1350
   417
    }
madarasip@1350
   418
  };
madarasip@1350
   419
madarasip@1350
   420
  template<class G1, class G2>
madarasip@1405
   421
  class Vf2WizardBase {
madarasip@1350
   422
  protected:
madarasip@1350
   423
    typedef G1 Graph1;
madarasip@1350
   424
    typedef G2 Graph2;
madarasip@1350
   425
madarasip@1350
   426
    const G1 &_g1;
madarasip@1350
   427
    const G2 &_g2;
madarasip@1350
   428
madarasip@1405
   429
    MappingType _mapping_type;
madarasip@1350
   430
madarasip@1350
   431
    typedef typename G1::template NodeMap<typename G2::Node> Mapping;
madarasip@1350
   432
    bool _local_mapping;
madarasip@1350
   433
    void *_mapping;
madarasip@1405
   434
    void createMapping() {
madarasip@1350
   435
      _mapping = new Mapping(_g1);
madarasip@1350
   436
    }
madarasip@1350
   437
madarasip@1405
   438
    void *myVf2; //used in Vf2Wizard::find
madarasip@1405
   439
madarasip@1405
   440
madarasip@1350
   441
    typedef bits::vf2::AlwaysEq NodeEq;
madarasip@1350
   442
    NodeEq _node_eq;
madarasip@1350
   443
madarasip@1350
   444
    Vf2WizardBase(const G1 &g1,const G2 &g2)
madarasip@1405
   445
      : _g1(g1), _g2(g2), _mapping_type(SUBGRAPH), _local_mapping(true) { }
madarasip@1350
   446
  };
madarasip@1350
   447
madarasip@1405
   448
alpar@1351
   449
  /// Auxiliary class for the function-type interface of %VF2 algorithm.
kpeter@1407
   450
  ///
alpar@1351
   451
  /// This auxiliary class implements the named parameters of
alpar@1351
   452
  /// \ref vf2() "function-type interface" of \ref Vf2 algorithm.
alpar@1351
   453
  ///
kpeter@1407
   454
  /// \warning This class is not to be used directly.
alpar@1351
   455
  ///
alpar@1351
   456
  /// \tparam TR The traits class that defines various types used by the
alpar@1351
   457
  /// algorithm.
madarasip@1350
   458
  template<class TR>
madarasip@1405
   459
  class Vf2Wizard : public TR {
madarasip@1350
   460
    typedef TR Base;
madarasip@1350
   461
    typedef typename TR::Graph1 Graph1;
madarasip@1350
   462
    typedef typename TR::Graph2 Graph2;
madarasip@1350
   463
madarasip@1350
   464
    typedef typename TR::Mapping Mapping;
madarasip@1350
   465
    typedef typename TR::NodeEq NodeEq;
madarasip@1350
   466
madarasip@1350
   467
    using TR::_g1;
madarasip@1350
   468
    using TR::_g2;
madarasip@1350
   469
    using TR::_mapping_type;
madarasip@1350
   470
    using TR::_mapping;
madarasip@1350
   471
    using TR::_node_eq;
madarasip@1350
   472
madarasip@1350
   473
  public:
alpar@1351
   474
    ///Constructor
kpeter@1407
   475
    Vf2Wizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {}
madarasip@1350
   476
madarasip@1350
   477
    ///Copy constructor
kpeter@1407
   478
    Vf2Wizard(const Base &b) : Base(b) {}
madarasip@1405
   479
madarasip@1405
   480
    ///Copy constructor
madarasip@1405
   481
    Vf2Wizard(const Vf2Wizard &b) : Base(b) {}
madarasip@1350
   482
madarasip@1350
   483
madarasip@1350
   484
    template<class T>
madarasip@1405
   485
    struct SetMappingBase : public Base{
madarasip@1350
   486
      typedef T Mapping;
madarasip@1350
   487
      SetMappingBase(const Base &b) : Base(b) {}
madarasip@1350
   488
    };
madarasip@1350
   489
madarasip@1350
   490
    ///\brief \ref named-templ-param "Named parameter" for setting
madarasip@1350
   491
    ///the mapping.
madarasip@1350
   492
    ///
madarasip@1350
   493
    ///\ref named-templ-param "Named parameter" function for setting
madarasip@1350
   494
    ///the map that stores the found embedding.
madarasip@1350
   495
    template<class T>
madarasip@1405
   496
    Vf2Wizard< SetMappingBase<T> > mapping(const T &t) {
madarasip@1350
   497
      Base::_mapping=reinterpret_cast<void*>(const_cast<T*>(&t));
madarasip@1350
   498
      Base::_local_mapping = false;
madarasip@1350
   499
      return Vf2Wizard<SetMappingBase<T> >(*this);
madarasip@1350
   500
    }
madarasip@1350
   501
madarasip@1350
   502
    template<class NE>
madarasip@1350
   503
    struct SetNodeEqBase : public Base {
madarasip@1350
   504
      typedef NE NodeEq;
madarasip@1350
   505
      NodeEq _node_eq;
madarasip@1350
   506
      SetNodeEqBase(const Base &b, const NE &node_eq)
madarasip@1405
   507
        : Base(b), _node_eq(node_eq){
madarasip@1405
   508
      }
madarasip@1350
   509
    };
madarasip@1350
   510
madarasip@1350
   511
    ///\brief \ref named-templ-param "Named parameter" for setting
madarasip@1350
   512
    ///the node equivalence relation.
madarasip@1350
   513
    ///
madarasip@1350
   514
    ///\ref named-templ-param "Named parameter" function for setting
madarasip@1350
   515
    ///the equivalence relation between the nodes.
alpar@1351
   516
    ///
alpar@1351
   517
    ///\param node_eq A bool-valued binary functor determinining
alpar@1351
   518
    ///whether a node is mappable to another. By default it is an
alpar@1351
   519
    ///always true operator.
madarasip@1350
   520
    template<class T>
madarasip@1405
   521
    Vf2Wizard< SetNodeEqBase<T> > nodeEq(const T &node_eq) {
madarasip@1350
   522
      return Vf2Wizard<SetNodeEqBase<T> >(SetNodeEqBase<T>(*this,node_eq));
madarasip@1350
   523
    }
madarasip@1350
   524
madarasip@1350
   525
    ///\brief \ref named-templ-param "Named parameter" for setting
madarasip@1350
   526
    ///the node labels.
madarasip@1350
   527
    ///
madarasip@1350
   528
    ///\ref named-templ-param "Named parameter" function for setting
madarasip@1350
   529
    ///the node labels defining equivalence relation between them.
alpar@1351
   530
    ///
madarasip@1405
   531
    ///\param m1 An arbitrary \ref concepts::ReadMap "readable node map"
alpar@1353
   532
    ///of g1.
madarasip@1405
   533
    ///\param m2 An arbitrary \ref concepts::ReadMap "readable node map"
alpar@1353
   534
    ///of g2.
alpar@1351
   535
    ///
alpar@1351
   536
    ///The value type of these maps must be equal comparable.
madarasip@1350
   537
    template<class M1, class M2>
madarasip@1350
   538
    Vf2Wizard< SetNodeEqBase<bits::vf2::MapEq<M1,M2> > >
madarasip@1405
   539
    nodeLabels(const M1 &m1,const M2 &m2){
madarasip@1350
   540
      return nodeEq(bits::vf2::MapEq<M1,M2>(m1,m2));
madarasip@1350
   541
    }
madarasip@1350
   542
alpar@1351
   543
    ///\brief \ref named-templ-param "Named parameter" for setting
alpar@1351
   544
    ///the mapping type.
alpar@1351
   545
    ///
alpar@1351
   546
    ///\ref named-templ-param "Named parameter" for setting
alpar@1351
   547
    ///the mapping type.
alpar@1351
   548
    ///
alpar@1351
   549
    ///The mapping type is set to \ref SUBGRAPH by default.
alpar@1351
   550
    ///
madarasip@1405
   551
    ///\sa See \ref MappingType for the possible values.
madarasip@1405
   552
    Vf2Wizard<Base> &mappingType(MappingType m_type) {
madarasip@1350
   553
      _mapping_type = m_type;
madarasip@1350
   554
      return *this;
madarasip@1350
   555
    }
madarasip@1350
   556
alpar@1351
   557
    ///\brief \ref named-templ-param "Named parameter" for setting
alpar@1351
   558
    ///the mapping type to \ref INDUCED.
alpar@1351
   559
    ///
alpar@1351
   560
    ///\ref named-templ-param "Named parameter" for setting
alpar@1351
   561
    ///the mapping type to \ref INDUCED.
madarasip@1405
   562
    Vf2Wizard<Base> &induced() {
madarasip@1350
   563
      _mapping_type = INDUCED;
madarasip@1350
   564
      return *this;
madarasip@1350
   565
    }
madarasip@1350
   566
alpar@1351
   567
    ///\brief \ref named-templ-param "Named parameter" for setting
alpar@1351
   568
    ///the mapping type to \ref ISOMORPH.
alpar@1351
   569
    ///
alpar@1351
   570
    ///\ref named-templ-param "Named parameter" for setting
alpar@1351
   571
    ///the mapping type to \ref ISOMORPH.
madarasip@1405
   572
    Vf2Wizard<Base> &iso() {
madarasip@1350
   573
      _mapping_type = ISOMORPH;
madarasip@1350
   574
      return *this;
madarasip@1350
   575
    }
madarasip@1350
   576
madarasip@1405
   577
alpar@1351
   578
    ///Runs VF2 algorithm.
alpar@1351
   579
alpar@1351
   580
    ///This method runs VF2 algorithm.
alpar@1351
   581
    ///
alpar@1351
   582
    ///\retval true if a mapping is found.
madarasip@1405
   583
    ///\retval false if there is no mapping.
madarasip@1405
   584
    bool run(){
madarasip@1350
   585
      if(Base::_local_mapping)
madarasip@1350
   586
        Base::createMapping();
madarasip@1350
   587
madarasip@1350
   588
      Vf2<Graph1, Graph2, Mapping, NodeEq >
madarasip@1350
   589
        alg(_g1, _g2, *reinterpret_cast<Mapping*>(_mapping), _node_eq);
madarasip@1350
   590
madarasip@1350
   591
      alg.mappingType(_mapping_type);
madarasip@1350
   592
madarasip@1350
   593
      bool ret = alg.find();
madarasip@1350
   594
madarasip@1350
   595
      if(Base::_local_mapping)
madarasip@1350
   596
        delete reinterpret_cast<Mapping*>(_mapping);
madarasip@1350
   597
madarasip@1350
   598
      return ret;
madarasip@1350
   599
    }
madarasip@1405
   600
madarasip@1405
   601
    ///Get a pointer to the generated Vf2 object.
madarasip@1405
   602
madarasip@1405
   603
    ///Gives a pointer to the generated Vf2 object.
madarasip@1405
   604
    ///
madarasip@1405
   605
    ///\return Pointer to the generated Vf2 object.
madarasip@1405
   606
    ///\warning Don't forget to delete the referred Vf2 object after use.
madarasip@1405
   607
    Vf2<Graph1, Graph2, Mapping, NodeEq >* getPtrToVf2Object() {
madarasip@1405
   608
      if(Base::_local_mapping)
madarasip@1405
   609
        Base::createMapping();
madarasip@1405
   610
      Vf2<Graph1, Graph2, Mapping, NodeEq >* ptr =
madarasip@1405
   611
        new Vf2<Graph1, Graph2, Mapping, NodeEq>
madarasip@1405
   612
        (_g1, _g2, *reinterpret_cast<Mapping*>(_mapping), _node_eq);
madarasip@1405
   613
      ptr->mappingType(_mapping_type);
madarasip@1405
   614
      if(Base::_local_mapping)
madarasip@1405
   615
        ptr->_deallocMappingAfterUse = true;
madarasip@1405
   616
      return ptr;
madarasip@1405
   617
    }
madarasip@1405
   618
madarasip@1405
   619
    ///Counts the number of mappings.
madarasip@1405
   620
madarasip@1405
   621
    ///This method counts the number of mappings.
madarasip@1405
   622
    ///
madarasip@1405
   623
    /// \return The number of mappings.
madarasip@1405
   624
    int count() {
madarasip@1405
   625
      if(Base::_local_mapping)
madarasip@1405
   626
        Base::createMapping();
madarasip@1405
   627
madarasip@1405
   628
      Vf2<Graph1, Graph2, Mapping, NodeEq>
madarasip@1405
   629
        alg(_g1, _g2, *reinterpret_cast<Mapping*>(_mapping), _node_eq);
madarasip@1405
   630
      if(Base::_local_mapping)
madarasip@1405
   631
        alg._deallocMappingAfterUse = true;
madarasip@1405
   632
      alg.mappingType(_mapping_type);
madarasip@1405
   633
madarasip@1405
   634
      int ret = 0;
madarasip@1405
   635
      while(alg.find())
madarasip@1405
   636
        ++ret;
madarasip@1405
   637
madarasip@1405
   638
      return ret;
madarasip@1405
   639
    }
madarasip@1350
   640
  };
madarasip@1350
   641
alpar@1351
   642
  ///Function-type interface for VF2 algorithm.
alpar@1351
   643
alpar@1351
   644
  /// \ingroup graph_isomorphism
alpar@1351
   645
  ///Function-type interface for VF2 algorithm \cite cordella2004sub.
alpar@1351
   646
  ///
alpar@1351
   647
  ///This function has several \ref named-func-param "named parameters"
alpar@1351
   648
  ///declared as the members of class \ref Vf2Wizard.
alpar@1351
   649
  ///The following examples show how to use these parameters.
alpar@1351
   650
  ///\code
madarasip@1405
   651
  ///  // Find an embedding of graph g1 into graph g2
alpar@1351
   652
  ///  ListGraph::NodeMap<ListGraph::Node> m(g);
madarasip@1405
   653
  ///  vf2(g1,g2).mapping(m).run();
alpar@1351
   654
  ///
madarasip@1405
   655
  ///  // Check whether graphs g1 and g2 are isomorphic
madarasip@1405
   656
  ///  bool is_iso = vf2(g1,g2).iso().run();
madarasip@1405
   657
  ///
madarasip@1405
   658
  ///  // Count the number of isomorphisms
madarasip@1405
   659
  ///  int num_isos = vf2(g1,g2).iso().count();
madarasip@1405
   660
  ///
madarasip@1405
   661
  ///  // Iterate through all the induced subgraph mappings of graph g1 into g2
madarasip@1405
   662
  ///  auto* myVf2 = vf2(g1,g2).mapping(m).nodeLabels(c1,c2)
madarasip@1405
   663
  ///  .induced().getPtrToVf2Object();
madarasip@1405
   664
  ///  while(myVf2->find()){
madarasip@1405
   665
  ///    //process the current mapping m
madarasip@1405
   666
  ///  }
madarasip@1405
   667
  ///  delete myVf22;
alpar@1351
   668
  ///\endcode
madarasip@1405
   669
  ///\warning Don't forget to put the \ref Vf2Wizard::run() "run()",
madarasip@1405
   670
  ///\ref Vf2Wizard::count() "count()" or
madarasip@1405
   671
  ///the \ref Vf2Wizard::getPtrToVf2Object() "getPtrToVf2Object()"
alpar@1351
   672
  ///to the end of the expression.
alpar@1351
   673
  ///\sa Vf2Wizard
alpar@1351
   674
  ///\sa Vf2
madarasip@1350
   675
  template<class G1, class G2>
madarasip@1405
   676
  Vf2Wizard<Vf2WizardBase<G1,G2> > vf2(const G1 &g1, const G2 &g2) {
madarasip@1350
   677
    return Vf2Wizard<Vf2WizardBase<G1,G2> >(g1,g2);
madarasip@1350
   678
  }
madarasip@1350
   679
madarasip@1350
   680
}
madarasip@1350
   681
madarasip@1350
   682
#endif