Vf2 improvements and Vf2pp implementation (#597)
authorPeter Madarasi <madarasip@caesar.elte.hu>
Tue, 19 Sep 2017 14:08:20 +0200
changeset 11863feba0ea1bda
parent 1160 bc571f16e1e9
child 1187 120b9031eada
Vf2 improvements and Vf2pp implementation (#597)
lemon/bits/vf2_internals.h
lemon/vf2.h
lemon/vf2pp.h
test/CMakeLists.txt
test/vf2_test.cc
test/vf2pp_test.cc
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/lemon/bits/vf2_internals.h	Tue Sep 19 14:08:20 2017 +0200
     1.3 @@ -0,0 +1,48 @@
     1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     1.5 + *
     1.6 + * This file is a part of LEMON, a generic C++ optimization library.
     1.7 + *
     1.8 + * Copyright (C) 2015-2017
     1.9 + * EMAXA Kutato-fejleszto Kft. (EMAXA Research Ltd.)
    1.10 + *
    1.11 + * Permission to use, modify and distribute this software is granted
    1.12 + * provided that this copyright notice appears in all copies. For
    1.13 + * precise terms see the accompanying LICENSE file.
    1.14 + *
    1.15 + * This software is provided "AS IS" with no warranty of any kind,
    1.16 + * express or implied, and with no claim as to its suitability for any
    1.17 + * purpose.
    1.18 + *
    1.19 + */
    1.20 +
    1.21 +#ifndef VF2_INTERNALS_H
    1.22 +#define VF2_INTERNALS_H
    1.23 +
    1.24 +
    1.25 +///\ingroup graph_properties
    1.26 +///\file
    1.27 +///\brief Mapping types for graph matching algorithms.
    1.28 +
    1.29 +namespace lemon {
    1.30 +  ///\ingroup graph_isomorphism
    1.31 +  ///The \ref Vf2 "VF2" algorithm is capable of finding different kind of
    1.32 +  ///embeddings, this enum specifies its type.
    1.33 +  ///
    1.34 +  ///See \ref graph_isomorphism for a more detailed description.
    1.35 +  enum MappingType {
    1.36 +    /// Subgraph isomorphism
    1.37 +    SUBGRAPH = 0,
    1.38 +    /// Induced subgraph isomorphism
    1.39 +    INDUCED = 1,
    1.40 +    /// Graph isomorphism
    1.41 +
    1.42 +    /// If the two graph has the same number of nodes, than it is
    1.43 +    /// equivalent to \ref INDUCED, and if they also have the same
    1.44 +    /// number of edges, then it is also equivalent to \ref SUBGRAPH.
    1.45 +    ///
    1.46 +    /// However, using this setting is faster than the other two
    1.47 +    /// options.
    1.48 +    ISOMORPH = 2
    1.49 +  };
    1.50 +}
    1.51 +#endif
     2.1 --- a/lemon/vf2.h	Tue Sep 19 15:23:43 2017 +0200
     2.2 +++ b/lemon/vf2.h	Tue Sep 19 14:08:20 2017 +0200
     2.3 @@ -2,7 +2,7 @@
     2.4   *
     2.5   * This file is a part of LEMON, a generic C++ optimization library.
     2.6   *
     2.7 - * Copyright (C) 2015
     2.8 + * Copyright (C) 2015-2017
     2.9   * EMAXA Kutato-fejleszto Kft. (EMAXA Research Ltd.)
    2.10   *
    2.11   * Permission to use, modify and distribute this software is granted
    2.12 @@ -26,95 +26,64 @@
    2.13  #include <lemon/concepts/graph.h>
    2.14  #include <lemon/dfs.h>
    2.15  #include <lemon/bfs.h>
    2.16 +#include <lemon/bits/vf2_internals.h>
    2.17  
    2.18  #include <vector>
    2.19 -#include <set>
    2.20  
    2.21 -namespace lemon
    2.22 -{
    2.23 -  namespace bits
    2.24 -  {
    2.25 -    namespace vf2
    2.26 -    {
    2.27 -      class AlwaysEq
    2.28 -      {
    2.29 +namespace lemon {
    2.30 +  namespace bits {
    2.31 +    namespace vf2 {
    2.32 +
    2.33 +      class AlwaysEq {
    2.34        public:
    2.35          template<class T1, class T2>
    2.36 -        bool operator()(T1, T2) const
    2.37 -        {
    2.38 +        bool operator()(T1&, T2&) const {
    2.39            return true;
    2.40          }
    2.41        };
    2.42  
    2.43        template<class M1, class M2>
    2.44 -      class MapEq
    2.45 -      {
    2.46 +      class MapEq{
    2.47          const M1 &_m1;
    2.48          const M2 &_m2;
    2.49        public:
    2.50 -        MapEq(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
    2.51 -        bool operator()(typename M1::Key k1, typename M2::Key k2) const
    2.52 -        {
    2.53 +        MapEq(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) { }
    2.54 +        bool operator()(typename M1::Key k1, typename M2::Key k2) const {
    2.55            return _m1[k1] == _m2[k2];
    2.56          }
    2.57        };
    2.58  
    2.59 +
    2.60 +
    2.61        template <class G>
    2.62 -      class DfsLeaveOrder : public DfsVisitor<G>
    2.63 -      {
    2.64 +      class DfsLeaveOrder : public DfsVisitor<G> {
    2.65          const G &_g;
    2.66          std::vector<typename G::Node> &_order;
    2.67          int i;
    2.68        public:
    2.69          DfsLeaveOrder(const G &g, std::vector<typename G::Node> &order)
    2.70 -          : i(countNodes(g)), _g(g), _order(order)
    2.71 -        {}
    2.72 -        void leave(const typename G::Node &node)
    2.73 -        {
    2.74 +          : i(countNodes(g)), _g(g), _order(order) { }
    2.75 +        void leave(const typename G::Node &node) {
    2.76            _order[--i]=node;
    2.77          }
    2.78        };
    2.79  
    2.80        template <class G>
    2.81 -      class BfsLeaveOrder : public BfsVisitor<G>
    2.82 -      {
    2.83 +      class BfsLeaveOrder : public BfsVisitor<G> {
    2.84          int i;
    2.85          const G &_g;
    2.86          std::vector<typename G::Node> &_order;
    2.87        public:
    2.88          BfsLeaveOrder(const G &g, std::vector<typename G::Node> &order)
    2.89 -          : i(0), _g(g), _order(order)
    2.90 -        {}
    2.91 -        void process(const typename G::Node &node)
    2.92 -        {
    2.93 +          : i(0), _g(g), _order(order){
    2.94 +        }
    2.95 +        void process(const typename G::Node &node) {
    2.96            _order[i++]=node;
    2.97          }
    2.98        };
    2.99      }
   2.100    }
   2.101  
   2.102 -  ///Graph mapping types.
   2.103 -
   2.104 -  ///\ingroup graph_isomorphism
   2.105 -  ///The \ref Vf2 "VF2" algorithm is capable of finding different kind of
   2.106 -  ///embeddings, this enum specifies its type.
   2.107 -  ///
   2.108 -  ///See \ref graph_isomorphism for a more detailed description.
   2.109 -  enum Vf2MappingType {
   2.110 -    /// Subgraph isomorphism
   2.111 -    SUBGRAPH = 0,
   2.112 -    /// Induced subgraph isomorphism
   2.113 -    INDUCED = 1,
   2.114 -    /// Graph isomorphism
   2.115 -
   2.116 -    /// If the two graph has the same number of nodes, than it is
   2.117 -    /// equivalent to \ref INDUCED, and if they also have the same
   2.118 -    /// number of edges, then it is also equivalent to \ref SUBGRAPH.
   2.119 -    ///
   2.120 -    /// However, using this setting is faster than the other two
   2.121 -    /// options.
   2.122 -    ISOMORPH = 2
   2.123 -  };
   2.124  
   2.125    ///%VF2 algorithm class.
   2.126  
   2.127 @@ -144,130 +113,122 @@
   2.128             class M = typename G1::template NodeMap<G2::Node>,
   2.129             class NEQ = bits::vf2::AlwaysEq >
   2.130  #endif
   2.131 -  class Vf2
   2.132 -  {
   2.133 +  class Vf2 {
   2.134      //Current depth in the DFS tree.
   2.135      int _depth;
   2.136      //Functor with bool operator()(G1::Node,G2::Node), which returns 1
   2.137 -    //if and only if the 2 nodes are equivalent.
   2.138 +    //ifff the two nodes are equivalent.
   2.139      NEQ _nEq;
   2.140  
   2.141      typename G2::template NodeMap<int> _conn;
   2.142      //Current mapping. We index it by the nodes of g1, and match[v] is
   2.143      //a node of g2.
   2.144      M &_mapping;
   2.145 -    //order[i] is the node of g1, for which we find a pair if depth=i
   2.146 +    //order[i] is the node of g1, for which we search a pair if depth=i
   2.147      std::vector<typename G1::Node> order;
   2.148      //currEdgeIts[i] is an edge iterator, witch is last used in the ith
   2.149      //depth to find a pair for order[i].
   2.150      std::vector<typename G2::IncEdgeIt> currEdgeIts;
   2.151      //The small graph.
   2.152      const G1 &_g1;
   2.153 -    //The big graph.
   2.154 +    //The large graph.
   2.155      const G2 &_g2;
   2.156 -    //lookup tables for cut the searchtree
   2.157 +    //lookup tables for cutting the searchtree
   2.158      typename G1::template NodeMap<int> rNew1t,rInOut1t;
   2.159  
   2.160 -    Vf2MappingType _mapping_type;
   2.161 +    MappingType _mapping_type;
   2.162 +
   2.163 +    bool _deallocMappingAfterUse;
   2.164  
   2.165      //cut the search tree
   2.166 -    template<Vf2MappingType MT>
   2.167 -    bool cut(const typename G1::Node n1,const typename G2::Node n2) const
   2.168 -    {
   2.169 +    template<MappingType MT>
   2.170 +    bool cut(const typename G1::Node n1,const typename G2::Node n2) const {
   2.171        int rNew2=0,rInOut2=0;
   2.172 -      for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2)
   2.173 -        {
   2.174 -          const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
   2.175 -          if(_conn[currNode]>0)
   2.176 -            ++rInOut2;
   2.177 -          else if(MT!=SUBGRAPH&&_conn[currNode]==0)
   2.178 -            ++rNew2;
   2.179 -        }
   2.180 -      switch(MT)
   2.181 -        {
   2.182 -        case INDUCED:
   2.183 -          return rInOut1t[n1]<=rInOut2&&rNew1t[n1]<=rNew2;
   2.184 -        case SUBGRAPH:
   2.185 -          return rInOut1t[n1]<=rInOut2;
   2.186 -        case ISOMORPH:
   2.187 -          return rInOut1t[n1]==rInOut2&&rNew1t[n1]==rNew2;
   2.188 -        default:
   2.189 -          return false;
   2.190 -        }
   2.191 +      for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
   2.192 +        const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
   2.193 +        if(_conn[currNode]>0)
   2.194 +          ++rInOut2;
   2.195 +        else if(MT!=SUBGRAPH&&_conn[currNode]==0)
   2.196 +          ++rNew2;
   2.197 +      }
   2.198 +      switch(MT) {
   2.199 +      case INDUCED:
   2.200 +        return rInOut1t[n1]<=rInOut2&&rNew1t[n1]<=rNew2;
   2.201 +      case SUBGRAPH:
   2.202 +        return rInOut1t[n1]<=rInOut2;
   2.203 +      case ISOMORPH:
   2.204 +        return rInOut1t[n1]==rInOut2&&rNew1t[n1]==rNew2;
   2.205 +      default:
   2.206 +        return false;
   2.207 +      }
   2.208      }
   2.209  
   2.210 -    template<Vf2MappingType MT>
   2.211 -    bool feas(const typename G1::Node n1,const typename G2::Node n2)
   2.212 -    {
   2.213 +    template<MappingType MT>
   2.214 +    bool feas(const typename G1::Node n1,const typename G2::Node n2) {
   2.215        if(!_nEq(n1,n2))
   2.216          return 0;
   2.217  
   2.218 -      for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1)
   2.219 -        {
   2.220 -          const typename G1::Node currNode=_g1.oppositeNode(n1,e1);
   2.221 -          if(_mapping[currNode]!=INVALID)
   2.222 -            --_conn[_mapping[currNode]];
   2.223 +      for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
   2.224 +        const typename G1::Node& currNode=_g1.oppositeNode(n1,e1);
   2.225 +        if(_mapping[currNode]!=INVALID)
   2.226 +          --_conn[_mapping[currNode]];
   2.227 +      }
   2.228 +      bool isIso=1;
   2.229 +      for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
   2.230 +        int& connCurrNode = _conn[_g2.oppositeNode(n2,e2)];
   2.231 +        if(connCurrNode<-1)
   2.232 +          ++connCurrNode;
   2.233 +        else if(MT!=SUBGRAPH&&connCurrNode==-1) {
   2.234 +          isIso=0;
   2.235 +          break;
   2.236          }
   2.237 -      bool isIso=1;
   2.238 -      for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2)
   2.239 -        {
   2.240 -          const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
   2.241 -          if(_conn[currNode]<-1)
   2.242 -            ++_conn[currNode];
   2.243 -          else if(MT!=SUBGRAPH&&_conn[currNode]==-1)
   2.244 -            {
   2.245 +      }
   2.246 +
   2.247 +      for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
   2.248 +        const typename G2::Node& currNodePair=_mapping[_g1.oppositeNode(n1,e1)];
   2.249 +        int& connCurrNodePair=_conn[currNodePair];
   2.250 +        if(currNodePair!=INVALID&&connCurrNodePair!=-1) {
   2.251 +          switch(MT) {
   2.252 +          case INDUCED:
   2.253 +          case ISOMORPH:
   2.254 +            isIso=0;
   2.255 +            break;
   2.256 +          case SUBGRAPH:
   2.257 +            if(connCurrNodePair<-1)
   2.258                isIso=0;
   2.259 -              break;
   2.260 -            }
   2.261 +            break;
   2.262 +          }
   2.263 +          connCurrNodePair=-1;
   2.264          }
   2.265 -
   2.266 -      for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1)
   2.267 -        {
   2.268 -          const typename G1::Node currNode=_g1.oppositeNode(n1,e1);
   2.269 -          if(_mapping[currNode]!=INVALID&&_conn[_mapping[currNode]]!=-1)
   2.270 -            {
   2.271 -              switch(MT)
   2.272 -                {
   2.273 -                case INDUCED:
   2.274 -                case ISOMORPH:
   2.275 -                  isIso=0;
   2.276 -                  break;
   2.277 -                case SUBGRAPH:
   2.278 -                  if(_conn[_mapping[currNode]]<-1)
   2.279 -                    isIso=0;
   2.280 -                  break;
   2.281 -                }
   2.282 -              _conn[_mapping[currNode]]=-1;
   2.283 -            }
   2.284 -        }
   2.285 +      }
   2.286        return isIso&&cut<MT>(n1,n2);
   2.287      }
   2.288  
   2.289 -    void addPair(const typename G1::Node n1,const typename G2::Node n2)
   2.290 -    {
   2.291 +    void addPair(const typename G1::Node n1,const typename G2::Node n2) {
   2.292        _conn[n2]=-1;
   2.293        _mapping.set(n1,n2);
   2.294 -      for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2)
   2.295 -        if(_conn[_g2.oppositeNode(n2,e2)]!=-1)
   2.296 -          ++_conn[_g2.oppositeNode(n2,e2)];
   2.297 +      for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
   2.298 +        int& currConn = _conn[_g2.oppositeNode(n2,e2)];
   2.299 +        if(currConn!=-1)
   2.300 +          ++currConn;
   2.301 +      }
   2.302      }
   2.303  
   2.304 -    void subPair(const typename G1::Node n1,const typename G2::Node n2)
   2.305 -    {
   2.306 +    void subPair(const typename G1::Node n1,const typename G2::Node n2) {
   2.307        _conn[n2]=0;
   2.308        _mapping.set(n1,INVALID);
   2.309 -      for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2)
   2.310 -        {
   2.311 -          const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
   2.312 -          if(_conn[currNode]>0)
   2.313 -            --_conn[currNode];
   2.314 -          else if(_conn[currNode]==-1)
   2.315 -            ++_conn[n2];
   2.316 -        }
   2.317 +      for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
   2.318 +        int& currConn = _conn[_g2.oppositeNode(n2,e2)];
   2.319 +        if(currConn>0)
   2.320 +          --currConn;
   2.321 +        else if(currConn==-1)
   2.322 +          ++_conn[n2];
   2.323 +      }
   2.324      }
   2.325  
   2.326 -    void setOrder()//we will find pairs for the nodes of g1 in this order
   2.327 -    {
   2.328 +    void setOrder() {
   2.329 +      // we will find pairs for the nodes of g1 in this order
   2.330 +
   2.331        // bits::vf2::DfsLeaveOrder<G1> v(_g1,order);
   2.332        //   DfsVisit<G1,bits::vf2::DfsLeaveOrder<G1> >dfs(_g1, v);
   2.333        //   dfs.run();
   2.334 @@ -278,117 +239,103 @@
   2.335        bfs.run();
   2.336      }
   2.337  
   2.338 -    template<Vf2MappingType MT>
   2.339 -    bool extMatch()
   2.340 -    {
   2.341 -      while(_depth>=0)
   2.342 -        {
   2.343 -          //there are not nodes in g1, which has not pair in g2.
   2.344 -          if(_depth==static_cast<int>(order.size()))
   2.345 -            {
   2.346 +    template<MappingType MT>
   2.347 +    bool extMatch() {
   2.348 +      while(_depth>=0) {
   2.349 +        //there are not nodes in g1, which has not pair in g2.
   2.350 +        if(_depth==static_cast<int>(order.size())) {
   2.351 +          --_depth;
   2.352 +          return true;
   2.353 +        }
   2.354 +        typename G1::Node& nodeOfDepth = order[_depth];
   2.355 +        const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth];
   2.356 +        typename G2::IncEdgeIt &edgeItOfDepth = currEdgeIts[_depth];
   2.357 +        //the node of g2, which neighbours are the candidates for
   2.358 +        //the pair of nodeOfDepth
   2.359 +        typename G2::Node currPNode;
   2.360 +        if(edgeItOfDepth==INVALID) {
   2.361 +          typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth);
   2.362 +          //if pairOfNodeOfDepth!=INVALID, we dont use
   2.363 +          //fstMatchedE
   2.364 +          if(pairOfNodeOfDepth==INVALID)
   2.365 +            for(; fstMatchedE!=INVALID &&
   2.366 +                  _mapping[_g1.oppositeNode(nodeOfDepth,
   2.367 +                                            fstMatchedE)]==INVALID;
   2.368 +                ++fstMatchedE) ; //find fstMatchedE
   2.369 +          if(fstMatchedE==INVALID||pairOfNodeOfDepth!=INVALID) {
   2.370 +            //We found no covered neighbours, this means
   2.371 +            //the graph is not connected(or _depth==0).  Each
   2.372 +            //uncovered(and there are some other properties due
   2.373 +            //to the spec. problem types) node of g2 is
   2.374 +            //candidate.  We can read the iterator of the last
   2.375 +            //tried node from the match if it is not the first
   2.376 +            //try(match[nodeOfDepth]!=INVALID)
   2.377 +            typename G2::NodeIt n2(_g2);
   2.378 +            //if it's not the first try
   2.379 +            if(pairOfNodeOfDepth!=INVALID) {
   2.380 +              n2=++typename G2::NodeIt(_g2,pairOfNodeOfDepth);
   2.381 +              subPair(nodeOfDepth,pairOfNodeOfDepth);
   2.382 +            }
   2.383 +            for(; n2!=INVALID; ++n2)
   2.384 +              if(MT!=SUBGRAPH) {
   2.385 +                if(_conn[n2]==0&&feas<MT>(nodeOfDepth,n2))
   2.386 +                  break;
   2.387 +              }
   2.388 +              else if(_conn[n2]>=0&&feas<MT>(nodeOfDepth,n2))
   2.389 +                break;
   2.390 +            // n2 is the next candidate
   2.391 +            if(n2!=INVALID){
   2.392 +              addPair(nodeOfDepth,n2);
   2.393 +              ++_depth;
   2.394 +            }
   2.395 +            else // there are no more candidates
   2.396                --_depth;
   2.397 -              return true;
   2.398 -            }
   2.399 -          //the node of g2, which neighbours are the candidates for
   2.400 -          //the pair of order[_depth]
   2.401 -          typename G2::Node currPNode;
   2.402 -          if(currEdgeIts[_depth]==INVALID)
   2.403 -            {
   2.404 -              typename G1::IncEdgeIt fstMatchedE(_g1,order[_depth]);
   2.405 -              //if _mapping[order[_depth]]!=INVALID, we dont use
   2.406 -              //fstMatchedE
   2.407 -              if(_mapping[order[_depth]]==INVALID)
   2.408 -                for(; fstMatchedE!=INVALID &&
   2.409 -                      _mapping[_g1.oppositeNode(order[_depth],
   2.410 -                                              fstMatchedE)]==INVALID;
   2.411 -                    ++fstMatchedE) ; //find fstMatchedE
   2.412 -              if(fstMatchedE==INVALID||_mapping[order[_depth]]!=INVALID)
   2.413 -                {
   2.414 -                  //We did not find an covered neighbour, this means
   2.415 -                  //the graph is not connected(or _depth==0).  Every
   2.416 -                  //uncovered(and there are some other properties due
   2.417 -                  //to the spec. problem types) node of g2 is
   2.418 -                  //candidate.  We can read the iterator of the last
   2.419 -                  //tryed node from the match if it is not the first
   2.420 -                  //try(match[order[_depth]]!=INVALID)
   2.421 -                  typename G2::NodeIt n2(_g2);
   2.422 -                  //if its not the first try
   2.423 -                  if(_mapping[order[_depth]]!=INVALID)
   2.424 -                    {
   2.425 -                      n2=++typename G2::NodeIt(_g2,_mapping[order[_depth]]);
   2.426 -                      subPair(order[_depth],_mapping[order[_depth]]);
   2.427 -                    }
   2.428 -                  for(; n2!=INVALID; ++n2)
   2.429 -                    if(MT!=SUBGRAPH&&_conn[n2]==0)
   2.430 -                      {
   2.431 -                        if(feas<MT>(order[_depth],n2))
   2.432 -                          break;
   2.433 -                      }
   2.434 -                    else if(MT==SUBGRAPH&&_conn[n2]>=0)
   2.435 -                      if(feas<MT>(order[_depth],n2))
   2.436 -                        break;
   2.437 -                  // n2 is the next candidate
   2.438 -                  if(n2!=INVALID)
   2.439 -                    {
   2.440 -                      addPair(order[_depth],n2);
   2.441 -                      ++_depth;
   2.442 -                    }
   2.443 -                  else // there is no more candidate
   2.444 -                    --_depth;
   2.445 -                  continue;
   2.446 -                }
   2.447 -              else
   2.448 -                {
   2.449 -                  currPNode=_mapping[_g1.oppositeNode(order[_depth],
   2.450 -                                                      fstMatchedE)];
   2.451 -                  currEdgeIts[_depth]=typename G2::IncEdgeIt(_g2,currPNode);
   2.452 -                }
   2.453 -            }
   2.454 -          else
   2.455 -            {
   2.456 -              currPNode=_g2.oppositeNode(_mapping[order[_depth]],
   2.457 -                                         currEdgeIts[_depth]);
   2.458 -              subPair(order[_depth],_mapping[order[_depth]]);
   2.459 -              ++currEdgeIts[_depth];
   2.460 -            }
   2.461 -          for(; currEdgeIts[_depth]!=INVALID; ++currEdgeIts[_depth])
   2.462 -            {
   2.463 -              const typename G2::Node currNode =
   2.464 -                _g2.oppositeNode(currPNode, currEdgeIts[_depth]);
   2.465 -              //if currNode is uncovered
   2.466 -              if(_conn[currNode]>0&&feas<MT>(order[_depth],currNode))
   2.467 -                {
   2.468 -                  addPair(order[_depth],currNode);
   2.469 -                  break;
   2.470 -                }
   2.471 -            }
   2.472 -          currEdgeIts[_depth]==INVALID?--_depth:++_depth;
   2.473 +            continue;
   2.474 +          }
   2.475 +          else {
   2.476 +            currPNode=_mapping[_g1.oppositeNode(nodeOfDepth,
   2.477 +                                                fstMatchedE)];
   2.478 +            edgeItOfDepth=typename G2::IncEdgeIt(_g2,currPNode);
   2.479 +          }
   2.480          }
   2.481 +        else {
   2.482 +          currPNode=_g2.oppositeNode(pairOfNodeOfDepth,
   2.483 +                                     edgeItOfDepth);
   2.484 +          subPair(nodeOfDepth,pairOfNodeOfDepth);
   2.485 +          ++edgeItOfDepth;
   2.486 +        }
   2.487 +        for(; edgeItOfDepth!=INVALID; ++edgeItOfDepth) {
   2.488 +          const typename G2::Node currNode =
   2.489 +            _g2.oppositeNode(currPNode, edgeItOfDepth);
   2.490 +          if(_conn[currNode]>0&&feas<MT>(nodeOfDepth,currNode)) {
   2.491 +            addPair(nodeOfDepth,currNode);
   2.492 +            break;
   2.493 +          }
   2.494 +        }
   2.495 +        edgeItOfDepth==INVALID?--_depth:++_depth;
   2.496 +      }
   2.497        return false;
   2.498      }
   2.499  
   2.500      //calc. the lookup table for cut the searchtree
   2.501 -    void setRNew1tRInOut1t()
   2.502 -    {
   2.503 +    void setRNew1tRInOut1t() {
   2.504        typename G1::template NodeMap<int> tmp(_g1,0);
   2.505 -      for(unsigned int i=0; i<order.size(); ++i)
   2.506 -        {
   2.507 -          tmp[order[i]]=-1;
   2.508 -          for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1)
   2.509 -            {
   2.510 -              const typename G1::Node currNode=_g1.oppositeNode(order[i],e1);
   2.511 -              if(tmp[currNode]>0)
   2.512 -                ++rInOut1t[order[i]];
   2.513 -              else if(tmp[currNode]==0)
   2.514 -                ++rNew1t[order[i]];
   2.515 -            }
   2.516 -          for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1)
   2.517 -            {
   2.518 -              const typename G1::Node currNode=_g1.oppositeNode(order[i],e1);
   2.519 -              if(tmp[currNode]!=-1)
   2.520 -                ++tmp[currNode];
   2.521 -            }
   2.522 +      for(unsigned int i=0; i<order.size(); ++i) {
   2.523 +        const typename G1::Node& orderI = order[i];
   2.524 +        tmp[orderI]=-1;
   2.525 +        for(typename G1::IncEdgeIt e1(_g1,orderI); e1!=INVALID; ++e1) {
   2.526 +          const typename G1::Node currNode=_g1.oppositeNode(orderI,e1);
   2.527 +          if(tmp[currNode]>0)
   2.528 +            ++rInOut1t[orderI];
   2.529 +          else if(tmp[currNode]==0)
   2.530 +            ++rNew1t[orderI];
   2.531          }
   2.532 +        for(typename G1::IncEdgeIt e1(_g1,orderI); e1!=INVALID; ++e1) {
   2.533 +          const typename G1::Node currNode=_g1.oppositeNode(orderI,e1);
   2.534 +          if(tmp[currNode]!=-1)
   2.535 +            ++tmp[currNode];
   2.536 +        }
   2.537 +      }
   2.538      }
   2.539    public:
   2.540      ///Constructor
   2.541 @@ -399,13 +346,12 @@
   2.542      ///\param g2 The graph \e g1 will be embedded into.
   2.543      ///\param m \ref concepts::ReadWriteMap "read-write" NodeMap
   2.544      ///storing the found mapping.
   2.545 -    ///\param neq A bool-valued binary functor determinining whether a node is
   2.546 +    ///\param neq A bool-valued binary functor determining whether a node is
   2.547      ///mappable to another. By default it is an always true operator.
   2.548 -    Vf2(const G1 &g1, const G2 &g2,M &m, const NEQ &neq = NEQ() ) :
   2.549 +    Vf2(const G1 &g1, const G2 &g2, M &m, const NEQ &neq = NEQ() ) :
   2.550        _nEq(neq), _conn(g2,0), _mapping(m), order(countNodes(g1)),
   2.551        currEdgeIts(countNodes(g1),INVALID), _g1(g1), _g2(g2), rNew1t(g1,0),
   2.552 -      rInOut1t(g1,0), _mapping_type(SUBGRAPH)
   2.553 -    {
   2.554 +      rInOut1t(g1,0), _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0) {
   2.555        _depth=0;
   2.556        setOrder();
   2.557        setRNew1tRInOut1t();
   2.558 @@ -413,48 +359,59 @@
   2.559          m[n]=INVALID;
   2.560      }
   2.561  
   2.562 +    ///Destructor
   2.563 +
   2.564 +    ///Destructor.
   2.565 +    ///
   2.566 +
   2.567 +    ~Vf2(){
   2.568 +      if(_deallocMappingAfterUse)
   2.569 +        delete &_mapping;
   2.570 +    }
   2.571 +
   2.572      ///Returns the current mapping type
   2.573  
   2.574      ///Returns the current mapping type
   2.575      ///
   2.576 -    Vf2MappingType mappingType() const { return _mapping_type; }
   2.577 +    MappingType mappingType() const {
   2.578 +      return _mapping_type;
   2.579 +    }
   2.580      ///Sets mapping type
   2.581  
   2.582      ///Sets mapping type.
   2.583      ///
   2.584      ///The mapping type is set to \ref SUBGRAPH by default.
   2.585      ///
   2.586 -    ///\sa See \ref Vf2MappingType for the possible values.
   2.587 -    void mappingType(Vf2MappingType m_type) { _mapping_type = m_type; }
   2.588 +    ///\sa See \ref MappingType for the possible values.
   2.589 +    void mappingType(MappingType m_type) {
   2.590 +      _mapping_type = m_type;
   2.591 +    }
   2.592  
   2.593      ///Finds a mapping
   2.594  
   2.595 -    ///It finds a mapping between from g1 into g2 according to the mapping
   2.596 -    ///type set by \ref mappingType(Vf2MappingType) "mappingType()".
   2.597 +    ///It finds a mapping from g1 into g2 according to the mapping
   2.598 +    ///type set by \ref mappingType(MappingType) "mappingType()".
   2.599      ///
   2.600      ///By subsequent calls, it returns all possible mappings one-by-one.
   2.601      ///
   2.602      ///\retval true if a mapping is found.
   2.603      ///\retval false if there is no (more) mapping.
   2.604 -    bool find()
   2.605 -    {
   2.606 -      switch(_mapping_type)
   2.607 -        {
   2.608 -        case SUBGRAPH:
   2.609 -          return extMatch<SUBGRAPH>();
   2.610 -        case INDUCED:
   2.611 -          return extMatch<INDUCED>();
   2.612 -        case ISOMORPH:
   2.613 -          return extMatch<ISOMORPH>();
   2.614 -        default:
   2.615 -          return false;
   2.616 -        }
   2.617 +    bool find() {
   2.618 +      switch(_mapping_type) {
   2.619 +      case SUBGRAPH:
   2.620 +        return extMatch<SUBGRAPH>();
   2.621 +      case INDUCED:
   2.622 +        return extMatch<INDUCED>();
   2.623 +      case ISOMORPH:
   2.624 +        return extMatch<ISOMORPH>();
   2.625 +      default:
   2.626 +        return false;
   2.627 +      }
   2.628      }
   2.629    };
   2.630  
   2.631    template<class G1, class G2>
   2.632 -  class Vf2WizardBase
   2.633 -  {
   2.634 +  class Vf2WizardBase {
   2.635    protected:
   2.636      typedef G1 Graph1;
   2.637      typedef G2 Graph2;
   2.638 @@ -462,23 +419,26 @@
   2.639      const G1 &_g1;
   2.640      const G2 &_g2;
   2.641  
   2.642 -    Vf2MappingType _mapping_type;
   2.643 +    MappingType _mapping_type;
   2.644  
   2.645      typedef typename G1::template NodeMap<typename G2::Node> Mapping;
   2.646      bool _local_mapping;
   2.647      void *_mapping;
   2.648 -    void createMapping()
   2.649 -    {
   2.650 +    void createMapping() {
   2.651        _mapping = new Mapping(_g1);
   2.652      }
   2.653  
   2.654 +    void *myVf2; //used in Vf2Wizard::find
   2.655 +
   2.656 +
   2.657      typedef bits::vf2::AlwaysEq NodeEq;
   2.658      NodeEq _node_eq;
   2.659  
   2.660      Vf2WizardBase(const G1 &g1,const G2 &g2)
   2.661 -      : _g1(g1), _g2(g2), _mapping_type(SUBGRAPH), _local_mapping(true) {}
   2.662 +      : _g1(g1), _g2(g2), _mapping_type(SUBGRAPH), _local_mapping(true) { }
   2.663    };
   2.664  
   2.665 +
   2.666    /// Auxiliary class for the function-type interface of %VF2 algorithm.
   2.667  
   2.668    /// This auxiliary class implements the named parameters of
   2.669 @@ -489,8 +449,7 @@
   2.670    /// \tparam TR The traits class that defines various types used by the
   2.671    /// algorithm.
   2.672    template<class TR>
   2.673 -  class Vf2Wizard : public TR
   2.674 -  {
   2.675 +  class Vf2Wizard : public TR {
   2.676      typedef TR Base;
   2.677      typedef typename TR::Graph1 Graph1;
   2.678      typedef typename TR::Graph2 Graph2;
   2.679 @@ -506,14 +465,18 @@
   2.680  
   2.681    public:
   2.682      ///Constructor
   2.683 -    Vf2Wizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {}
   2.684 +    Vf2Wizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {
   2.685 +    }
   2.686  
   2.687      ///Copy constructor
   2.688 -    Vf2Wizard(const Base &b) : Base(b) {}
   2.689 +    Vf2Wizard(const Base &b) : Base(b) { }
   2.690 +
   2.691 +    ///Copy constructor
   2.692 +    Vf2Wizard(const Vf2Wizard &b) : Base(b) {}
   2.693  
   2.694  
   2.695      template<class T>
   2.696 -    struct SetMappingBase : public Base {
   2.697 +    struct SetMappingBase : public Base{
   2.698        typedef T Mapping;
   2.699        SetMappingBase(const Base &b) : Base(b) {}
   2.700      };
   2.701 @@ -524,8 +487,7 @@
   2.702      ///\ref named-templ-param "Named parameter" function for setting
   2.703      ///the map that stores the found embedding.
   2.704      template<class T>
   2.705 -    Vf2Wizard< SetMappingBase<T> > mapping(const T &t)
   2.706 -    {
   2.707 +    Vf2Wizard< SetMappingBase<T> > mapping(const T &t) {
   2.708        Base::_mapping=reinterpret_cast<void*>(const_cast<T*>(&t));
   2.709        Base::_local_mapping = false;
   2.710        return Vf2Wizard<SetMappingBase<T> >(*this);
   2.711 @@ -536,7 +498,8 @@
   2.712        typedef NE NodeEq;
   2.713        NodeEq _node_eq;
   2.714        SetNodeEqBase(const Base &b, const NE &node_eq)
   2.715 -        : Base(b), _node_eq(node_eq) {}
   2.716 +        : Base(b), _node_eq(node_eq){
   2.717 +      }
   2.718      };
   2.719  
   2.720      ///\brief \ref named-templ-param "Named parameter" for setting
   2.721 @@ -549,8 +512,7 @@
   2.722      ///whether a node is mappable to another. By default it is an
   2.723      ///always true operator.
   2.724      template<class T>
   2.725 -    Vf2Wizard< SetNodeEqBase<T> > nodeEq(const T &node_eq)
   2.726 -    {
   2.727 +    Vf2Wizard< SetNodeEqBase<T> > nodeEq(const T &node_eq) {
   2.728        return Vf2Wizard<SetNodeEqBase<T> >(SetNodeEqBase<T>(*this,node_eq));
   2.729      }
   2.730  
   2.731 @@ -560,16 +522,15 @@
   2.732      ///\ref named-templ-param "Named parameter" function for setting
   2.733      ///the node labels defining equivalence relation between them.
   2.734      ///
   2.735 -    ///\param m1 It is arbitrary \ref concepts::ReadMap "readable node map"
   2.736 +    ///\param m1 An arbitrary \ref concepts::ReadMap "readable node map"
   2.737      ///of g1.
   2.738 -    ///\param m2 It is arbitrary \ref concepts::ReadMap "readable node map"
   2.739 +    ///\param m2 An arbitrary \ref concepts::ReadMap "readable node map"
   2.740      ///of g2.
   2.741      ///
   2.742      ///The value type of these maps must be equal comparable.
   2.743      template<class M1, class M2>
   2.744      Vf2Wizard< SetNodeEqBase<bits::vf2::MapEq<M1,M2> > >
   2.745 -    nodeLabels(const M1 &m1,const M2 &m2)
   2.746 -    {
   2.747 +    nodeLabels(const M1 &m1,const M2 &m2){
   2.748        return nodeEq(bits::vf2::MapEq<M1,M2>(m1,m2));
   2.749      }
   2.750  
   2.751 @@ -581,9 +542,8 @@
   2.752      ///
   2.753      ///The mapping type is set to \ref SUBGRAPH by default.
   2.754      ///
   2.755 -    ///\sa See \ref Vf2MappingType for the possible values.
   2.756 -    Vf2Wizard<Base> &mappingType(Vf2MappingType m_type)
   2.757 -    {
   2.758 +    ///\sa See \ref MappingType for the possible values.
   2.759 +    Vf2Wizard<Base> &mappingType(MappingType m_type) {
   2.760        _mapping_type = m_type;
   2.761        return *this;
   2.762      }
   2.763 @@ -593,8 +553,7 @@
   2.764      ///
   2.765      ///\ref named-templ-param "Named parameter" for setting
   2.766      ///the mapping type to \ref INDUCED.
   2.767 -    Vf2Wizard<Base> &induced()
   2.768 -    {
   2.769 +    Vf2Wizard<Base> &induced() {
   2.770        _mapping_type = INDUCED;
   2.771        return *this;
   2.772      }
   2.773 @@ -604,20 +563,19 @@
   2.774      ///
   2.775      ///\ref named-templ-param "Named parameter" for setting
   2.776      ///the mapping type to \ref ISOMORPH.
   2.777 -    Vf2Wizard<Base> &iso()
   2.778 -    {
   2.779 +    Vf2Wizard<Base> &iso() {
   2.780        _mapping_type = ISOMORPH;
   2.781        return *this;
   2.782      }
   2.783  
   2.784 +
   2.785      ///Runs VF2 algorithm.
   2.786  
   2.787      ///This method runs VF2 algorithm.
   2.788      ///
   2.789      ///\retval true if a mapping is found.
   2.790 -    ///\retval false if there is no (more) mapping.
   2.791 -    bool run()
   2.792 -    {
   2.793 +    ///\retval false if there is no mapping.
   2.794 +    bool run(){
   2.795        if(Base::_local_mapping)
   2.796          Base::createMapping();
   2.797  
   2.798 @@ -633,6 +591,46 @@
   2.799  
   2.800        return ret;
   2.801      }
   2.802 +
   2.803 +    ///Get a pointer to the generated Vf2 object.
   2.804 +
   2.805 +    ///Gives a pointer to the generated Vf2 object.
   2.806 +    ///
   2.807 +    ///\return Pointer to the generated Vf2 object.
   2.808 +    ///\warning Don't forget to delete the referred Vf2 object after use.
   2.809 +    Vf2<Graph1, Graph2, Mapping, NodeEq >* getPtrToVf2Object() {
   2.810 +      if(Base::_local_mapping)
   2.811 +        Base::createMapping();
   2.812 +      Vf2<Graph1, Graph2, Mapping, NodeEq >* ptr =
   2.813 +        new Vf2<Graph1, Graph2, Mapping, NodeEq>
   2.814 +        (_g1, _g2, *reinterpret_cast<Mapping*>(_mapping), _node_eq);
   2.815 +      ptr->mappingType(_mapping_type);
   2.816 +      if(Base::_local_mapping)
   2.817 +        ptr->_deallocMappingAfterUse = true;
   2.818 +      return ptr;
   2.819 +    }
   2.820 +
   2.821 +    ///Counts the number of mappings.
   2.822 +
   2.823 +    ///This method counts the number of mappings.
   2.824 +    ///
   2.825 +    /// \return The number of mappings.
   2.826 +    int count() {
   2.827 +      if(Base::_local_mapping)
   2.828 +        Base::createMapping();
   2.829 +
   2.830 +      Vf2<Graph1, Graph2, Mapping, NodeEq>
   2.831 +        alg(_g1, _g2, *reinterpret_cast<Mapping*>(_mapping), _node_eq);
   2.832 +      if(Base::_local_mapping)
   2.833 +        alg._deallocMappingAfterUse = true;
   2.834 +      alg.mappingType(_mapping_type);
   2.835 +
   2.836 +      int ret = 0;
   2.837 +      while(alg.find())
   2.838 +        ++ret;
   2.839 +
   2.840 +      return ret;
   2.841 +    }
   2.842    };
   2.843  
   2.844    ///Function-type interface for VF2 algorithm.
   2.845 @@ -644,20 +642,32 @@
   2.846    ///declared as the members of class \ref Vf2Wizard.
   2.847    ///The following examples show how to use these parameters.
   2.848    ///\code
   2.849 -  ///  // Find an embedding of graph g into graph h
   2.850 +  ///  // Find an embedding of graph g1 into graph g2
   2.851    ///  ListGraph::NodeMap<ListGraph::Node> m(g);
   2.852 -  ///  vf2(g,h).mapping(m).run();
   2.853 +  ///  vf2(g1,g2).mapping(m).run();
   2.854    ///
   2.855 -  ///  // Check whether graphs g and h are isomorphic
   2.856 -  ///  bool is_iso = vf2(g,h).iso().run();
   2.857 +  ///  // Check whether graphs g1 and g2 are isomorphic
   2.858 +  ///  bool is_iso = vf2(g1,g2).iso().run();
   2.859 +  ///
   2.860 +  ///  // Count the number of isomorphisms
   2.861 +  ///  int num_isos = vf2(g1,g2).iso().count();
   2.862 +  ///
   2.863 +  ///  // Iterate through all the induced subgraph mappings of graph g1 into g2
   2.864 +  ///  auto* myVf2 = vf2(g1,g2).mapping(m).nodeLabels(c1,c2)
   2.865 +  ///  .induced().getPtrToVf2Object();
   2.866 +  ///  while(myVf2->find()){
   2.867 +  ///    //process the current mapping m
   2.868 +  ///  }
   2.869 +  ///  delete myVf22;
   2.870    ///\endcode
   2.871 -  ///\warning Don't forget to put the \ref Vf2Wizard::run() "run()"
   2.872 +  ///\warning Don't forget to put the \ref Vf2Wizard::run() "run()",
   2.873 +  ///\ref Vf2Wizard::count() "count()" or
   2.874 +  ///the \ref Vf2Wizard::getPtrToVf2Object() "getPtrToVf2Object()"
   2.875    ///to the end of the expression.
   2.876    ///\sa Vf2Wizard
   2.877    ///\sa Vf2
   2.878    template<class G1, class G2>
   2.879 -  Vf2Wizard<Vf2WizardBase<G1,G2> > vf2(const G1 &g1, const G2 &g2)
   2.880 -  {
   2.881 +  Vf2Wizard<Vf2WizardBase<G1,G2> > vf2(const G1 &g1, const G2 &g2) {
   2.882      return Vf2Wizard<Vf2WizardBase<G1,G2> >(g1,g2);
   2.883    }
   2.884  
     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/lemon/vf2pp.h	Tue Sep 19 14:08:20 2017 +0200
     3.3 @@ -0,0 +1,902 @@
     3.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     3.5 + *
     3.6 + * This file is a part of LEMON, a generic C++ optimization library.
     3.7 + *
     3.8 + * Copyright (C) 2015-2017
     3.9 + * EMAXA Kutato-fejleszto Kft. (EMAXA Research Ltd.)
    3.10 + *
    3.11 + * Permission to use, modify and distribute this software is granted
    3.12 + * provided that this copyright notice appears in all copies. For
    3.13 + * precise terms see the accompanying LICENSE file.
    3.14 + *
    3.15 + * This software is provided "AS IS" with no warranty of any kind,
    3.16 + * express or implied, and with no claim as to its suitability for any
    3.17 + * purpose.
    3.18 + *
    3.19 + */
    3.20 +
    3.21 +#ifndef LEMON_VF2PP_H
    3.22 +#define LEMON_VF2PP_H
    3.23 +
    3.24 +///\ingroup graph_properties
    3.25 +///\file
    3.26 +///\brief VF2 Plus Plus algorithm.
    3.27 +
    3.28 +#include <lemon/core.h>
    3.29 +#include <lemon/concepts/graph.h>
    3.30 +#include <lemon/dfs.h>
    3.31 +#include <lemon/bfs.h>
    3.32 +#include <lemon/bits/vf2_internals.h>
    3.33 +
    3.34 +
    3.35 +#include <vector>
    3.36 +#include <algorithm>
    3.37 +#include <utility>
    3.38 +
    3.39 +
    3.40 +namespace lemon {
    3.41 +  namespace bits {
    3.42 +    namespace vf2pp {
    3.43 +
    3.44 +      template <class G>
    3.45 +      class DfsLeaveOrder : public DfsVisitor<G> {
    3.46 +        int i;
    3.47 +        const G &_g;
    3.48 +        std::vector<typename G::Node> &_order;
    3.49 +      public:
    3.50 +        DfsLeaveOrder(const G &g, std::vector<typename G::Node> &order)
    3.51 +          : i(countNodes(g)), _g(g), _order(order) {
    3.52 +        }
    3.53 +        void leave(const typename G::Node &node) {
    3.54 +          _order[--i]=node;
    3.55 +        }
    3.56 +      };
    3.57 +
    3.58 +      template <class G>
    3.59 +      class BfsLeaveOrder : public BfsVisitor<G> {
    3.60 +        int i;
    3.61 +        const G &_g;
    3.62 +        std::vector<typename G::Node> &_order;
    3.63 +      public:
    3.64 +        BfsLeaveOrder(const G &g, std::vector<typename G::Node> &order) { }
    3.65 +        void process(const typename G::Node &node) {
    3.66 +          _order[i++]=node;
    3.67 +        }
    3.68 +      };
    3.69 +    }
    3.70 +  }
    3.71 +
    3.72 +
    3.73 +  ///%VF2 Plus Plus algorithm class.
    3.74 +
    3.75 +  ///\ingroup graph_isomorphism This class provides an efficient
    3.76 +  ///implementation of the %VF2 Plus Plus algorithm
    3.77 +  ///for variants of the (Sub)graph Isomorphism problem.
    3.78 +  ///
    3.79 +  ///There is also a \ref vf2pp() "function-type interface" called
    3.80 +  ///\ref vf2pp() for the %VF2 Plus Plus algorithm, which is probably
    3.81 +  ///more convenient in most use-cases.
    3.82 +  ///
    3.83 +  ///\tparam G1 The type of the graph to be embedded.
    3.84 +  ///The default type is \ref ListDigraph.
    3.85 +  ///\tparam G2 The type of the graph g1 will be embedded into.
    3.86 +  ///The default type is \ref ListDigraph.
    3.87 +  ///\tparam M The type of the NodeMap storing the mapping.
    3.88 +  ///By default, it is G1::NodeMap<G2::Node>
    3.89 +  ///\tparam M1 The type of the NodeMap storing the integer node labels of G1.
    3.90 +  ///The labels must be the numbers {0,1,2,..,K-1}, where K is the number of
    3.91 +  ///different labels. By default, it is G1::NodeMap<int>.
    3.92 +  ///\tparam M2 The type of the NodeMap storing the integer node labels of G2.
    3.93 +  ///The labels must be the numbers {0,1,2,..,K-1}, where K is the number of
    3.94 +  ///different labels. By default, it is G2::NodeMap<int>.
    3.95 +  ///
    3.96 +  ///\sa vf2pp()
    3.97 +#ifdef DOXYGEN
    3.98 +  template<class G1, class G2, class M, class M1, class M2 >
    3.99 +#else
   3.100 +  template<class G1=ListDigraph,
   3.101 +           class G2=ListDigraph,
   3.102 +           class M = typename G1::template NodeMap<G2::Node>,//the mapping
   3.103 +           //labels of G1,the labels are the numbers {0,1,2,..,K-1},
   3.104 +           //where K is the number of different labels
   3.105 +           class M1 = typename G1::template NodeMap<int>,
   3.106 +           //labels of G2, ...
   3.107 +           class M2 = typename G2::template NodeMap<int> >
   3.108 +#endif
   3.109 +  class Vf2pp {
   3.110 +    //Current depth in the search tree.
   3.111 +    int _depth;
   3.112 +
   3.113 +    //_conn[v2] = number of covered neighbours of v2
   3.114 +    typename G2::template NodeMap<int> _conn;
   3.115 +
   3.116 +    //The current mapping. _mapping[v1]=v2 iff v1 has been mapped to v2,
   3.117 +    //where v1 is a node of G1 and v2 is a node of G2
   3.118 +    M &_mapping;
   3.119 +
   3.120 +    //order[i] is a node of g1, for which a pair is searched if depth=i
   3.121 +    std::vector<typename G1::Node> order;
   3.122 +
   3.123 +    //currEdgeIts[i] is the last used edge iterator in the ith
   3.124 +    //depth to find a pair for node order[i]
   3.125 +    std::vector<typename G2::IncEdgeIt> currEdgeIts;
   3.126 +
   3.127 +    //The small graph.
   3.128 +    const G1 &_g1;
   3.129 +
   3.130 +    //The large graph.
   3.131 +    const G2 &_g2;
   3.132 +
   3.133 +    //rNewLabels1[v] is a pair of form
   3.134 +    //(label; num. of uncov. nodes with such label and no covered neighbours)
   3.135 +    typename G1::template NodeMap<std::vector<std::pair<int,int> > >
   3.136 +    rNewLabels1;
   3.137 +
   3.138 +    //rInOutLabels1[v] is the number of covered neighbours of v for each label
   3.139 +    //in form (label,number of such labels)
   3.140 +    typename G1::template NodeMap<std::vector<std::pair<int,int> > >
   3.141 +    rInOutLabels1;
   3.142 +
   3.143 +    //_intLabels1[v]==i means that vertex v has the i label in
   3.144 +    //_g1 (i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
   3.145 +    M1 &_intLabels1;
   3.146 +
   3.147 +    //_intLabels2[v]==i means that vertex v has the i label in
   3.148 +    //_g2 (i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
   3.149 +    M2 &_intLabels2;
   3.150 +
   3.151 +    //largest label
   3.152 +    const int maxLabel;
   3.153 +
   3.154 +    //lookup tables for manipulating with label class cardinalities
   3.155 +    //after use they have to be reset to 0..0
   3.156 +    std::vector<int> labelTmp1,labelTmp2;
   3.157 +
   3.158 +    MappingType _mapping_type;
   3.159 +
   3.160 +    //indicates whether the mapping or the labels must be deleted in the ctor
   3.161 +    bool _deallocMappingAfterUse,_deallocLabelsAfterUse;
   3.162 +
   3.163 +
   3.164 +    //improved cutting function
   3.165 +    template<MappingType MT>
   3.166 +    bool cutByLabels(const typename G1::Node n1,const typename G2::Node n2) {
   3.167 +      for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
   3.168 +        const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
   3.169 +        if(_conn[currNode]>0)
   3.170 +          --labelTmp1[_intLabels2[currNode]];
   3.171 +        else if(MT!=SUBGRAPH&&_conn[currNode]==0)
   3.172 +          --labelTmp2[_intLabels2[currNode]];
   3.173 +      }
   3.174 +
   3.175 +      bool ret=1;
   3.176 +      if(ret) {
   3.177 +        for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i)
   3.178 +          labelTmp1[rInOutLabels1[n1][i].first]+=rInOutLabels1[n1][i].second;
   3.179 +
   3.180 +        if(MT!=SUBGRAPH)
   3.181 +          for(unsigned int i = 0; i < rNewLabels1[n1].size(); ++i)
   3.182 +            labelTmp2[rNewLabels1[n1][i].first]+=rNewLabels1[n1][i].second;
   3.183 +
   3.184 +        switch(MT) {
   3.185 +        case INDUCED:
   3.186 +          for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i)
   3.187 +            if(labelTmp1[rInOutLabels1[n1][i].first]>0) {
   3.188 +              ret=0;
   3.189 +              break;
   3.190 +            }
   3.191 +          if(ret)
   3.192 +            for(unsigned int i = 0; i < rNewLabels1[n1].size(); ++i)
   3.193 +              if(labelTmp2[rNewLabels1[n1][i].first]>0) {
   3.194 +                ret=0;
   3.195 +                break;
   3.196 +              }
   3.197 +          break;
   3.198 +        case SUBGRAPH:
   3.199 +          for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i)
   3.200 +            if(labelTmp1[rInOutLabels1[n1][i].first]>0) {
   3.201 +              ret=0;
   3.202 +              break;
   3.203 +            }
   3.204 +          break;
   3.205 +        case ISOMORPH:
   3.206 +          for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i)
   3.207 +            if(labelTmp1[rInOutLabels1[n1][i].first]!=0) {
   3.208 +              ret=0;
   3.209 +              break;
   3.210 +            }
   3.211 +          if(ret)
   3.212 +            for(unsigned int i = 0; i < rNewLabels1[n1].size(); ++i)
   3.213 +              if(labelTmp2[rNewLabels1[n1][i].first]!=0) {
   3.214 +                ret=0;
   3.215 +                break;
   3.216 +              }
   3.217 +          break;
   3.218 +        default:
   3.219 +          return false;
   3.220 +        }
   3.221 +        for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i)
   3.222 +          labelTmp1[rInOutLabels1[n1][i].first]=0;
   3.223 +
   3.224 +        if(MT!=SUBGRAPH)
   3.225 +          for(unsigned int i = 0; i < rNewLabels1[n1].size(); ++i)
   3.226 +            labelTmp2[rNewLabels1[n1][i].first]=0;
   3.227 +      }
   3.228 +
   3.229 +      for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
   3.230 +        const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
   3.231 +        labelTmp1[_intLabels2[currNode]]=0;
   3.232 +        if(MT!=SUBGRAPH&&_conn[currNode]==0)
   3.233 +          labelTmp2[_intLabels2[currNode]]=0;
   3.234 +      }
   3.235 +
   3.236 +      return ret;
   3.237 +    }
   3.238 +
   3.239 +
   3.240 +    //try to exclude the matching of n1 and n2
   3.241 +    template<MappingType MT>
   3.242 +    bool feas(const typename G1::Node n1,const typename G2::Node n2) {
   3.243 +      if(_intLabels1[n1]!=_intLabels2[n2])
   3.244 +        return 0;
   3.245 +
   3.246 +      for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
   3.247 +        const typename G1::Node& currNode=_g1.oppositeNode(n1,e1);
   3.248 +        if(_mapping[currNode]!=INVALID)
   3.249 +          --_conn[_mapping[currNode]];
   3.250 +      }
   3.251 +
   3.252 +      bool isIso=1;
   3.253 +      for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
   3.254 +        int& connCurrNode = _conn[_g2.oppositeNode(n2,e2)];
   3.255 +        if(connCurrNode<-1)
   3.256 +          ++connCurrNode;
   3.257 +        else if(MT!=SUBGRAPH&&connCurrNode==-1) {
   3.258 +          isIso=0;
   3.259 +          break;
   3.260 +        }
   3.261 +      }
   3.262 +
   3.263 +      if(isIso)
   3.264 +        for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
   3.265 +          const typename G2::Node& currNodePair =
   3.266 +            _mapping[_g1.oppositeNode(n1,e1)];
   3.267 +          int& connCurrNodePair=_conn[currNodePair];
   3.268 +          if(currNodePair!=INVALID&&connCurrNodePair!=-1) {
   3.269 +            switch(MT){
   3.270 +            case INDUCED:
   3.271 +            case ISOMORPH:
   3.272 +              isIso=0;
   3.273 +              break;
   3.274 +            case SUBGRAPH:
   3.275 +              if(connCurrNodePair<-1)
   3.276 +                isIso=0;
   3.277 +              break;
   3.278 +            }
   3.279 +            connCurrNodePair=-1;
   3.280 +          }
   3.281 +        }
   3.282 +      else
   3.283 +        for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
   3.284 +          const typename G2::Node currNode=_mapping[_g1.oppositeNode(n1,e1)];
   3.285 +          if(currNode!=INVALID/*&&_conn[currNode]!=-1*/)
   3.286 +            _conn[currNode]=-1;
   3.287 +        }
   3.288 +
   3.289 +      return isIso&&cutByLabels<MT>(n1,n2);
   3.290 +    }
   3.291 +
   3.292 +
   3.293 +    //matches n1 and n2
   3.294 +    void addPair(const typename G1::Node n1,const typename G2::Node n2) {
   3.295 +      _conn[n2]=-1;
   3.296 +      _mapping.set(n1,n2);
   3.297 +      for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
   3.298 +        int& currConn = _conn[_g2.oppositeNode(n2,e2)];
   3.299 +        if(currConn!=-1)
   3.300 +          ++currConn;
   3.301 +      }
   3.302 +    }
   3.303 +
   3.304 +
   3.305 +    //dematches n1 and n2
   3.306 +    void subPair(const typename G1::Node n1,const typename G2::Node n2) {
   3.307 +      _conn[n2]=0;
   3.308 +      _mapping.set(n1,INVALID);
   3.309 +      for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2){
   3.310 +        int& currConn = _conn[_g2.oppositeNode(n2,e2)];
   3.311 +        if(currConn>0)
   3.312 +          --currConn;
   3.313 +        else if(currConn==-1)
   3.314 +          ++_conn[n2];
   3.315 +      }
   3.316 +    }
   3.317 +
   3.318 +
   3.319 +    void processBFSLevel(typename G1::Node source,unsigned int& orderIndex,
   3.320 +                         typename G1::template NodeMap<int>& dm1,
   3.321 +                         typename G1::template NodeMap<bool>& added) {
   3.322 +      order[orderIndex]=source;
   3.323 +      added[source]=1;
   3.324 +
   3.325 +      unsigned int endPosOfLevel=orderIndex,
   3.326 +        startPosOfLevel=orderIndex,
   3.327 +        lastAdded=orderIndex;
   3.328 +
   3.329 +      typename G1::template NodeMap<int> currConn(_g1,0);
   3.330 +
   3.331 +      while(orderIndex<=lastAdded){
   3.332 +        typename G1::Node currNode = order[orderIndex];
   3.333 +        for(typename G1::IncEdgeIt e(_g1,currNode); e!=INVALID; ++e) {
   3.334 +          typename G1::Node n = _g1.oppositeNode(currNode,e);
   3.335 +          if(!added[n]) {
   3.336 +            order[++lastAdded]=n;
   3.337 +            added[n]=1;
   3.338 +          }
   3.339 +        }
   3.340 +        if(orderIndex>endPosOfLevel){
   3.341 +          for(unsigned int j = startPosOfLevel; j <= endPosOfLevel; ++j) {
   3.342 +            int minInd=j;
   3.343 +            for(unsigned int i = j+1; i <= endPosOfLevel; ++i)
   3.344 +              if(currConn[order[i]]>currConn[order[minInd]]||
   3.345 +                 (currConn[order[i]]==currConn[order[minInd]]&&
   3.346 +                  (dm1[order[i]]>dm1[order[minInd]]||
   3.347 +                   (dm1[order[i]]==dm1[order[minInd]]&&
   3.348 +                    labelTmp1[_intLabels1[order[minInd]]]>
   3.349 +                    labelTmp1[_intLabels1[order[i]]]))))
   3.350 +                minInd=i;
   3.351 +
   3.352 +            --labelTmp1[_intLabels1[order[minInd]]];
   3.353 +            for(typename G1::IncEdgeIt e(_g1,order[minInd]); e!=INVALID; ++e)
   3.354 +              ++currConn[_g1.oppositeNode(order[minInd],e)];
   3.355 +            std::swap(order[j],order[minInd]);
   3.356 +          }
   3.357 +          startPosOfLevel=endPosOfLevel+1;
   3.358 +          endPosOfLevel=lastAdded;
   3.359 +        }
   3.360 +        ++orderIndex;
   3.361 +      }
   3.362 +    }
   3.363 +
   3.364 +
   3.365 +    //we will find pairs for the nodes of g1 in this order
   3.366 +    void setOrder(){
   3.367 +      for(typename G2::NodeIt n2(_g2); n2!=INVALID; ++n2)
   3.368 +        ++labelTmp1[_intLabels2[n2]];
   3.369 +
   3.370 +      //       OutDegMap<G1> dm1(_g1);
   3.371 +      typename G1::template NodeMap<int> dm1(_g1,0);
   3.372 +      for(typename G1::EdgeIt e(_g1); e!=INVALID; ++e) {
   3.373 +        ++dm1[_g1.u(e)];
   3.374 +        ++dm1[_g1.v(e)];
   3.375 +      }
   3.376 +
   3.377 +      typename G1::template NodeMap<bool> added(_g1,0);
   3.378 +      unsigned int orderIndex=0;
   3.379 +
   3.380 +      for(typename G1::NodeIt n(_g1); n!=INVALID;) {
   3.381 +        if(!added[n]){
   3.382 +          typename G1::Node minNode = n;
   3.383 +          for(typename G1::NodeIt n1(_g1,minNode); n1!=INVALID; ++n1)
   3.384 +            if(!added[n1] &&
   3.385 +               (labelTmp1[_intLabels1[minNode]]>
   3.386 +                labelTmp1[_intLabels1[n1]]||(dm1[minNode]<dm1[n1]&&
   3.387 +                                             labelTmp1[_intLabels1[minNode]]==
   3.388 +                                             labelTmp1[_intLabels1[n1]])))
   3.389 +              minNode=n1;
   3.390 +          processBFSLevel(minNode,orderIndex,dm1,added);
   3.391 +        }
   3.392 +        else
   3.393 +          ++n;
   3.394 +      }
   3.395 +      for(unsigned int i = 0; i < labelTmp1.size(); ++i)
   3.396 +        labelTmp1[i]=0;
   3.397 +    }
   3.398 +
   3.399 +
   3.400 +    template<MappingType MT>
   3.401 +    bool extMatch(){
   3.402 +      while(_depth>=0) {
   3.403 +        //there is no node in g1, which has not pair in g2.
   3.404 +        if(_depth==static_cast<int>(order.size())) {
   3.405 +          --_depth;
   3.406 +          return true;
   3.407 +        }
   3.408 +        typename G1::Node& nodeOfDepth = order[_depth];
   3.409 +        const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth];
   3.410 +        typename G2::IncEdgeIt &edgeItOfDepth = currEdgeIts[_depth];
   3.411 +        //the node of g2, which neighbours are the candidates for
   3.412 +        //the pair of order[_depth]
   3.413 +        typename G2::Node currPNode;
   3.414 +        if(edgeItOfDepth==INVALID){
   3.415 +          typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth);
   3.416 +          //if _mapping[order[_depth]]!=INVALID, we dont need
   3.417 +          //fstMatchedE
   3.418 +          if(pairOfNodeOfDepth==INVALID)
   3.419 +            for(; fstMatchedE!=INVALID &&
   3.420 +                  _mapping[_g1.oppositeNode(nodeOfDepth,
   3.421 +                                            fstMatchedE)]==INVALID;
   3.422 +                ++fstMatchedE); //find fstMatchedE, it could be preprocessed
   3.423 +          if(fstMatchedE==INVALID||pairOfNodeOfDepth!=INVALID) {
   3.424 +            //We found no covered neighbours, this means
   3.425 +            //the graph is not connected(or _depth==0).  Each
   3.426 +            //uncovered(and there are some other properties due
   3.427 +            //to the spec. problem types) node of g2 is
   3.428 +            //candidate.  We can read the iterator of the last
   3.429 +            //tried node from the match if it is not the first
   3.430 +            //try(match[nodeOfDepth]!=INVALID)
   3.431 +            typename G2::NodeIt n2(_g2);
   3.432 +            //if it's not the first try
   3.433 +            if(pairOfNodeOfDepth!=INVALID) {
   3.434 +              n2=++typename G2::NodeIt(_g2,pairOfNodeOfDepth);
   3.435 +              subPair(nodeOfDepth,pairOfNodeOfDepth);
   3.436 +            }
   3.437 +            for(; n2!=INVALID; ++n2)
   3.438 +              if(MT!=SUBGRAPH) {
   3.439 +                if(_conn[n2]==0&&feas<MT>(nodeOfDepth,n2))
   3.440 +                  break;
   3.441 +              }
   3.442 +              else if(_conn[n2]>=0&&feas<MT>(nodeOfDepth,n2))
   3.443 +                break;
   3.444 +            // n2 is the next candidate
   3.445 +            if(n2!=INVALID) {
   3.446 +              addPair(nodeOfDepth,n2);
   3.447 +              ++_depth;
   3.448 +            }
   3.449 +            else // there are no more candidates
   3.450 +              --_depth;
   3.451 +            continue;
   3.452 +          }
   3.453 +          else{
   3.454 +            currPNode=_mapping[_g1.oppositeNode(nodeOfDepth,
   3.455 +                                                fstMatchedE)];
   3.456 +            edgeItOfDepth=typename G2::IncEdgeIt(_g2,currPNode);
   3.457 +          }
   3.458 +        }
   3.459 +        else{
   3.460 +          currPNode=_g2.oppositeNode(pairOfNodeOfDepth,
   3.461 +                                     edgeItOfDepth);
   3.462 +          subPair(nodeOfDepth,pairOfNodeOfDepth);
   3.463 +          ++edgeItOfDepth;
   3.464 +        }
   3.465 +        for(; edgeItOfDepth!=INVALID; ++edgeItOfDepth) {
   3.466 +          const typename G2::Node currNode =
   3.467 +            _g2.oppositeNode(currPNode, edgeItOfDepth);
   3.468 +          if(_conn[currNode]>0&&feas<MT>(nodeOfDepth,currNode)) {
   3.469 +            addPair(nodeOfDepth,currNode);
   3.470 +            break;
   3.471 +          }
   3.472 +        }
   3.473 +        edgeItOfDepth==INVALID?--_depth:++_depth;
   3.474 +      }
   3.475 +      return false;
   3.476 +    }
   3.477 +
   3.478 +    //calc. the lookup table for cutting the searchtree
   3.479 +    void setRNew1tRInOut1t(){
   3.480 +      typename G1::template NodeMap<int> tmp(_g1,0);
   3.481 +      for(unsigned int i=0; i<order.size(); ++i) {
   3.482 +        tmp[order[i]]=-1;
   3.483 +        for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1) {
   3.484 +          const typename G1::Node currNode=_g1.oppositeNode(order[i],e1);
   3.485 +          if(tmp[currNode]>0)
   3.486 +            ++labelTmp1[_intLabels1[currNode]];
   3.487 +          else if(tmp[currNode]==0)
   3.488 +            ++labelTmp2[_intLabels1[currNode]];
   3.489 +        }
   3.490 +        //labelTmp1[i]=number of neightbours with label i in set rInOut
   3.491 +        //labelTmp2[i]=number of neightbours with label i in set rNew
   3.492 +        for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1) {
   3.493 +          const int& currIntLabel = _intLabels1[_g1.oppositeNode(order[i],e1)];
   3.494 +          if(labelTmp1[currIntLabel]>0) {
   3.495 +            rInOutLabels1[order[i]]
   3.496 +              .push_back(std::make_pair(currIntLabel,
   3.497 +                                        labelTmp1[currIntLabel]));
   3.498 +            labelTmp1[currIntLabel]=0;
   3.499 +          }
   3.500 +          else if(labelTmp2[currIntLabel]>0) {
   3.501 +            rNewLabels1[order[i]].
   3.502 +              push_back(std::make_pair(currIntLabel,labelTmp2[currIntLabel]));
   3.503 +            labelTmp2[currIntLabel]=0;
   3.504 +          }
   3.505 +        }
   3.506 +
   3.507 +        for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1) {
   3.508 +          int& tmpCurrNode=tmp[_g1.oppositeNode(order[i],e1)];
   3.509 +          if(tmpCurrNode!=-1)
   3.510 +            ++tmpCurrNode;
   3.511 +        }
   3.512 +      }
   3.513 +    }
   3.514 +
   3.515 +    int getMaxLabel() const{
   3.516 +      int m=-1;
   3.517 +      for(typename G1::NodeIt n1(_g1); n1!=INVALID; ++n1) {
   3.518 +        const int& currIntLabel = _intLabels1[n1];
   3.519 +        if(currIntLabel>m)
   3.520 +          m=currIntLabel;
   3.521 +      }
   3.522 +      for(typename G2::NodeIt n2(_g2); n2!=INVALID; ++n2) {
   3.523 +        const int& currIntLabel = _intLabels2[n2];
   3.524 +        if(currIntLabel>m)
   3.525 +          m=currIntLabel;
   3.526 +      }
   3.527 +      return m;
   3.528 +    }
   3.529 +
   3.530 +  public:
   3.531 +    ///Constructor
   3.532 +
   3.533 +    ///Constructor.
   3.534 +    ///\param g1 The graph to be embedded.
   3.535 +    ///\param g2 The graph \e g1 will be embedded into.
   3.536 +    ///\param m The type of the NodeMap storing the mapping.
   3.537 +    ///By default, it is G1::NodeMap<G2::Node>
   3.538 +    ///\param intLabel1 The NodeMap storing the integer node labels of G1.
   3.539 +    ///The labels must be the numbers {0,1,2,..,K-1}, where K is the number of
   3.540 +    ///different labels.
   3.541 +    ///\param intLabel1 The NodeMap storing the integer node labels of G2.
   3.542 +    ///The labels must be the numbers {0,1,2,..,K-1}, where K is the number of
   3.543 +    ///different labels.
   3.544 +    Vf2pp(const G1 &g1, const G2 &g2,M &m, M1 &intLabels1, M2 &intLabels2) :
   3.545 +      _depth(0), _conn(g2,0), _mapping(m), order(countNodes(g1),INVALID),
   3.546 +      currEdgeIts(countNodes(g1),INVALID), _g1(g1), _g2(g2), rNewLabels1(_g1),
   3.547 +      rInOutLabels1(_g1), _intLabels1(intLabels1) ,_intLabels2(intLabels2),
   3.548 +      maxLabel(getMaxLabel()), labelTmp1(maxLabel+1),labelTmp2(maxLabel+1),
   3.549 +      _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0),
   3.550 +      _deallocLabelsAfterUse(0)
   3.551 +    {
   3.552 +      setOrder();
   3.553 +      setRNew1tRInOut1t();
   3.554 +
   3.555 +      //reset mapping
   3.556 +      for(typename G1::NodeIt n(g1);n!=INVALID;++n)
   3.557 +        m[n]=INVALID;
   3.558 +    }
   3.559 +
   3.560 +    ///Destructor
   3.561 +
   3.562 +    ///Destructor.
   3.563 +    ///
   3.564 +    ~Vf2pp()
   3.565 +    {
   3.566 +      if(_deallocMappingAfterUse)
   3.567 +        delete &_mapping;
   3.568 +      if(_deallocLabelsAfterUse) {
   3.569 +        delete &_intLabels1;
   3.570 +        delete &_intLabels2;
   3.571 +      }
   3.572 +    }
   3.573 +
   3.574 +    ///Returns the current mapping type.
   3.575 +
   3.576 +    ///Returns the current mapping type.
   3.577 +    ///
   3.578 +    MappingType mappingType() const
   3.579 +    {
   3.580 +      return _mapping_type;
   3.581 +    }
   3.582 +
   3.583 +    ///Sets the mapping type
   3.584 +
   3.585 +    ///Sets the mapping type.
   3.586 +    ///
   3.587 +    ///The mapping type is set to \ref SUBGRAPH by default.
   3.588 +    ///
   3.589 +    ///\sa See \ref MappingType for the possible values.
   3.590 +    void mappingType(MappingType m_type)
   3.591 +    {
   3.592 +      _mapping_type = m_type;
   3.593 +    }
   3.594 +
   3.595 +    ///Finds a mapping.
   3.596 +
   3.597 +    ///This method finds a mapping from g1 into g2 according to the mapping
   3.598 +    ///type set by \ref mappingType(MappingType) "mappingType()".
   3.599 +    ///
   3.600 +    ///By subsequent calls, it returns all possible mappings one-by-one.
   3.601 +    ///
   3.602 +    ///\retval true if a mapping is found.
   3.603 +    ///\retval false if there is no (more) mapping.
   3.604 +    bool find()
   3.605 +    {
   3.606 +      switch(_mapping_type)
   3.607 +        {
   3.608 +        case SUBGRAPH:
   3.609 +          return extMatch<SUBGRAPH>();
   3.610 +        case INDUCED:
   3.611 +          return extMatch<INDUCED>();
   3.612 +        case ISOMORPH:
   3.613 +          return extMatch<ISOMORPH>();
   3.614 +        default:
   3.615 +          return false;
   3.616 +        }
   3.617 +    }
   3.618 +  };
   3.619 +
   3.620 +  template<typename G1, typename G2>
   3.621 +  class Vf2ppWizardBase {
   3.622 +  protected:
   3.623 +    typedef G1 Graph1;
   3.624 +    typedef G2 Graph2;
   3.625 +
   3.626 +    const G1 &_g1;
   3.627 +    const G2 &_g2;
   3.628 +
   3.629 +    MappingType _mapping_type;
   3.630 +
   3.631 +    typedef typename G1::template NodeMap<typename G2::Node> Mapping;
   3.632 +    bool _local_mapping;
   3.633 +    void *_mapping;
   3.634 +    void createMapping() {
   3.635 +      _mapping = new Mapping(_g1);
   3.636 +    }
   3.637 +
   3.638 +    bool _local_nodeLabels;
   3.639 +    typedef typename G1::template NodeMap<int> NodeLabels1;
   3.640 +    typedef typename G2::template NodeMap<int> NodeLabels2;
   3.641 +    void *_nodeLabels1, *_nodeLabels2;
   3.642 +    void createNodeLabels() {
   3.643 +      _nodeLabels1 = new NodeLabels1(_g1,0);
   3.644 +      _nodeLabels2 = new NodeLabels2(_g2,0);
   3.645 +    }
   3.646 +
   3.647 +    Vf2ppWizardBase(const G1 &g1,const G2 &g2)
   3.648 +      : _g1(g1), _g2(g2), _mapping_type(SUBGRAPH),
   3.649 +        _local_mapping(1), _local_nodeLabels(1) { }
   3.650 +  };
   3.651 +
   3.652 +
   3.653 +  /// \brief Auxiliary class for the function-type interface of %VF2
   3.654 +  /// Plus Plus algorithm.
   3.655 +  ///
   3.656 +  /// This auxiliary class implements the named parameters of
   3.657 +  /// \ref vf2pp() "function-type interface" of \ref Vf2pp algorithm.
   3.658 +  ///
   3.659 +  /// \warning This class is not to be used directly.
   3.660 +  ///
   3.661 +  /// \tparam TR The traits class that defines various types used by the
   3.662 +  /// algorithm.
   3.663 +  template<typename TR>
   3.664 +  class Vf2ppWizard : public TR {
   3.665 +    typedef TR Base;
   3.666 +    typedef typename TR::Graph1 Graph1;
   3.667 +    typedef typename TR::Graph2 Graph2;
   3.668 +    typedef typename TR::Mapping Mapping;
   3.669 +    typedef typename TR::NodeLabels1 NodeLabels1;
   3.670 +    typedef typename TR::NodeLabels2 NodeLabels2;
   3.671 +
   3.672 +    using TR::_g1;
   3.673 +    using TR::_g2;
   3.674 +    using TR::_mapping_type;
   3.675 +    using TR::_mapping;
   3.676 +    using TR::_nodeLabels1;
   3.677 +    using TR::_nodeLabels2;
   3.678 +
   3.679 +  public:
   3.680 +    ///Constructor
   3.681 +    Vf2ppWizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) { }
   3.682 +
   3.683 +    ///Copy constructor
   3.684 +    Vf2ppWizard(const Base &b) : Base(b) {}
   3.685 +
   3.686 +
   3.687 +    template<typename T>
   3.688 +    struct SetMappingBase : public Base {
   3.689 +      typedef T Mapping;
   3.690 +      SetMappingBase(const Base &b) : Base(b) { }
   3.691 +    };
   3.692 +
   3.693 +    ///\brief \ref named-templ-param "Named parameter" for setting
   3.694 +    ///the mapping.
   3.695 +    ///
   3.696 +    ///\ref named-templ-param "Named parameter" function for setting
   3.697 +    ///the map that stores the found embedding.
   3.698 +    template<typename T>
   3.699 +    Vf2ppWizard< SetMappingBase<T> > mapping(const T &t) {
   3.700 +      Base::_mapping=reinterpret_cast<void*>(const_cast<T*>(&t));
   3.701 +      Base::_local_mapping = 0;
   3.702 +      return Vf2ppWizard<SetMappingBase<T> >(*this);
   3.703 +    }
   3.704 +
   3.705 +    template<typename NL1, typename NL2>
   3.706 +    struct SetNodeLabelsBase : public Base {
   3.707 +      typedef NL1 NodeLabels1;
   3.708 +      typedef NL2 NodeLabels2;
   3.709 +      SetNodeLabelsBase(const Base &b) : Base(b) { }
   3.710 +    };
   3.711 +
   3.712 +    ///\brief \ref named-templ-param "Named parameter" for setting the
   3.713 +    ///node labels.
   3.714 +    ///
   3.715 +    ///\ref named-templ-param "Named parameter" function for setting
   3.716 +    ///the node labels.
   3.717 +    ///
   3.718 +    ///\param nodeLabels1 A \ref concepts::ReadMap "readable node map"
   3.719 +    ///of g1 with integer value. In case of K different labels, the labels
   3.720 +    ///must be the {0,1,..,K-1} numbers.
   3.721 +    ///\param nodeLabels2 A \ref concepts::ReadMap "readable node map"
   3.722 +    ///of g2 with integer value. In case of K different labels, the labels
   3.723 +    ///must be the {0,1,..,K-1} numbers.
   3.724 +    template<typename NL1, typename NL2>
   3.725 +    Vf2ppWizard< SetNodeLabelsBase<NL1,NL2> >
   3.726 +    nodeLabels(const NL1 &nodeLabels1, const NL2 &nodeLabels2) {
   3.727 +      Base::_local_nodeLabels = 0;
   3.728 +      Base::_nodeLabels1=
   3.729 +        reinterpret_cast<void*>(const_cast<NL1*>(&nodeLabels1));
   3.730 +      Base::_nodeLabels2=
   3.731 +        reinterpret_cast<void*>(const_cast<NL2*>(&nodeLabels2));
   3.732 +      return Vf2ppWizard<SetNodeLabelsBase<NL1,NL2> >
   3.733 +        (SetNodeLabelsBase<NL1,NL2>(*this));
   3.734 +    }
   3.735 +
   3.736 +
   3.737 +    ///\brief \ref named-templ-param "Named parameter" for setting
   3.738 +    ///the mapping type.
   3.739 +    ///
   3.740 +    ///\ref named-templ-param "Named parameter" for setting
   3.741 +    ///the mapping type.
   3.742 +    ///
   3.743 +    ///The mapping type is set to \ref SUBGRAPH by default.
   3.744 +    ///
   3.745 +    ///\sa See \ref MappingType for the possible values.
   3.746 +    Vf2ppWizard<Base> &mappingType(MappingType m_type) {
   3.747 +      _mapping_type = m_type;
   3.748 +      return *this;
   3.749 +    }
   3.750 +
   3.751 +    ///\brief \ref named-templ-param "Named parameter" for setting
   3.752 +    ///the mapping type to \ref INDUCED.
   3.753 +    ///
   3.754 +    ///\ref named-templ-param "Named parameter" for setting
   3.755 +    ///the mapping type to \ref INDUCED.
   3.756 +    Vf2ppWizard<Base> &induced() {
   3.757 +      _mapping_type = INDUCED;
   3.758 +      return *this;
   3.759 +    }
   3.760 +
   3.761 +    ///\brief \ref named-templ-param "Named parameter" for setting
   3.762 +    ///the mapping type to \ref ISOMORPH.
   3.763 +    ///
   3.764 +    ///\ref named-templ-param "Named parameter" for setting
   3.765 +    ///the mapping type to \ref ISOMORPH.
   3.766 +    Vf2ppWizard<Base> &iso() {
   3.767 +      _mapping_type = ISOMORPH;
   3.768 +      return *this;
   3.769 +    }
   3.770 +
   3.771 +    ///Runs the %VF2 Plus Plus algorithm.
   3.772 +
   3.773 +    ///This method runs the VF2 Plus Plus algorithm.
   3.774 +    ///
   3.775 +    ///\retval true if a mapping is found.
   3.776 +    ///\retval false if there is no mapping.
   3.777 +    bool run() {
   3.778 +      if(Base::_local_mapping)
   3.779 +        Base::createMapping();
   3.780 +      if(Base::_local_nodeLabels)
   3.781 +        Base::createNodeLabels();
   3.782 +
   3.783 +      Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2 >
   3.784 +        alg(_g1, _g2, *reinterpret_cast<Mapping*>(_mapping),
   3.785 +            *reinterpret_cast<NodeLabels1*>(_nodeLabels1),
   3.786 +            *reinterpret_cast<NodeLabels2*>(_nodeLabels2));
   3.787 +
   3.788 +      alg.mappingType(_mapping_type);
   3.789 +
   3.790 +      const bool ret = alg.find();
   3.791 +
   3.792 +      if(Base::_local_nodeLabels) {
   3.793 +        delete reinterpret_cast<NodeLabels1*>(_nodeLabels1);
   3.794 +        delete reinterpret_cast<NodeLabels2*>(_nodeLabels2);
   3.795 +      }
   3.796 +      if(Base::_local_mapping)
   3.797 +        delete reinterpret_cast<Mapping*>(_mapping);
   3.798 +
   3.799 +      return ret;
   3.800 +    }
   3.801 +
   3.802 +    ///Get a pointer to the generated Vf2pp object.
   3.803 +
   3.804 +    ///Gives a pointer to the generated Vf2pp object.
   3.805 +    ///
   3.806 +    ///\return Pointer to the generated Vf2pp object.
   3.807 +    ///\warning Don't forget to delete the referred Vf2pp object after use.
   3.808 +    Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2 >*
   3.809 +    getPtrToVf2ppObject(){
   3.810 +      if(Base::_local_mapping)
   3.811 +        Base::createMapping();
   3.812 +      if(Base::_local_nodeLabels)
   3.813 +        Base::createNodeLabels();
   3.814 +
   3.815 +      Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2 >* ptr =
   3.816 +        new Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2>
   3.817 +        (_g1, _g2, *reinterpret_cast<Mapping*>(_mapping),
   3.818 +         *reinterpret_cast<NodeLabels1*>(_nodeLabels1),
   3.819 +         *reinterpret_cast<NodeLabels2*>(_nodeLabels2));
   3.820 +      ptr->mappingType(_mapping_type);
   3.821 +      if(Base::_local_mapping)
   3.822 +        ptr->_deallocMappingAfterUse=true;
   3.823 +      if(Base::_local_nodeLabels)
   3.824 +        ptr->_deallocLabelMapsAfterUse=true;
   3.825 +
   3.826 +      return ptr;
   3.827 +    }
   3.828 +
   3.829 +    ///Counts the number of mappings.
   3.830 +
   3.831 +    ///This method counts the number of mappings.
   3.832 +    ///
   3.833 +    /// \return The number of mappings.
   3.834 +    int count() {
   3.835 +      if(Base::_local_mapping)
   3.836 +        Base::createMapping();
   3.837 +      if(Base::_local_nodeLabels)
   3.838 +        Base::createNodeLabels();
   3.839 +
   3.840 +      Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2>
   3.841 +        alg(_g1, _g2, *reinterpret_cast<Mapping*>(_mapping),
   3.842 +            *reinterpret_cast<NodeLabels1*>(_nodeLabels1),
   3.843 +            *reinterpret_cast<NodeLabels2*>(_nodeLabels2));
   3.844 +
   3.845 +      alg.mappingType(_mapping_type);
   3.846 +
   3.847 +      int ret = 0;
   3.848 +      while(alg.find())
   3.849 +        ++ret;
   3.850 +
   3.851 +      if(Base::_local_nodeLabels) {
   3.852 +        delete reinterpret_cast<NodeLabels1*>(_nodeLabels1);
   3.853 +        delete reinterpret_cast<NodeLabels2*>(_nodeLabels2);
   3.854 +      }
   3.855 +      if(Base::_local_mapping)
   3.856 +        delete reinterpret_cast<Mapping*>(_mapping);
   3.857 +
   3.858 +      return ret;
   3.859 +    }
   3.860 +  };
   3.861 +
   3.862 +
   3.863 +  ///Function-type interface for VF2 Plus Plus algorithm.
   3.864 +
   3.865 +  /// \ingroup graph_isomorphism
   3.866 +  ///Function-type interface for VF2 Plus Plus algorithm.
   3.867 +  ///
   3.868 +  ///This function has several \ref named-func-param "named parameters"
   3.869 +  ///declared as the members of class \ref Vf2ppWizard.
   3.870 +  ///The following examples show how to use these parameters.
   3.871 +  ///\code
   3.872 +  ///  ListGraph::NodeMap<ListGraph::Node> m(g);
   3.873 +  ///  // Find an embedding of graph g1 into graph g2
   3.874 +  ///  vf2pp(g1,g2).mapping(m).run();
   3.875 +  ///
   3.876 +  ///  // Check whether graphs g1 and g2 are isomorphic
   3.877 +  ///  bool is_iso = vf2pp(g1,g2).iso().run();
   3.878 +  ///
   3.879 +  ///  // Count the number of isomorphisms
   3.880 +  ///  int num_isos = vf2pp(g1,g2).iso().count();
   3.881 +  ///
   3.882 +  ///  // Iterate through all the induced subgraph mappings
   3.883 +  ///  //of graph g1 into g2 using the labels c1 and c2
   3.884 +  ///  auto* myVf2pp = vf2pp(g1,g2).mapping(m).nodeLabels(c1,c2)
   3.885 +  ///  .induced().getPtrToVf2Object();
   3.886 +  ///  while(myVf2pp->find()){
   3.887 +  ///    //process the current mapping m
   3.888 +  ///  }
   3.889 +  ///  delete myVf22pp;
   3.890 +  ///\endcode
   3.891 +  ///\warning Don't forget to put the \ref Vf2ppWizard::run() "run()",
   3.892 +  ///\ref Vf2ppWizard::count() "count()" or
   3.893 +  ///the \ref Vf2ppWizard::getPtrToVf2ppObject() "getPtrToVf2ppObject()"
   3.894 +  ///to the end of the expression.
   3.895 +  ///\sa Vf2ppWizard
   3.896 +  ///\sa Vf2pp
   3.897 +  template<class G1, class G2>
   3.898 +  Vf2ppWizard<Vf2ppWizardBase<G1,G2> > vf2pp(const G1 &g1, const G2 &g2) {
   3.899 +    return Vf2ppWizard<Vf2ppWizardBase<G1,G2> >(g1,g2);
   3.900 +  }
   3.901 +
   3.902 +}
   3.903 +
   3.904 +#endif
   3.905 +
     4.1 --- a/test/CMakeLists.txt	Tue Sep 19 15:23:43 2017 +0200
     4.2 +++ b/test/CMakeLists.txt	Tue Sep 19 14:08:20 2017 +0200
     4.3 @@ -55,6 +55,7 @@
     4.4    tsp_test
     4.5    unionfind_test
     4.6    vf2_test
     4.7 +  vf2pp_test
     4.8  )
     4.9  
    4.10  IF(LEMON_HAVE_LP)
     5.1 --- a/test/vf2_test.cc	Tue Sep 19 15:23:43 2017 +0200
     5.2 +++ b/test/vf2_test.cc	Tue Sep 19 14:08:20 2017 +0200
     5.3 @@ -2,7 +2,7 @@
     5.4   *
     5.5   * This file is a part of LEMON, a generic C++ optimization library.
     5.6   *
     5.7 - * Copyright (C) 2015
     5.8 + * Copyright (C) 2015-2017
     5.9   * EMAXA Kutato-fejleszto Kft. (EMAXA Research Ltd.)
    5.10   *
    5.11   * Permission to use, modify and distribute this software is granted
    5.12 @@ -183,18 +183,21 @@
    5.13  
    5.14  class EqComparable {
    5.15  public:
    5.16 -  bool operator==(const EqComparable&) { return false; }
    5.17 +  bool operator==(const EqComparable&) {
    5.18 +    return false;
    5.19 +  }
    5.20  };
    5.21  
    5.22  template<class A, class B>
    5.23  class EqClass {
    5.24  public:
    5.25 -  bool operator()(A, B) { return false; }
    5.26 +  bool operator()(A, B){
    5.27 +    return false;
    5.28 +  }
    5.29  };
    5.30  
    5.31  template<class G1,class G2>
    5.32 -void checkVf2Compile()
    5.33 -{
    5.34 +void checkVf2Compile() {
    5.35    G1 g;
    5.36    G2 h;
    5.37    concepts::ReadWriteMap<typename G1::Node, typename G2::Node> r;
    5.38 @@ -205,8 +208,15 @@
    5.39    succ = vf2(g,h).induced().run();
    5.40    succ = vf2(g,h).iso().run();
    5.41    succ = vf2(g,h).mapping(r).run();
    5.42 +
    5.43 +  Vf2<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
    5.44 +      EqClass<typename G1::Node,typename G2::Node> >
    5.45 +    myVf2(g,h,r,EqClass<typename G1::Node,typename G2::Node>());
    5.46 +  myVf2.find();
    5.47 +
    5.48    succ = vf2(g,h).induced().mapping(r).run();
    5.49    succ = vf2(g,h).iso().mapping(r).run();
    5.50 +
    5.51    concepts::ReadMap<typename G1::Node, EqComparable> l1;
    5.52    concepts::ReadMap<typename G2::Node, EqComparable> l2;
    5.53    succ = vf2(g,h).nodeLabels(l1,l2).mapping(r).run();
    5.54 @@ -214,24 +224,21 @@
    5.55      .mapping(r).run();
    5.56  }
    5.57  
    5.58 -void justCompile()
    5.59 -{
    5.60 +void justCompile() {
    5.61    checkVf2Compile<concepts::Graph,concepts::Graph>();
    5.62    checkVf2Compile<concepts::Graph,SmartGraph>();
    5.63    checkVf2Compile<SmartGraph,concepts::Graph>();
    5.64  }
    5.65  
    5.66  template<class G1, class G2, class I>
    5.67 -void checkSub(const G1 &g1, const G2 &g2, const I &i)
    5.68 -{
    5.69 +void checkSub(const G1 &g1, const G2 &g2, const I &i) {
    5.70    {
    5.71      std::set<typename G2::Node> image;
    5.72 -    for(typename G1::NodeIt n(g1);n!=INVALID;++n)
    5.73 -      {
    5.74 -          check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
    5.75 -          check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
    5.76 -          image.insert(i[n]);
    5.77 -      }
    5.78 +    for(typename G1::NodeIt n(g1);n!=INVALID;++n){
    5.79 +      check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
    5.80 +      check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
    5.81 +      image.insert(i[n]);
    5.82 +    }
    5.83    }
    5.84    for(typename G1::EdgeIt e(g1);e!=INVALID;++e)
    5.85      check(findEdge(g2,i[g1.u(e)],i[g1.v(e)])!=INVALID,
    5.86 @@ -239,87 +246,78 @@
    5.87  }
    5.88  
    5.89  template<class G1, class G2, class I>
    5.90 -void checkInd(const G1 &g1, const G2 &g2, const I &i)
    5.91 -  {
    5.92 +void checkInd(const G1 &g1, const G2 &g2, const I &i) {
    5.93    std::set<typename G2::Node> image;
    5.94 -  for(typename G1::NodeIt n(g1);n!=INVALID;++n)
    5.95 -    {
    5.96 +  for(typename G1::NodeIt n(g1);n!=INVALID;++n) {
    5.97      check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
    5.98      check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
    5.99      image.insert(i[n]);
   5.100 -    }
   5.101 +  }
   5.102    for(typename G1::NodeIt n(g1); n!=INVALID; ++n)
   5.103      for(typename G1::NodeIt m(g1); m!=INVALID; ++m)
   5.104 -      if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID))
   5.105 -        {
   5.106 +      if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID)) {
   5.107          std::cout << "Wrong isomorphism: edge mismatch";
   5.108          exit(1);
   5.109 -        }
   5.110 -  }
   5.111 -
   5.112 -template<class G1,class G2>
   5.113 -int checkSub(const G1 &g1, const G2 &g2)
   5.114 -{
   5.115 -  typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
   5.116 -  if(vf2(g1,g2).mapping(iso).run())
   5.117 -    {
   5.118 -      checkSub(g1,g2,iso);
   5.119 -      return true;
   5.120 -    }
   5.121 -  else return false;
   5.122 +      }
   5.123  }
   5.124  
   5.125  template<class G1,class G2>
   5.126 -int checkInd(const G1 &g1, const G2 &g2)
   5.127 -{
   5.128 +int checkSub(const G1 &g1, const G2 &g2) {
   5.129    typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
   5.130 -  if(vf2(g1,g2).induced().mapping(iso).run())
   5.131 -    {
   5.132 -      checkInd(g1,g2,iso);
   5.133 -      return true;
   5.134 -    }
   5.135 -  else return false;
   5.136 +  if(vf2(g1,g2).mapping(iso).run()) {
   5.137 +    checkSub(g1,g2,iso);
   5.138 +    return true;
   5.139 +  }
   5.140 +  else
   5.141 +    return false;
   5.142  }
   5.143  
   5.144  template<class G1,class G2>
   5.145 -int checkIso(const G1 &g1, const G2 &g2)
   5.146 -{
   5.147 +int checkInd(const G1 &g1, const G2 &g2) {
   5.148    typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
   5.149 -  if(vf2(g1,g2).iso().mapping(iso).run())
   5.150 -    {
   5.151 -      check(countNodes(g1)==countNodes(g2),
   5.152 -            "Wrong iso alg.: they are not isomophic.");
   5.153 -      checkInd(g1,g2,iso);
   5.154 -      return true;
   5.155 -    }
   5.156 -  else return false;
   5.157 +  if(vf2(g1,g2).induced().mapping(iso).run()) {
   5.158 +    checkInd(g1,g2,iso);
   5.159 +    return true;
   5.160 +  }
   5.161 +  else
   5.162 +    return false;
   5.163 +}
   5.164 +
   5.165 +template<class G1,class G2>
   5.166 +int checkIso(const G1 &g1, const G2 &g2) {
   5.167 +  typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
   5.168 +  if(vf2(g1,g2).iso().mapping(iso).run()) {
   5.169 +    check(countNodes(g1)==countNodes(g2),
   5.170 +          "Wrong iso alg.: they are not isomophic.");
   5.171 +    checkInd(g1,g2,iso);
   5.172 +    return true;
   5.173 +  }
   5.174 +  else
   5.175 +    return false;
   5.176  }
   5.177  
   5.178  template<class G1, class G2, class L1, class L2, class I>
   5.179  void checkLabel(const G1 &g1, const G2 &,
   5.180 -                const L1 &l1, const L2 &l2,const I &i)
   5.181 -{
   5.182 +                const L1 &l1, const L2 &l2,const I &i) {
   5.183    for(typename G1::NodeIt n(g1);n!=INVALID;++n)
   5.184 -    {
   5.185 -      check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch.");
   5.186 -    }
   5.187 +    check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch.");
   5.188  }
   5.189  
   5.190  template<class G1,class G2,class L1,class L2>
   5.191 -int checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2)
   5.192 -{
   5.193 +int checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2) {
   5.194    typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
   5.195 -  if(vf2(g1,g2).nodeLabels(l1,l2).mapping(iso).run())
   5.196 -    {
   5.197 -      checkSub(g1,g2,iso);
   5.198 -      checkLabel(g1,g2,l1,l2,iso);
   5.199 -      return true;
   5.200 -    }
   5.201 -  else return false;
   5.202 +  if(vf2(g1,g2).nodeLabels(l1,l2).mapping(iso).run()){
   5.203 +    checkSub(g1,g2,iso);
   5.204 +    checkLabel(g1,g2,l1,l2,iso);
   5.205 +    return true;
   5.206 +  }
   5.207 +  else
   5.208 +    return false;
   5.209  }
   5.210  
   5.211  int main() {
   5.212    make_graphs();
   5.213 +  //   justCompile();
   5.214    check(checkSub(c5,petersen), "There should exist a C5->Petersen mapping.");
   5.215    check(!checkSub(c7,petersen),
   5.216          "There should not exist a C7->Petersen mapping.");
     6.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     6.2 +++ b/test/vf2pp_test.cc	Tue Sep 19 14:08:20 2017 +0200
     6.3 @@ -0,0 +1,392 @@
     6.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     6.5 + *
     6.6 + * This file is a part of LEMON, a generic C++ optimization library.
     6.7 + *
     6.8 + * Copyright (C) 2015-2017
     6.9 + * EMAXA Kutato-fejleszto Kft. (EMAXA Research Ltd.)
    6.10 + *
    6.11 + * Permission to use, modify and distribute this software is granted
    6.12 + * provided that this copyright notice appears in all copies. For
    6.13 + * precise terms see the accompanying LICENSE file.
    6.14 + *
    6.15 + * This software is provided "AS IS" with no warranty of any kind,
    6.16 + * express or implied, and with no claim as to its suitability for any
    6.17 + * purpose.
    6.18 + *
    6.19 + */
    6.20 +
    6.21 +#include <lemon/vf2pp.h>
    6.22 +#include <lemon/concepts/digraph.h>
    6.23 +#include <lemon/smart_graph.h>
    6.24 +#include <lemon/lgf_reader.h>
    6.25 +#include <lemon/concepts/maps.h>
    6.26 +#include <lemon/maps.h>
    6.27 +#include <lemon/list_graph.h>
    6.28 +
    6.29 +#include <test/test_tools.h>
    6.30 +#include <sstream>
    6.31 +
    6.32 +using namespace lemon;
    6.33 +
    6.34 +char petersen_lgf[] =
    6.35 +  "@nodes\n"
    6.36 +  "label col1 col2\n"
    6.37 +  "0 1 1\n"
    6.38 +  "1 1 2\n"
    6.39 +  "2 1 3\n"
    6.40 +  "3 1 4\n"
    6.41 +  "4 2 5\n"
    6.42 +  "5 2 1\n"
    6.43 +  "6 2 2\n"
    6.44 +  "7 2 3\n"
    6.45 +  "8 2 4\n"
    6.46 +  "9 2 5\n"
    6.47 +  "@arcs\n"
    6.48 +  "     -\n"
    6.49 +  "0 1\n"
    6.50 +  "1 2\n"
    6.51 +  "2 3\n"
    6.52 +  "3 4\n"
    6.53 +  "4 0\n"
    6.54 +  "0 5\n"
    6.55 +  "1 6\n"
    6.56 +  "2 7\n"
    6.57 +  "3 8\n"
    6.58 +  "4 9\n"
    6.59 +  "5 8\n"
    6.60 +  "5 7\n"
    6.61 +  "9 6\n"
    6.62 +  "9 7\n"
    6.63 +  "6 8\n";
    6.64 +
    6.65 +char c5_lgf[] =
    6.66 +  "@nodes\n"
    6.67 +  "label col\n"
    6.68 +  "0 1\n"
    6.69 +  "1 2\n"
    6.70 +  "2 3\n"
    6.71 +  "3 4\n"
    6.72 +  "4 5\n"
    6.73 +  "@arcs\n"
    6.74 +  "     -\n"
    6.75 +  "0 1\n"
    6.76 +  "1 2\n"
    6.77 +  "2 3\n"
    6.78 +  "3 4\n"
    6.79 +  "4 0\n";
    6.80 +
    6.81 +char c7_lgf[] =
    6.82 +  "@nodes\n"
    6.83 +  "label\n"
    6.84 +  "0\n"
    6.85 +  "1\n"
    6.86 +  "2\n"
    6.87 +  "3\n"
    6.88 +  "4\n"
    6.89 +  "5\n"
    6.90 +  "6\n"
    6.91 +  "@arcs\n"
    6.92 +  "     -\n"
    6.93 +  "0 1\n"
    6.94 +  "1 2\n"
    6.95 +  "2 3\n"
    6.96 +  "3 4\n"
    6.97 +  "4 5\n"
    6.98 +  "5 6\n"
    6.99 +  "6 0\n";
   6.100 +
   6.101 +char c10_lgf[] =
   6.102 +  "@nodes\n"
   6.103 +  "label\n"
   6.104 +  "0\n"
   6.105 +  "1\n"
   6.106 +  "2\n"
   6.107 +  "3\n"
   6.108 +  "4\n"
   6.109 +  "5\n"
   6.110 +  "6\n"
   6.111 +  "7\n"
   6.112 +  "8\n"
   6.113 +  "9\n"
   6.114 +  "@arcs\n"
   6.115 +  "     -\n"
   6.116 +  "0 1\n"
   6.117 +  "1 2\n"
   6.118 +  "2 3\n"
   6.119 +  "3 4\n"
   6.120 +  "4 5\n"
   6.121 +  "5 6\n"
   6.122 +  "6 7\n"
   6.123 +  "7 8\n"
   6.124 +  "8 9\n"
   6.125 +  "9 0\n";
   6.126 +
   6.127 +char p10_lgf[] =
   6.128 +  "@nodes\n"
   6.129 +  "label\n"
   6.130 +  "0\n"
   6.131 +  "1\n"
   6.132 +  "2\n"
   6.133 +  "3\n"
   6.134 +  "4\n"
   6.135 +  "5\n"
   6.136 +  "6\n"
   6.137 +  "7\n"
   6.138 +  "8\n"
   6.139 +  "9\n"
   6.140 +  "@arcs\n"
   6.141 +  "     -\n"
   6.142 +  "0 1\n"
   6.143 +  "1 2\n"
   6.144 +  "2 3\n"
   6.145 +  "3 4\n"
   6.146 +  "4 5\n"
   6.147 +  "5 6\n"
   6.148 +  "6 7\n"
   6.149 +  "7 8\n"
   6.150 +  "8 9\n";
   6.151 +
   6.152 +SmartGraph petersen, c5, c7, c10, p10;
   6.153 +SmartGraph::NodeMap<int> petersen_col1(petersen);
   6.154 +SmartGraph::NodeMap<int> petersen_col2(petersen);
   6.155 +SmartGraph::NodeMap<int> c5_col(c5);
   6.156 +
   6.157 +void make_graphs(){
   6.158 +  std::stringstream ss(petersen_lgf);
   6.159 +  graphReader(petersen, ss)
   6.160 +    .nodeMap("col1",petersen_col1)
   6.161 +    .nodeMap("col2",petersen_col2)
   6.162 +    .run();
   6.163 +
   6.164 +  ss.clear();
   6.165 +  ss.str("");
   6.166 +  ss<<c5_lgf;
   6.167 +
   6.168 +  graphReader(c5, ss)
   6.169 +    .nodeMap("col",c5_col)
   6.170 +    .run();
   6.171 +
   6.172 +  ss.clear();
   6.173 +  ss.str("");
   6.174 +  ss<<c7_lgf;
   6.175 +  graphReader(c7, ss).run();
   6.176 +
   6.177 +  ss.clear();
   6.178 +  ss.str("");
   6.179 +  ss<<c10_lgf;
   6.180 +  graphReader(c10, ss).run();
   6.181 +
   6.182 +  ss.clear();
   6.183 +  ss.str("");
   6.184 +  ss<<p10_lgf;
   6.185 +  graphReader(p10, ss).run();
   6.186 +
   6.187 +}
   6.188 +
   6.189 +class IntConvertible1{
   6.190 +public:
   6.191 +  operator int(){
   6.192 +    return 0;
   6.193 +  }
   6.194 +};
   6.195 +
   6.196 +class IntConvertible2{
   6.197 +public:
   6.198 +  operator int(){
   6.199 +    return 0;
   6.200 +  }
   6.201 +};
   6.202 +
   6.203 +template<class G1,class G2>
   6.204 +void checkVf2Compile() {
   6.205 +  G1 g;
   6.206 +  G2 h;
   6.207 +  concepts::ReadWriteMap<typename G1::Node, typename G2::Node> r;
   6.208 +  bool succ;
   6.209 +  ::lemon::ignore_unused_variable_warning(succ);
   6.210 +
   6.211 +  succ = vf2pp(g,h).run();
   6.212 +  succ = vf2pp(g,h).induced().run();
   6.213 +  succ = vf2pp(g,h).iso().run();
   6.214 +  succ = vf2pp(g,h).mapping(r).run();
   6.215 +  succ = vf2pp(g,h).induced().mapping(r).run();
   6.216 +  succ = vf2pp(g,h).iso().mapping(r).run();
   6.217 +
   6.218 +
   6.219 +  concepts::ReadMap<typename G1::Node, int> c1;
   6.220 +  concepts::ReadMap<typename G2::Node, int> c2;
   6.221 +  Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
   6.222 +        concepts::ReadMap<typename G1::Node, int>,
   6.223 +        concepts::ReadMap<typename G2::Node, int> >
   6.224 +    myVf2pp(g,h,r,c1,c2);
   6.225 +  myVf2pp.find();
   6.226 +
   6.227 +  succ = vf2pp(g,h).nodeLabels(c1,c2).mapping(r).run();
   6.228 +  succ = vf2pp(g,h).nodeLabels(c1,c2)
   6.229 +    .mapping(r).run();
   6.230 +
   6.231 +
   6.232 +  concepts::ReadMap<typename G1::Node, char> c1_c;
   6.233 +  concepts::ReadMap<typename G2::Node, char> c2_c;
   6.234 +  Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
   6.235 +        concepts::ReadMap<typename G1::Node, char>,
   6.236 +        concepts::ReadMap<typename G2::Node, char> >
   6.237 +    myVf2pp_c(g,h,r,c1_c,c2_c);
   6.238 +  myVf2pp_c.find();
   6.239 +
   6.240 +  succ = vf2pp(g,h).nodeLabels(c1_c,c2_c).mapping(r).run();
   6.241 +  succ = vf2pp(g,h).nodeLabels(c1_c,c2_c)
   6.242 +    .mapping(r).run();
   6.243 +
   6.244 +
   6.245 +  concepts::ReadMap<typename G1::Node, IntConvertible1> c1_IntConv;
   6.246 +  concepts::ReadMap<typename G2::Node, IntConvertible2> c2_IntConv;
   6.247 +  Vf2pp<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
   6.248 +        concepts::ReadMap<typename G1::Node, IntConvertible1>,
   6.249 +        concepts::ReadMap<typename G2::Node, IntConvertible2> >
   6.250 +    myVf2pp_IntConv(g,h,r,c1_IntConv,c2_IntConv);
   6.251 +  myVf2pp_IntConv.find();
   6.252 +
   6.253 +  succ = vf2pp(g,h).nodeLabels(c1_IntConv,c2_IntConv).mapping(r).run();
   6.254 +  succ = vf2pp(g,h).nodeLabels(c1_IntConv,c2_IntConv)
   6.255 +    .mapping(r).run();
   6.256 +}
   6.257 +
   6.258 +void justCompile() {
   6.259 +  checkVf2Compile<concepts::Graph,concepts::Graph>();
   6.260 +  checkVf2Compile<concepts::Graph,SmartGraph>();
   6.261 +  checkVf2Compile<SmartGraph,concepts::Graph>();
   6.262 +}
   6.263 +
   6.264 +template<class G1, class G2, class I>
   6.265 +void checkSub(const G1 &g1, const G2 &g2, const I &i) {
   6.266 +  {
   6.267 +    std::set<typename G2::Node> image;
   6.268 +    for(typename G1::NodeIt n(g1);n!=INVALID;++n){
   6.269 +      check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
   6.270 +      check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
   6.271 +      image.insert(i[n]);
   6.272 +    }
   6.273 +  }
   6.274 +  for(typename G1::EdgeIt e(g1);e!=INVALID;++e)
   6.275 +    check(findEdge(g2,i[g1.u(e)],i[g1.v(e)])!=INVALID,
   6.276 +          "Wrong isomorphism: missing edge(checkSub).");
   6.277 +}
   6.278 +
   6.279 +template<class G1, class G2, class I>
   6.280 +void checkInd(const G1 &g1, const G2 &g2, const I &i) {
   6.281 +  std::set<typename G2::Node> image;
   6.282 +  for(typename G1::NodeIt n(g1);n!=INVALID;++n) {
   6.283 +    check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
   6.284 +    check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
   6.285 +    image.insert(i[n]);
   6.286 +  }
   6.287 +  for(typename G1::NodeIt n(g1); n!=INVALID; ++n)
   6.288 +    for(typename G1::NodeIt m(g1); m!=INVALID; ++m)
   6.289 +      if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID)) {
   6.290 +        std::cout << "Wrong isomorphism: edge mismatch";
   6.291 +        exit(1);
   6.292 +      }
   6.293 +}
   6.294 +
   6.295 +template<class G1,class G2>
   6.296 +int checkSub(const G1 &g1, const G2 &g2) {
   6.297 +  typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
   6.298 +  if(vf2pp(g1,g2).mapping(iso).run()){
   6.299 +    checkSub(g1,g2,iso);
   6.300 +    return true;
   6.301 +  }
   6.302 +  else
   6.303 +    return false;
   6.304 +}
   6.305 +
   6.306 +template<class G1,class G2>
   6.307 +int checkInd(const G1 &g1, const G2 &g2) {
   6.308 +  typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
   6.309 +  if(vf2pp(g1,g2).induced().mapping(iso).run()) {
   6.310 +    checkInd(g1,g2,iso);
   6.311 +    return true;
   6.312 +  }
   6.313 +  else
   6.314 +    return false;
   6.315 +}
   6.316 +
   6.317 +template<class G1,class G2>
   6.318 +int checkIso(const G1 &g1, const G2 &g2) {
   6.319 +  typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
   6.320 +  if(vf2pp(g1,g2).iso().mapping(iso).run()) {
   6.321 +    check(countNodes(g1)==countNodes(g2),
   6.322 +          "Wrong iso alg.: they are not isomophic.");
   6.323 +    checkInd(g1,g2,iso);
   6.324 +    return true;
   6.325 +  }
   6.326 +  else
   6.327 +    return false;
   6.328 +}
   6.329 +
   6.330 +template<class G1, class G2, class L1, class L2, class I>
   6.331 +void checkLabel(const G1 &g1, const G2 &,
   6.332 +                const L1 &l1, const L2 &l2,const I &i) {
   6.333 +  for(typename G1::NodeIt n(g1);n!=INVALID;++n)
   6.334 +    check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch.");
   6.335 +}
   6.336 +
   6.337 +template<class G1,class G2,class L1,class L2>
   6.338 +int checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2) {
   6.339 +  typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
   6.340 +  if(vf2pp(g1,g2).nodeLabels(l1,l2).mapping(iso).run()) {
   6.341 +    checkSub(g1,g2,iso);
   6.342 +    checkLabel(g1,g2,l1,l2,iso);
   6.343 +    return true;
   6.344 +  }
   6.345 +  else
   6.346 +    return false;
   6.347 +}
   6.348 +
   6.349 +int main() {
   6.350 +  make_graphs();
   6.351 +//   justCompile();
   6.352 +  check(checkSub(c5,petersen), "There should exist a C5->Petersen mapping.");
   6.353 +  check(!checkSub(c7,petersen),
   6.354 +        "There should not exist a C7->Petersen mapping.");
   6.355 +  check(checkSub(p10,petersen), "There should exist a P10->Petersen mapping.");
   6.356 +  check(!checkSub(c10,petersen),
   6.357 +        "There should not exist a C10->Petersen mapping.");
   6.358 +  check(checkSub(petersen,petersen),
   6.359 +        "There should exist a Petersen->Petersen mapping.");
   6.360 +
   6.361 +  check(checkInd(c5,petersen),
   6.362 +        "There should exist a C5->Petersen spanned mapping.");
   6.363 +  check(!checkInd(c7,petersen),
   6.364 +        "There should exist a C7->Petersen spanned mapping.");
   6.365 +  check(!checkInd(p10,petersen),
   6.366 +        "There should not exist a P10->Petersen spanned mapping.");
   6.367 +  check(!checkInd(c10,petersen),
   6.368 +        "There should not exist a C10->Petersen spanned mapping.");
   6.369 +  check(checkInd(petersen,petersen),
   6.370 +        "There should exist a Petersen->Petersen spanned mapping.");
   6.371 +
   6.372 +  check(!checkSub(petersen,c10),
   6.373 +        "There should not exist a Petersen->C10 mapping.");
   6.374 +  check(checkSub(p10,c10),
   6.375 +        "There should exist a P10->C10 mapping.");
   6.376 +  check(!checkInd(p10,c10),
   6.377 +        "There should not exist a P10->C10 spanned mapping.");
   6.378 +  check(!checkSub(c10,p10),
   6.379 +        "There should not exist a C10->P10 mapping.");
   6.380 +
   6.381 +  check(!checkIso(p10,c10),
   6.382 +        "P10 and C10 are not isomorphic.");
   6.383 +  check(checkIso(c10,c10),
   6.384 +        "C10 and C10 are isomorphic.");
   6.385 +
   6.386 +  check(!vf2pp(p10,c10).iso().run(),
   6.387 +        "P10 and C10 are not isomorphic.");
   6.388 +  check(vf2pp(c10,c10).iso().run(),
   6.389 +        "C10 and C10 are isomorphic.");
   6.390 +
   6.391 +  check(!checkSub(c5,petersen,c5_col,petersen_col1),
   6.392 +        "There should exist a C5->Petersen mapping.");
   6.393 +  check(checkSub(c5,petersen,c5_col,petersen_col2),
   6.394 +        "There should exist a C5->Petersen mapping.");
   6.395 +}