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