COIN-OR::LEMON - Graph Library

Changeset 1405:3feba0ea1bda in lemon


Ignore:
Timestamp:
09/19/17 14:08:20 (2 years ago)
Author:
Peter Madarasi <madarasip@…>
Branch:
default
Phase:
public
Message:

Vf2 improvements and Vf2pp implementation (#597)

Files:
3 added
3 edited

Legend:

Unmodified
Added
Removed
  • lemon/vf2.h

    r1370 r1405  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2015
     5 * Copyright (C) 2015-2017
    66 * EMAXA Kutato-fejleszto Kft. (EMAXA Research Ltd.)
    77 *
     
    2727#include <lemon/dfs.h>
    2828#include <lemon/bfs.h>
     29#include <lemon/bits/vf2_internals.h>
    2930
    3031#include <vector>
    31 #include <set>
    32 
    33 namespace lemon
    34 {
    35   namespace bits
    36   {
    37     namespace vf2
    38     {
    39       class AlwaysEq
    40       {
     32
     33namespace lemon {
     34  namespace bits {
     35    namespace vf2 {
     36
     37      class AlwaysEq {
    4138      public:
    4239        template<class T1, class T2>
    43         bool operator()(T1, T2) const
    44         {
     40        bool operator()(T1&, T2&) const {
    4541          return true;
    4642        }
     
    4844
    4945      template<class M1, class M2>
    50       class MapEq
    51       {
     46      class MapEq{
    5247        const M1 &_m1;
    5348        const M2 &_m2;
    5449      public:
    55         MapEq(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
    56         bool operator()(typename M1::Key k1, typename M2::Key k2) const
    57         {
     50        MapEq(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) { }
     51        bool operator()(typename M1::Key k1, typename M2::Key k2) const {
    5852          return _m1[k1] == _m2[k2];
    5953        }
    6054      };
    6155
     56
     57
    6258      template <class G>
    63       class DfsLeaveOrder : public DfsVisitor<G>
    64       {
     59      class DfsLeaveOrder : public DfsVisitor<G> {
    6560        const G &_g;
    6661        std::vector<typename G::Node> &_order;
     
    6863      public:
    6964        DfsLeaveOrder(const G &g, std::vector<typename G::Node> &order)
    70           : i(countNodes(g)), _g(g), _order(order)
    71         {}
    72         void leave(const typename G::Node &node)
    73         {
     65          : i(countNodes(g)), _g(g), _order(order) { }
     66        void leave(const typename G::Node &node) {
    7467          _order[--i]=node;
    7568        }
     
    7770
    7871      template <class G>
    79       class BfsLeaveOrder : public BfsVisitor<G>
    80       {
     72      class BfsLeaveOrder : public BfsVisitor<G> {
    8173        int i;
    8274        const G &_g;
     
    8476      public:
    8577        BfsLeaveOrder(const G &g, std::vector<typename G::Node> &order)
    86           : i(0), _g(g), _order(order)
    87         {}
    88         void process(const typename G::Node &node)
    89         {
     78          : i(0), _g(g), _order(order){
     79        }
     80        void process(const typename G::Node &node) {
    9081          _order[i++]=node;
    9182        }
     
    9485  }
    9586
    96   ///Graph mapping types.
    97 
    98   ///\ingroup graph_isomorphism
    99   ///The \ref Vf2 "VF2" algorithm is capable of finding different kind of
    100   ///embeddings, this enum specifies its type.
    101   ///
    102   ///See \ref graph_isomorphism for a more detailed description.
    103   enum Vf2MappingType {
    104     /// Subgraph isomorphism
    105     SUBGRAPH = 0,
    106     /// Induced subgraph isomorphism
    107     INDUCED = 1,
    108     /// Graph isomorphism
    109 
    110     /// If the two graph has the same number of nodes, than it is
    111     /// equivalent to \ref INDUCED, and if they also have the same
    112     /// number of edges, then it is also equivalent to \ref SUBGRAPH.
    113     ///
    114     /// However, using this setting is faster than the other two
    115     /// options.
    116     ISOMORPH = 2
    117   };
    11887
    11988  ///%VF2 algorithm class.
     
    145114           class NEQ = bits::vf2::AlwaysEq >
    146115#endif
    147   class Vf2
    148   {
     116  class Vf2 {
    149117    //Current depth in the DFS tree.
    150118    int _depth;
    151119    //Functor with bool operator()(G1::Node,G2::Node), which returns 1
    152     //if and only if the 2 nodes are equivalent.
     120    //ifff the two nodes are equivalent.
    153121    NEQ _nEq;
    154122
     
    157125    //a node of g2.
    158126    M &_mapping;
    159     //order[i] is the node of g1, for which we find a pair if depth=i
     127    //order[i] is the node of g1, for which we search a pair if depth=i
    160128    std::vector<typename G1::Node> order;
    161129    //currEdgeIts[i] is an edge iterator, witch is last used in the ith
     
    164132    //The small graph.
    165133    const G1 &_g1;
    166     //The big graph.
     134    //The large graph.
    167135    const G2 &_g2;
    168     //lookup tables for cut the searchtree
     136    //lookup tables for cutting the searchtree
    169137    typename G1::template NodeMap<int> rNew1t,rInOut1t;
    170138
    171     Vf2MappingType _mapping_type;
     139    MappingType _mapping_type;
     140
     141    bool _deallocMappingAfterUse;
    172142
    173143    //cut the search tree
    174     template<Vf2MappingType MT>
    175     bool cut(const typename G1::Node n1,const typename G2::Node n2) const
    176     {
     144    template<MappingType MT>
     145    bool cut(const typename G1::Node n1,const typename G2::Node n2) const {
    177146      int rNew2=0,rInOut2=0;
    178       for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2)
    179         {
    180           const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
    181           if(_conn[currNode]>0)
    182             ++rInOut2;
    183           else if(MT!=SUBGRAPH&&_conn[currNode]==0)
    184             ++rNew2;
    185         }
    186       switch(MT)
    187         {
    188         case INDUCED:
    189           return rInOut1t[n1]<=rInOut2&&rNew1t[n1]<=rNew2;
    190         case SUBGRAPH:
    191           return rInOut1t[n1]<=rInOut2;
    192         case ISOMORPH:
    193           return rInOut1t[n1]==rInOut2&&rNew1t[n1]==rNew2;
    194         default:
    195           return false;
    196         }
    197     }
    198 
    199     template<Vf2MappingType MT>
    200     bool feas(const typename G1::Node n1,const typename G2::Node n2)
    201     {
     147      for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
     148        const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
     149        if(_conn[currNode]>0)
     150          ++rInOut2;
     151        else if(MT!=SUBGRAPH&&_conn[currNode]==0)
     152          ++rNew2;
     153      }
     154      switch(MT) {
     155      case INDUCED:
     156        return rInOut1t[n1]<=rInOut2&&rNew1t[n1]<=rNew2;
     157      case SUBGRAPH:
     158        return rInOut1t[n1]<=rInOut2;
     159      case ISOMORPH:
     160        return rInOut1t[n1]==rInOut2&&rNew1t[n1]==rNew2;
     161      default:
     162        return false;
     163      }
     164    }
     165
     166    template<MappingType MT>
     167    bool feas(const typename G1::Node n1,const typename G2::Node n2) {
    202168      if(!_nEq(n1,n2))
    203169        return 0;
    204170
    205       for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1)
    206         {
    207           const typename G1::Node currNode=_g1.oppositeNode(n1,e1);
    208           if(_mapping[currNode]!=INVALID)
    209             --_conn[_mapping[currNode]];
    210         }
     171      for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
     172        const typename G1::Node& currNode=_g1.oppositeNode(n1,e1);
     173        if(_mapping[currNode]!=INVALID)
     174          --_conn[_mapping[currNode]];
     175      }
    211176      bool isIso=1;
    212       for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2)
    213         {
    214           const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
    215           if(_conn[currNode]<-1)
    216             ++_conn[currNode];
    217           else if(MT!=SUBGRAPH&&_conn[currNode]==-1)
    218             {
     177      for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
     178        int& connCurrNode = _conn[_g2.oppositeNode(n2,e2)];
     179        if(connCurrNode<-1)
     180          ++connCurrNode;
     181        else if(MT!=SUBGRAPH&&connCurrNode==-1) {
     182          isIso=0;
     183          break;
     184        }
     185      }
     186
     187      for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
     188        const typename G2::Node& currNodePair=_mapping[_g1.oppositeNode(n1,e1)];
     189        int& connCurrNodePair=_conn[currNodePair];
     190        if(currNodePair!=INVALID&&connCurrNodePair!=-1) {
     191          switch(MT) {
     192          case INDUCED:
     193          case ISOMORPH:
     194            isIso=0;
     195            break;
     196          case SUBGRAPH:
     197            if(connCurrNodePair<-1)
    219198              isIso=0;
    220               break;
    221             }
    222         }
    223 
    224       for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1)
    225         {
    226           const typename G1::Node currNode=_g1.oppositeNode(n1,e1);
    227           if(_mapping[currNode]!=INVALID&&_conn[_mapping[currNode]]!=-1)
    228             {
    229               switch(MT)
    230                 {
    231                 case INDUCED:
    232                 case ISOMORPH:
    233                   isIso=0;
    234                   break;
    235                 case SUBGRAPH:
    236                   if(_conn[_mapping[currNode]]<-1)
    237                     isIso=0;
    238                   break;
    239                 }
    240               _conn[_mapping[currNode]]=-1;
    241             }
    242         }
     199            break;
     200          }
     201          connCurrNodePair=-1;
     202        }
     203      }
    243204      return isIso&&cut<MT>(n1,n2);
    244205    }
    245206
    246     void addPair(const typename G1::Node n1,const typename G2::Node n2)
    247     {
     207    void addPair(const typename G1::Node n1,const typename G2::Node n2) {
    248208      _conn[n2]=-1;
    249209      _mapping.set(n1,n2);
    250       for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2)
    251         if(_conn[_g2.oppositeNode(n2,e2)]!=-1)
    252           ++_conn[_g2.oppositeNode(n2,e2)];
    253     }
    254 
    255     void subPair(const typename G1::Node n1,const typename G2::Node n2)
    256     {
     210      for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
     211        int& currConn = _conn[_g2.oppositeNode(n2,e2)];
     212        if(currConn!=-1)
     213          ++currConn;
     214      }
     215    }
     216
     217    void subPair(const typename G1::Node n1,const typename G2::Node n2) {
    257218      _conn[n2]=0;
    258219      _mapping.set(n1,INVALID);
    259       for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2)
    260         {
    261           const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
    262           if(_conn[currNode]>0)
    263             --_conn[currNode];
    264           else if(_conn[currNode]==-1)
    265             ++_conn[n2];
    266         }
    267     }
    268 
    269     void setOrder()//we will find pairs for the nodes of g1 in this order
    270     {
     220      for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
     221        int& currConn = _conn[_g2.oppositeNode(n2,e2)];
     222        if(currConn>0)
     223          --currConn;
     224        else if(currConn==-1)
     225          ++_conn[n2];
     226      }
     227    }
     228
     229    void setOrder() {
     230      // we will find pairs for the nodes of g1 in this order
     231
    271232      // bits::vf2::DfsLeaveOrder<G1> v(_g1,order);
    272233      //   DfsVisit<G1,bits::vf2::DfsLeaveOrder<G1> >dfs(_g1, v);
     
    279240    }
    280241
    281     template<Vf2MappingType MT>
    282     bool extMatch()
    283     {
    284       while(_depth>=0)
    285         {
    286           //there are not nodes in g1, which has not pair in g2.
    287           if(_depth==static_cast<int>(order.size()))
    288             {
     242    template<MappingType MT>
     243    bool extMatch() {
     244      while(_depth>=0) {
     245        //there are not nodes in g1, which has not pair in g2.
     246        if(_depth==static_cast<int>(order.size())) {
     247          --_depth;
     248          return true;
     249        }
     250        typename G1::Node& nodeOfDepth = order[_depth];
     251        const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth];
     252        typename G2::IncEdgeIt &edgeItOfDepth = currEdgeIts[_depth];
     253        //the node of g2, which neighbours are the candidates for
     254        //the pair of nodeOfDepth
     255        typename G2::Node currPNode;
     256        if(edgeItOfDepth==INVALID) {
     257          typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth);
     258          //if pairOfNodeOfDepth!=INVALID, we dont use
     259          //fstMatchedE
     260          if(pairOfNodeOfDepth==INVALID)
     261            for(; fstMatchedE!=INVALID &&
     262                  _mapping[_g1.oppositeNode(nodeOfDepth,
     263                                            fstMatchedE)]==INVALID;
     264                ++fstMatchedE) ; //find fstMatchedE
     265          if(fstMatchedE==INVALID||pairOfNodeOfDepth!=INVALID) {
     266            //We found no covered neighbours, this means
     267            //the graph is not connected(or _depth==0).  Each
     268            //uncovered(and there are some other properties due
     269            //to the spec. problem types) node of g2 is
     270            //candidate.  We can read the iterator of the last
     271            //tried node from the match if it is not the first
     272            //try(match[nodeOfDepth]!=INVALID)
     273            typename G2::NodeIt n2(_g2);
     274            //if it's not the first try
     275            if(pairOfNodeOfDepth!=INVALID) {
     276              n2=++typename G2::NodeIt(_g2,pairOfNodeOfDepth);
     277              subPair(nodeOfDepth,pairOfNodeOfDepth);
     278            }
     279            for(; n2!=INVALID; ++n2)
     280              if(MT!=SUBGRAPH) {
     281                if(_conn[n2]==0&&feas<MT>(nodeOfDepth,n2))
     282                  break;
     283              }
     284              else if(_conn[n2]>=0&&feas<MT>(nodeOfDepth,n2))
     285                break;
     286            // n2 is the next candidate
     287            if(n2!=INVALID){
     288              addPair(nodeOfDepth,n2);
     289              ++_depth;
     290            }
     291            else // there are no more candidates
    289292              --_depth;
    290               return true;
    291             }
    292           //the node of g2, which neighbours are the candidates for
    293           //the pair of order[_depth]
    294           typename G2::Node currPNode;
    295           if(currEdgeIts[_depth]==INVALID)
    296             {
    297               typename G1::IncEdgeIt fstMatchedE(_g1,order[_depth]);
    298               //if _mapping[order[_depth]]!=INVALID, we dont use
    299               //fstMatchedE
    300               if(_mapping[order[_depth]]==INVALID)
    301                 for(; fstMatchedE!=INVALID &&
    302                       _mapping[_g1.oppositeNode(order[_depth],
    303                                               fstMatchedE)]==INVALID;
    304                     ++fstMatchedE) ; //find fstMatchedE
    305               if(fstMatchedE==INVALID||_mapping[order[_depth]]!=INVALID)
    306                 {
    307                   //We did not find an covered neighbour, this means
    308                   //the graph is not connected(or _depth==0).  Every
    309                   //uncovered(and there are some other properties due
    310                   //to the spec. problem types) node of g2 is
    311                   //candidate.  We can read the iterator of the last
    312                   //tryed node from the match if it is not the first
    313                   //try(match[order[_depth]]!=INVALID)
    314                   typename G2::NodeIt n2(_g2);
    315                   //if its not the first try
    316                   if(_mapping[order[_depth]]!=INVALID)
    317                     {
    318                       n2=++typename G2::NodeIt(_g2,_mapping[order[_depth]]);
    319                       subPair(order[_depth],_mapping[order[_depth]]);
    320                     }
    321                   for(; n2!=INVALID; ++n2)
    322                     if(MT!=SUBGRAPH&&_conn[n2]==0)
    323                       {
    324                         if(feas<MT>(order[_depth],n2))
    325                           break;
    326                       }
    327                     else if(MT==SUBGRAPH&&_conn[n2]>=0)
    328                       if(feas<MT>(order[_depth],n2))
    329                         break;
    330                   // n2 is the next candidate
    331                   if(n2!=INVALID)
    332                     {
    333                       addPair(order[_depth],n2);
    334                       ++_depth;
    335                     }
    336                   else // there is no more candidate
    337                     --_depth;
    338                   continue;
    339                 }
    340               else
    341                 {
    342                   currPNode=_mapping[_g1.oppositeNode(order[_depth],
    343                                                       fstMatchedE)];
    344                   currEdgeIts[_depth]=typename G2::IncEdgeIt(_g2,currPNode);
    345                 }
    346             }
    347           else
    348             {
    349               currPNode=_g2.oppositeNode(_mapping[order[_depth]],
    350                                          currEdgeIts[_depth]);
    351               subPair(order[_depth],_mapping[order[_depth]]);
    352               ++currEdgeIts[_depth];
    353             }
    354           for(; currEdgeIts[_depth]!=INVALID; ++currEdgeIts[_depth])
    355             {
    356               const typename G2::Node currNode =
    357                 _g2.oppositeNode(currPNode, currEdgeIts[_depth]);
    358               //if currNode is uncovered
    359               if(_conn[currNode]>0&&feas<MT>(order[_depth],currNode))
    360                 {
    361                   addPair(order[_depth],currNode);
    362                   break;
    363                 }
    364             }
    365           currEdgeIts[_depth]==INVALID?--_depth:++_depth;
    366         }
     293            continue;
     294          }
     295          else {
     296            currPNode=_mapping[_g1.oppositeNode(nodeOfDepth,
     297                                                fstMatchedE)];
     298            edgeItOfDepth=typename G2::IncEdgeIt(_g2,currPNode);
     299          }
     300        }
     301        else {
     302          currPNode=_g2.oppositeNode(pairOfNodeOfDepth,
     303                                     edgeItOfDepth);
     304          subPair(nodeOfDepth,pairOfNodeOfDepth);
     305          ++edgeItOfDepth;
     306        }
     307        for(; edgeItOfDepth!=INVALID; ++edgeItOfDepth) {
     308          const typename G2::Node currNode =
     309            _g2.oppositeNode(currPNode, edgeItOfDepth);
     310          if(_conn[currNode]>0&&feas<MT>(nodeOfDepth,currNode)) {
     311            addPair(nodeOfDepth,currNode);
     312            break;
     313          }
     314        }
     315        edgeItOfDepth==INVALID?--_depth:++_depth;
     316      }
    367317      return false;
    368318    }
    369319
    370320    //calc. the lookup table for cut the searchtree
    371     void setRNew1tRInOut1t()
    372     {
     321    void setRNew1tRInOut1t() {
    373322      typename G1::template NodeMap<int> tmp(_g1,0);
    374       for(unsigned int i=0; i<order.size(); ++i)
    375         {
    376           tmp[order[i]]=-1;
    377           for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1)
    378             {
    379               const typename G1::Node currNode=_g1.oppositeNode(order[i],e1);
    380               if(tmp[currNode]>0)
    381                 ++rInOut1t[order[i]];
    382               else if(tmp[currNode]==0)
    383                 ++rNew1t[order[i]];
    384             }
    385           for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1)
    386             {
    387               const typename G1::Node currNode=_g1.oppositeNode(order[i],e1);
    388               if(tmp[currNode]!=-1)
    389                 ++tmp[currNode];
    390             }
    391         }
     323      for(unsigned int i=0; i<order.size(); ++i) {
     324        const typename G1::Node& orderI = order[i];
     325        tmp[orderI]=-1;
     326        for(typename G1::IncEdgeIt e1(_g1,orderI); e1!=INVALID; ++e1) {
     327          const typename G1::Node currNode=_g1.oppositeNode(orderI,e1);
     328          if(tmp[currNode]>0)
     329            ++rInOut1t[orderI];
     330          else if(tmp[currNode]==0)
     331            ++rNew1t[orderI];
     332        }
     333        for(typename G1::IncEdgeIt e1(_g1,orderI); e1!=INVALID; ++e1) {
     334          const typename G1::Node currNode=_g1.oppositeNode(orderI,e1);
     335          if(tmp[currNode]!=-1)
     336            ++tmp[currNode];
     337        }
     338      }
    392339    }
    393340  public:
     
    400347    ///\param m \ref concepts::ReadWriteMap "read-write" NodeMap
    401348    ///storing the found mapping.
    402     ///\param neq A bool-valued binary functor determinining whether a node is
     349    ///\param neq A bool-valued binary functor determining whether a node is
    403350    ///mappable to another. By default it is an always true operator.
    404     Vf2(const G1 &g1, const G2 &g2,M &m, const NEQ &neq = NEQ() ) :
     351    Vf2(const G1 &g1, const G2 &g2, M &m, const NEQ &neq = NEQ() ) :
    405352      _nEq(neq), _conn(g2,0), _mapping(m), order(countNodes(g1)),
    406353      currEdgeIts(countNodes(g1),INVALID), _g1(g1), _g2(g2), rNew1t(g1,0),
    407       rInOut1t(g1,0), _mapping_type(SUBGRAPH)
    408     {
     354      rInOut1t(g1,0), _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0) {
    409355      _depth=0;
    410356      setOrder();
     
    414360    }
    415361
     362    ///Destructor
     363
     364    ///Destructor.
     365    ///
     366
     367    ~Vf2(){
     368      if(_deallocMappingAfterUse)
     369        delete &_mapping;
     370    }
     371
    416372    ///Returns the current mapping type
    417373
    418374    ///Returns the current mapping type
    419375    ///
    420     Vf2MappingType mappingType() const { return _mapping_type; }
     376    MappingType mappingType() const {
     377      return _mapping_type;
     378    }
    421379    ///Sets mapping type
    422380
     
    425383    ///The mapping type is set to \ref SUBGRAPH by default.
    426384    ///
    427     ///\sa See \ref Vf2MappingType for the possible values.
    428     void mappingType(Vf2MappingType m_type) { _mapping_type = m_type; }
     385    ///\sa See \ref MappingType for the possible values.
     386    void mappingType(MappingType m_type) {
     387      _mapping_type = m_type;
     388    }
    429389
    430390    ///Finds a mapping
    431391
    432     ///It finds a mapping between from g1 into g2 according to the mapping
    433     ///type set by \ref mappingType(Vf2MappingType) "mappingType()".
     392    ///It finds a mapping from g1 into g2 according to the mapping
     393    ///type set by \ref mappingType(MappingType) "mappingType()".
    434394    ///
    435395    ///By subsequent calls, it returns all possible mappings one-by-one.
     
    437397    ///\retval true if a mapping is found.
    438398    ///\retval false if there is no (more) mapping.
    439     bool find()
    440     {
    441       switch(_mapping_type)
    442         {
    443         case SUBGRAPH:
    444           return extMatch<SUBGRAPH>();
    445         case INDUCED:
    446           return extMatch<INDUCED>();
    447         case ISOMORPH:
    448           return extMatch<ISOMORPH>();
    449         default:
    450           return false;
    451         }
     399    bool find() {
     400      switch(_mapping_type) {
     401      case SUBGRAPH:
     402        return extMatch<SUBGRAPH>();
     403      case INDUCED:
     404        return extMatch<INDUCED>();
     405      case ISOMORPH:
     406        return extMatch<ISOMORPH>();
     407      default:
     408        return false;
     409      }
    452410    }
    453411  };
    454412
    455413  template<class G1, class G2>
    456   class Vf2WizardBase
    457   {
     414  class Vf2WizardBase {
    458415  protected:
    459416    typedef G1 Graph1;
     
    463420    const G2 &_g2;
    464421
    465     Vf2MappingType _mapping_type;
     422    MappingType _mapping_type;
    466423
    467424    typedef typename G1::template NodeMap<typename G2::Node> Mapping;
    468425    bool _local_mapping;
    469426    void *_mapping;
    470     void createMapping()
    471     {
     427    void createMapping() {
    472428      _mapping = new Mapping(_g1);
    473429    }
     430
     431    void *myVf2; //used in Vf2Wizard::find
     432
    474433
    475434    typedef bits::vf2::AlwaysEq NodeEq;
     
    477436
    478437    Vf2WizardBase(const G1 &g1,const G2 &g2)
    479       : _g1(g1), _g2(g2), _mapping_type(SUBGRAPH), _local_mapping(true) {}
     438      : _g1(g1), _g2(g2), _mapping_type(SUBGRAPH), _local_mapping(true) { }
    480439  };
     440
    481441
    482442  /// Auxiliary class for the function-type interface of %VF2 algorithm.
     
    490450  /// algorithm.
    491451  template<class TR>
    492   class Vf2Wizard : public TR
    493   {
     452  class Vf2Wizard : public TR {
    494453    typedef TR Base;
    495454    typedef typename TR::Graph1 Graph1;
     
    507466  public:
    508467    ///Constructor
    509     Vf2Wizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {}
     468    Vf2Wizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {
     469    }
    510470
    511471    ///Copy constructor
    512     Vf2Wizard(const Base &b) : Base(b) {}
     472    Vf2Wizard(const Base &b) : Base(b) { }
     473
     474    ///Copy constructor
     475    Vf2Wizard(const Vf2Wizard &b) : Base(b) {}
    513476
    514477
    515478    template<class T>
    516     struct SetMappingBase : public Base {
     479    struct SetMappingBase : public Base{
    517480      typedef T Mapping;
    518481      SetMappingBase(const Base &b) : Base(b) {}
     
    525488    ///the map that stores the found embedding.
    526489    template<class T>
    527     Vf2Wizard< SetMappingBase<T> > mapping(const T &t)
    528     {
     490    Vf2Wizard< SetMappingBase<T> > mapping(const T &t) {
    529491      Base::_mapping=reinterpret_cast<void*>(const_cast<T*>(&t));
    530492      Base::_local_mapping = false;
     
    537499      NodeEq _node_eq;
    538500      SetNodeEqBase(const Base &b, const NE &node_eq)
    539         : Base(b), _node_eq(node_eq) {}
     501        : Base(b), _node_eq(node_eq){
     502      }
    540503    };
    541504
     
    550513    ///always true operator.
    551514    template<class T>
    552     Vf2Wizard< SetNodeEqBase<T> > nodeEq(const T &node_eq)
    553     {
     515    Vf2Wizard< SetNodeEqBase<T> > nodeEq(const T &node_eq) {
    554516      return Vf2Wizard<SetNodeEqBase<T> >(SetNodeEqBase<T>(*this,node_eq));
    555517    }
     
    561523    ///the node labels defining equivalence relation between them.
    562524    ///
    563     ///\param m1 It is arbitrary \ref concepts::ReadMap "readable node map"
     525    ///\param m1 An arbitrary \ref concepts::ReadMap "readable node map"
    564526    ///of g1.
    565     ///\param m2 It is arbitrary \ref concepts::ReadMap "readable node map"
     527    ///\param m2 An arbitrary \ref concepts::ReadMap "readable node map"
    566528    ///of g2.
    567529    ///
     
    569531    template<class M1, class M2>
    570532    Vf2Wizard< SetNodeEqBase<bits::vf2::MapEq<M1,M2> > >
    571     nodeLabels(const M1 &m1,const M2 &m2)
    572     {
     533    nodeLabels(const M1 &m1,const M2 &m2){
    573534      return nodeEq(bits::vf2::MapEq<M1,M2>(m1,m2));
    574535    }
     
    582543    ///The mapping type is set to \ref SUBGRAPH by default.
    583544    ///
    584     ///\sa See \ref Vf2MappingType for the possible values.
    585     Vf2Wizard<Base> &mappingType(Vf2MappingType m_type)
    586     {
     545    ///\sa See \ref MappingType for the possible values.
     546    Vf2Wizard<Base> &mappingType(MappingType m_type) {
    587547      _mapping_type = m_type;
    588548      return *this;
     
    594554    ///\ref named-templ-param "Named parameter" for setting
    595555    ///the mapping type to \ref INDUCED.
    596     Vf2Wizard<Base> &induced()
    597     {
     556    Vf2Wizard<Base> &induced() {
    598557      _mapping_type = INDUCED;
    599558      return *this;
     
    605564    ///\ref named-templ-param "Named parameter" for setting
    606565    ///the mapping type to \ref ISOMORPH.
    607     Vf2Wizard<Base> &iso()
    608     {
     566    Vf2Wizard<Base> &iso() {
    609567      _mapping_type = ISOMORPH;
    610568      return *this;
    611569    }
    612570
     571
    613572    ///Runs VF2 algorithm.
    614573
     
    616575    ///
    617576    ///\retval true if a mapping is found.
    618     ///\retval false if there is no (more) mapping.
    619     bool run()
    620     {
     577    ///\retval false if there is no mapping.
     578    bool run(){
    621579      if(Base::_local_mapping)
    622580        Base::createMapping();
     
    631589      if(Base::_local_mapping)
    632590        delete reinterpret_cast<Mapping*>(_mapping);
     591
     592      return ret;
     593    }
     594
     595    ///Get a pointer to the generated Vf2 object.
     596
     597    ///Gives a pointer to the generated Vf2 object.
     598    ///
     599    ///\return Pointer to the generated Vf2 object.
     600    ///\warning Don't forget to delete the referred Vf2 object after use.
     601    Vf2<Graph1, Graph2, Mapping, NodeEq >* getPtrToVf2Object() {
     602      if(Base::_local_mapping)
     603        Base::createMapping();
     604      Vf2<Graph1, Graph2, Mapping, NodeEq >* ptr =
     605        new Vf2<Graph1, Graph2, Mapping, NodeEq>
     606        (_g1, _g2, *reinterpret_cast<Mapping*>(_mapping), _node_eq);
     607      ptr->mappingType(_mapping_type);
     608      if(Base::_local_mapping)
     609        ptr->_deallocMappingAfterUse = true;
     610      return ptr;
     611    }
     612
     613    ///Counts the number of mappings.
     614
     615    ///This method counts the number of mappings.
     616    ///
     617    /// \return The number of mappings.
     618    int count() {
     619      if(Base::_local_mapping)
     620        Base::createMapping();
     621
     622      Vf2<Graph1, Graph2, Mapping, NodeEq>
     623        alg(_g1, _g2, *reinterpret_cast<Mapping*>(_mapping), _node_eq);
     624      if(Base::_local_mapping)
     625        alg._deallocMappingAfterUse = true;
     626      alg.mappingType(_mapping_type);
     627
     628      int ret = 0;
     629      while(alg.find())
     630        ++ret;
    633631
    634632      return ret;
     
    645643  ///The following examples show how to use these parameters.
    646644  ///\code
    647   ///  // Find an embedding of graph g into graph h
     645  ///  // Find an embedding of graph g1 into graph g2
    648646  ///  ListGraph::NodeMap<ListGraph::Node> m(g);
    649   ///  vf2(g,h).mapping(m).run();
    650   ///
    651   ///  // Check whether graphs g and h are isomorphic
    652   ///  bool is_iso = vf2(g,h).iso().run();
     647  ///  vf2(g1,g2).mapping(m).run();
     648  ///
     649  ///  // Check whether graphs g1 and g2 are isomorphic
     650  ///  bool is_iso = vf2(g1,g2).iso().run();
     651  ///
     652  ///  // Count the number of isomorphisms
     653  ///  int num_isos = vf2(g1,g2).iso().count();
     654  ///
     655  ///  // Iterate through all the induced subgraph mappings of graph g1 into g2
     656  ///  auto* myVf2 = vf2(g1,g2).mapping(m).nodeLabels(c1,c2)
     657  ///  .induced().getPtrToVf2Object();
     658  ///  while(myVf2->find()){
     659  ///    //process the current mapping m
     660  ///  }
     661  ///  delete myVf22;
    653662  ///\endcode
    654   ///\warning Don't forget to put the \ref Vf2Wizard::run() "run()"
     663  ///\warning Don't forget to put the \ref Vf2Wizard::run() "run()",
     664  ///\ref Vf2Wizard::count() "count()" or
     665  ///the \ref Vf2Wizard::getPtrToVf2Object() "getPtrToVf2Object()"
    655666  ///to the end of the expression.
    656667  ///\sa Vf2Wizard
    657668  ///\sa Vf2
    658669  template<class G1, class G2>
    659   Vf2Wizard<Vf2WizardBase<G1,G2> > vf2(const G1 &g1, const G2 &g2)
    660   {
     670  Vf2Wizard<Vf2WizardBase<G1,G2> > vf2(const G1 &g1, const G2 &g2) {
    661671    return Vf2Wizard<Vf2WizardBase<G1,G2> >(g1,g2);
    662672  }
  • test/CMakeLists.txt

    r1350 r1405  
    5656  unionfind_test
    5757  vf2_test
     58  vf2pp_test
    5859)
    5960
  • test/vf2_test.cc

    r1352 r1405  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2015
     5 * Copyright (C) 2015-2017
    66 * EMAXA Kutato-fejleszto Kft. (EMAXA Research Ltd.)
    77 *
     
    184184class EqComparable {
    185185public:
    186   bool operator==(const EqComparable&) { return false; }
     186  bool operator==(const EqComparable&) {
     187    return false;
     188  }
    187189};
    188190
     
    190192class EqClass {
    191193public:
    192   bool operator()(A, B) { return false; }
     194  bool operator()(A, B){
     195    return false;
     196  }
    193197};
    194198
    195199template<class G1,class G2>
    196 void checkVf2Compile()
    197 {
     200void checkVf2Compile() {
    198201  G1 g;
    199202  G2 h;
     
    206209  succ = vf2(g,h).iso().run();
    207210  succ = vf2(g,h).mapping(r).run();
     211
     212  Vf2<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>,
     213      EqClass<typename G1::Node,typename G2::Node> >
     214    myVf2(g,h,r,EqClass<typename G1::Node,typename G2::Node>());
     215  myVf2.find();
     216
    208217  succ = vf2(g,h).induced().mapping(r).run();
    209218  succ = vf2(g,h).iso().mapping(r).run();
     219
    210220  concepts::ReadMap<typename G1::Node, EqComparable> l1;
    211221  concepts::ReadMap<typename G2::Node, EqComparable> l2;
     
    215225}
    216226
    217 void justCompile()
    218 {
     227void justCompile() {
    219228  checkVf2Compile<concepts::Graph,concepts::Graph>();
    220229  checkVf2Compile<concepts::Graph,SmartGraph>();
     
    223232
    224233template<class G1, class G2, class I>
    225 void checkSub(const G1 &g1, const G2 &g2, const I &i)
    226 {
     234void checkSub(const G1 &g1, const G2 &g2, const I &i) {
    227235  {
    228236    std::set<typename G2::Node> image;
    229     for(typename G1::NodeIt n(g1);n!=INVALID;++n)
    230       {
    231           check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
    232           check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
    233           image.insert(i[n]);
    234       }
     237    for(typename G1::NodeIt n(g1);n!=INVALID;++n){
     238      check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
     239      check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
     240      image.insert(i[n]);
     241    }
    235242  }
    236243  for(typename G1::EdgeIt e(g1);e!=INVALID;++e)
     
    240247
    241248template<class G1, class G2, class I>
    242 void checkInd(const G1 &g1, const G2 &g2, const I &i)
    243   {
     249void checkInd(const G1 &g1, const G2 &g2, const I &i) {
    244250  std::set<typename G2::Node> image;
    245   for(typename G1::NodeIt n(g1);n!=INVALID;++n)
    246     {
     251  for(typename G1::NodeIt n(g1);n!=INVALID;++n) {
    247252    check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping.");
    248253    check(image.count(i[n])==0,"Wrong isomorphism: not injective.");
    249254    image.insert(i[n]);
    250     }
     255  }
    251256  for(typename G1::NodeIt n(g1); n!=INVALID; ++n)
    252257    for(typename G1::NodeIt m(g1); m!=INVALID; ++m)
    253       if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID))
    254         {
     258      if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID)) {
    255259        std::cout << "Wrong isomorphism: edge mismatch";
    256260        exit(1);
    257         }
    258   }
     261      }
     262}
    259263
    260264template<class G1,class G2>
    261 int checkSub(const G1 &g1, const G2 &g2)
    262 {
     265int checkSub(const G1 &g1, const G2 &g2) {
    263266  typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
    264   if(vf2(g1,g2).mapping(iso).run())
    265     {
    266       checkSub(g1,g2,iso);
    267       return true;
    268     }
    269   else return false;
     267  if(vf2(g1,g2).mapping(iso).run()) {
     268    checkSub(g1,g2,iso);
     269    return true;
     270  }
     271  else
     272    return false;
    270273}
    271274
    272275template<class G1,class G2>
    273 int checkInd(const G1 &g1, const G2 &g2)
    274 {
     276int checkInd(const G1 &g1, const G2 &g2) {
    275277  typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
    276   if(vf2(g1,g2).induced().mapping(iso).run())
    277     {
    278       checkInd(g1,g2,iso);
    279       return true;
    280     }
    281   else return false;
     278  if(vf2(g1,g2).induced().mapping(iso).run()) {
     279    checkInd(g1,g2,iso);
     280    return true;
     281  }
     282  else
     283    return false;
    282284}
    283285
    284286template<class G1,class G2>
    285 int checkIso(const G1 &g1, const G2 &g2)
    286 {
     287int checkIso(const G1 &g1, const G2 &g2) {
    287288  typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
    288   if(vf2(g1,g2).iso().mapping(iso).run())
    289     {
    290       check(countNodes(g1)==countNodes(g2),
    291             "Wrong iso alg.: they are not isomophic.");
    292       checkInd(g1,g2,iso);
    293       return true;
    294     }
    295   else return false;
     289  if(vf2(g1,g2).iso().mapping(iso).run()) {
     290    check(countNodes(g1)==countNodes(g2),
     291          "Wrong iso alg.: they are not isomophic.");
     292    checkInd(g1,g2,iso);
     293    return true;
     294  }
     295  else
     296    return false;
    296297}
    297298
    298299template<class G1, class G2, class L1, class L2, class I>
    299300void checkLabel(const G1 &g1, const G2 &,
    300                 const L1 &l1, const L2 &l2,const I &i)
    301 {
     301                const L1 &l1, const L2 &l2,const I &i) {
    302302  for(typename G1::NodeIt n(g1);n!=INVALID;++n)
    303     {
    304       check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch.");
    305     }
     303    check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch.");
    306304}
    307305
    308306template<class G1,class G2,class L1,class L2>
    309 int checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2)
    310 {
     307int checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2) {
    311308  typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID);
    312   if(vf2(g1,g2).nodeLabels(l1,l2).mapping(iso).run())
    313     {
    314       checkSub(g1,g2,iso);
    315       checkLabel(g1,g2,l1,l2,iso);
    316       return true;
    317     }
    318   else return false;
     309  if(vf2(g1,g2).nodeLabels(l1,l2).mapping(iso).run()){
     310    checkSub(g1,g2,iso);
     311    checkLabel(g1,g2,l1,l2,iso);
     312    return true;
     313  }
     314  else
     315    return false;
    319316}
    320317
    321318int main() {
    322319  make_graphs();
     320  //   justCompile();
    323321  check(checkSub(c5,petersen), "There should exist a C5->Petersen mapping.");
    324322  check(!checkSub(c7,petersen),
Note: See TracChangeset for help on using the changeset viewer.