lemon/vf2.h
 changeset 1351 2f479109a71d parent 1350 a037254714b3 child 1352 f85ee41c84bc
     1.1 --- a/lemon/vf2.h	Mon Mar 30 17:42:30 2015 +0200
1.2 +++ b/lemon/vf2.h	Thu May 14 16:07:38 2015 +0200
1.3 @@ -18,6 +18,10 @@
1.4  #ifndef LEMON_VF2_H
1.5  #define LEMON_VF2_H
1.6
1.7 +///\ingroup graph_properties
1.8 +///\file
1.9 +///\brief VF2 algorithm \cite cordella2004sub.
1.10 +
1.11  #include <lemon/core.h>
1.12  #include <lemon/concepts/graph.h>
1.13  #include <lemon/dfs.h>
1.14 @@ -90,25 +94,69 @@
1.15      }
1.16    }
1.17
1.18 -  enum MappingType {
1.19 +  ///Graph mapping types.
1.20 +
1.21 +  ///\ingroup graph_isomorphism
1.22 +  ///The \ref Vf2 "VF2" algorithm is capable of finding different kind of
1.23 +  ///embeddings, this enum specifies its type.
1.24 +  ///
1.25 +  ///See \ref graph_isomorphism for a more detailed description.
1.26 +  enum Vf2MappingType {
1.27 +    /// Subgraph isomorphism
1.28      SUBGRAPH = 0,
1.29 +    /// Induced subgraph isomorphism
1.30      INDUCED = 1,
1.31 +    /// Graph isomorphism
1.32 +
1.33 +    /// If the two graph has the same number of nodes, than it is
1.34 +    /// equivalent to \ref INDUCED, and if they also have the same
1.35 +    /// number of edges, then it is also equivalent to \ref SUBGRAPH.
1.36 +    ///
1.37 +    /// However, using this setting is faster than the other two
1.38 +    /// options.
1.39      ISOMORPH = 2
1.40    };
1.41
1.42 -  template<class G1, class G2, class I, class NEq = bits::vf2::AlwaysEq >
1.43 +  ///%VF2 algorithm class.
1.44 +
1.45 +  ///\ingroup graph_isomorphism This class provides an efficient
1.46 +  ///implementation of the %VF2 algorithm \cite cordella2004sub
1.47 +  ///for variants of the (Sub)graph Isomorphism problem.
1.48 +  ///
1.49 +  ///There is also a \ref vf2() "function-type interface" called \ref vf2()
1.50 +  ///for the %VF2 algorithm, which is probably more convenient in most
1.51 +  ///use-cases.
1.52 +  ///
1.53 +  ///\tparam G1 The type of the graph to be embedded.
1.54 +  ///The default type is \ref ListDigraph.
1.55 +  ///\tparam G2 The type of the graph g1 will be embedded into.
1.56 +  ///The default type is \ref ListDigraph.
1.57 +  ///\tparam M The type of the NodeMap storing the mapping.
1.58 +  ///By default, it is G1::NodeMap<G2::Node>
1.59 +  ///\tparam NEQ A bool-valued binary functor determinining whether a node is
1.60 +  ///mappable to another. By default it is an always true operator.
1.61 +  ///
1.62 +  ///\sa vf2()
1.63 +#ifdef DOXYGEN
1.64 +  template<class G1, class G2, class M, class NEQ >
1.65 +#else
1.66 +  template<class G1=ListDigraph,
1.67 +           class G2=ListDigraph,
1.68 +           class M = typename G1::template NodeMap<G2::Node>,
1.69 +           class NEQ = bits::vf2::AlwaysEq >
1.70 +#endif
1.71    class Vf2
1.72    {
1.73      //Current depth in the DFS tree.
1.74      int _depth;
1.75      //Functor with bool operator()(G1::Node,G2::Node), which returns 1
1.76      //if and only if the 2 nodes are equivalent.
1.77 -    NEq _nEq;
1.78 +    NEQ _nEq;
1.79
1.80      typename G2::template NodeMap<int> _conn;
1.81 -    //Current matching. We index it by the nodes of g1, and match[v] is
1.82 +    //Current mapping. We index it by the nodes of g1, and match[v] is
1.83      //a node of g2.
1.84 -    I &_match;
1.85 +    M &_mapping;
1.86      //order[i] is the node of g1, for which we find a pair if depth=i
1.87      std::vector<typename G1::Node> order;
1.88      //currEdgeIts[i] is an edge iterator, witch is last used in the ith
1.89 @@ -121,10 +169,10 @@
1.90      //lookup tables for cut the searchtree
1.91      typename G1::template NodeMap<int> rNew1t,rInOut1t;
1.92
1.93 -    MappingType _mapping_type;
1.94 +    Vf2MappingType _mapping_type;
1.95
1.96      //cut the search tree
1.97 -    template<MappingType MT>
1.98 +    template<Vf2MappingType MT>
1.99      bool cut(const typename G1::Node n1,const typename G2::Node n2) const
1.100      {
1.101        int rNew2=0,rInOut2=0;
1.102 @@ -149,7 +197,7 @@
1.103          }
1.104      }
1.105
1.106 -    template<MappingType MT>
1.107 +    template<Vf2MappingType MT>
1.108      bool feas(const typename G1::Node n1,const typename G2::Node n2)
1.109      {
1.110        if(!_nEq(n1,n2))
1.111 @@ -158,8 +206,8 @@
1.112        for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1)
1.113          {
1.114            const typename G1::Node currNode=_g1.oppositeNode(n1,e1);
1.115 -          if(_match[currNode]!=INVALID)
1.116 -            --_conn[_match[currNode]];
1.117 +          if(_mapping[currNode]!=INVALID)
1.118 +            --_conn[_mapping[currNode]];
1.119          }
1.120        bool isIso=1;
1.121        for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2)
1.122 @@ -177,7 +225,7 @@
1.123        for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1)
1.124          {
1.125            const typename G1::Node currNode=_g1.oppositeNode(n1,e1);
1.126 -          if(_match[currNode]!=INVALID&&_conn[_match[currNode]]!=-1)
1.127 +          if(_mapping[currNode]!=INVALID&&_conn[_mapping[currNode]]!=-1)
1.128              {
1.129                switch(MT)
1.130                  {
1.131 @@ -186,11 +234,11 @@
1.132                    isIso=0;
1.133                    break;
1.134                  case SUBGRAPH:
1.135 -                  if(_conn[_match[currNode]]<-1)
1.136 +                  if(_conn[_mapping[currNode]]<-1)
1.137                      isIso=0;
1.138                    break;
1.139                  }
1.140 -              _conn[_match[currNode]]=-1;
1.141 +              _conn[_mapping[currNode]]=-1;
1.142              }
1.143          }
1.144        return isIso&&cut<MT>(n1,n2);
1.145 @@ -199,7 +247,7 @@
1.146      void addPair(const typename G1::Node n1,const typename G2::Node n2)
1.147      {
1.148        _conn[n2]=-1;
1.149 -      _match.set(n1,n2);
1.150 +      _mapping.set(n1,n2);
1.151        for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2)
1.152          if(_conn[_g2.oppositeNode(n2,e2)]!=-1)
1.153            ++_conn[_g2.oppositeNode(n2,e2)];
1.154 @@ -208,7 +256,7 @@
1.155      void subPair(const typename G1::Node n1,const typename G2::Node n2)
1.156      {
1.157        _conn[n2]=0;
1.158 -      _match.set(n1,INVALID);
1.159 +      _mapping.set(n1,INVALID);
1.160        for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2)
1.161          {
1.162            const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
1.163 @@ -231,9 +279,7 @@
1.164        bfs.run();
1.165      }
1.166
1.167 -  public:
1.168 -
1.169 -    template<MappingType MT>
1.170 +    template<Vf2MappingType MT>
1.171      bool extMatch()
1.172      {
1.173        while(_depth>=0)
1.174 @@ -250,14 +296,14 @@
1.175            if(currEdgeIts[_depth]==INVALID)
1.176              {
1.177                typename G1::IncEdgeIt fstMatchedE(_g1,order[_depth]);
1.178 -              //if _match[order[_depth]]!=INVALID, we dont use
1.179 +              //if _mapping[order[_depth]]!=INVALID, we dont use
1.180                //fstMatchedE
1.181 -              if(_match[order[_depth]]==INVALID)
1.182 +              if(_mapping[order[_depth]]==INVALID)
1.183                  for(; fstMatchedE!=INVALID &&
1.184 -                      _match[_g1.oppositeNode(order[_depth],
1.185 +                      _mapping[_g1.oppositeNode(order[_depth],
1.186                                                fstMatchedE)]==INVALID;
1.187                      ++fstMatchedE) ; //find fstMatchedE
1.188 -              if(fstMatchedE==INVALID||_match[order[_depth]]!=INVALID)
1.189 +              if(fstMatchedE==INVALID||_mapping[order[_depth]]!=INVALID)
1.190                  {
1.191                    //We did not find an covered neighbour, this means
1.192                    //the graph is not connected(or _depth==0).  Every
1.193 @@ -268,10 +314,10 @@
1.194                    //try(match[order[_depth]]!=INVALID)
1.195                    typename G2::NodeIt n2(_g2);
1.196                    //if its not the first try
1.197 -                  if(_match[order[_depth]]!=INVALID)
1.198 +                  if(_mapping[order[_depth]]!=INVALID)
1.199                      {
1.200 -                      n2=++typename G2::NodeIt(_g2,_match[order[_depth]]);
1.201 -                      subPair(order[_depth],_match[order[_depth]]);
1.202 +                      n2=++typename G2::NodeIt(_g2,_mapping[order[_depth]]);
1.203 +                      subPair(order[_depth],_mapping[order[_depth]]);
1.204                      }
1.205                    for(; n2!=INVALID; ++n2)
1.206                      if(MT!=SUBGRAPH&&_conn[n2]==0)
1.207 @@ -294,15 +340,16 @@
1.208                  }
1.209                else
1.210                  {
1.211 -                  currPNode=_match[_g1.oppositeNode(order[_depth],fstMatchedE)];
1.212 +                  currPNode=_mapping[_g1.oppositeNode(order[_depth],
1.213 +                                                      fstMatchedE)];
1.214                    currEdgeIts[_depth]=typename G2::IncEdgeIt(_g2,currPNode);
1.215                  }
1.216              }
1.217            else
1.218              {
1.219 -              currPNode=_g2.oppositeNode(_match[order[_depth]],
1.220 +              currPNode=_g2.oppositeNode(_mapping[order[_depth]],
1.221                                           currEdgeIts[_depth]);
1.222 -              subPair(order[_depth],_match[order[_depth]]);
1.223 +              subPair(order[_depth],_mapping[order[_depth]]);
1.224                ++currEdgeIts[_depth];
1.225              }
1.226            for(; currEdgeIts[_depth]!=INVALID; ++currEdgeIts[_depth])
1.227 @@ -345,8 +392,18 @@
1.228          }
1.229      }
1.230    public:
1.231 -    Vf2(const G1 &g1, const G2 &g2,I &i, const NEq &nEq = NEq() ) :
1.232 -      _nEq(nEq), _conn(g2,0), _match(i), order(countNodes(g1)),
1.233 +    ///Constructor
1.234 +
1.235 +    ///Constructor
1.236 +
1.237 +    ///\param g1 The graph to be embedded into \e g2.
1.238 +    ///\param g2 The graph \e g1 will be embedded into.
1.240 +    ///storing the found mapping.
1.241 +    ///\param neq A bool-valued binary functor determinining whether a node is
1.242 +    ///mappable to another. By default it is an always true operator.
1.243 +    Vf2(const G1 &g1, const G2 &g2,M &m, const NEQ &neq = NEQ() ) :
1.244 +      _nEq(neq), _conn(g2,0), _mapping(m), order(countNodes(g1)),
1.245        currEdgeIts(countNodes(g1),INVALID), _g1(g1), _g2(g2), rNew1t(g1,0),
1.246        rInOut1t(g1,0), _mapping_type(SUBGRAPH)
1.247      {
1.248 @@ -355,9 +412,29 @@
1.249        setRNew1tRInOut1t();
1.250      }
1.251
1.252 -    MappingType mappingType() const { return _mapping_type; }
1.253 -    void mappingType(MappingType m_type) { _mapping_type = m_type; }
1.254 +    ///Returns the current mapping type
1.255
1.256 +    ///Returns the current mapping type
1.257 +    ///
1.258 +    Vf2MappingType mappingType() const { return _mapping_type; }
1.259 +    ///Sets mapping type
1.260 +
1.261 +    ///Sets mapping type.
1.262 +    ///
1.263 +    ///The mapping type is set to \ref SUBGRAPH by default.
1.264 +    ///
1.265 +    ///\sa See \ref for the possible values.
1.266 +    void mappingType(Vf2MappingType m_type) { _mapping_type = m_type; }
1.267 +
1.268 +    ///Find a mapping
1.269 +
1.270 +    ///It finds a mapping between from g1 into g2 according to the mapping
1.271 +    ///type set by \ref mappingType(Vf2MappingType) "mappingType()".
1.272 +    ///
1.273 +    ///By subsequent calls, it returns all possible mappings one-by-one.
1.274 +    ///
1.275 +    ///\retval true if a mapping is found.
1.276 +    ///\retval false if there is no (more) mapping.
1.277      bool find()
1.278      {
1.279        switch(_mapping_type)
1.280 @@ -384,7 +461,7 @@
1.281      const G1 &_g1;
1.282      const G2 &_g2;
1.283
1.284 -    MappingType _mapping_type;
1.285 +    Vf2MappingType _mapping_type;
1.286
1.287      typedef typename G1::template NodeMap<typename G2::Node> Mapping;
1.288      bool _local_mapping;
1.289 @@ -401,6 +478,15 @@
1.290        : _g1(g1), _g2(g2), _mapping_type(SUBGRAPH), _local_mapping(true) {}
1.291    };
1.292
1.293 +  /// Auxiliary class for the function-type interface of %VF2 algorithm.
1.294 +
1.295 +  /// This auxiliary class implements the named parameters of
1.296 +  /// \ref vf2() "function-type interface" of \ref Vf2 algorithm.
1.297 +  ///
1.298 +  /// \warning This class should only be used through the function \ref vf2().
1.299 +  ///
1.300 +  /// \tparam TR The traits class that defines various types used by the
1.301 +  /// algorithm.
1.302    template<class TR>
1.303    class Vf2Wizard : public TR
1.304    {
1.305 @@ -418,7 +504,7 @@
1.306      using TR::_node_eq;
1.307
1.308    public:
1.309 -    ///Copy constructor
1.310 +    ///Constructor
1.311      Vf2Wizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {}
1.312
1.313      ///Copy constructor
1.314 @@ -457,6 +543,10 @@
1.315      ///
1.316      ///\ref named-templ-param "Named parameter" function for setting
1.317      ///the equivalence relation between the nodes.
1.318 +    ///
1.319 +    ///\param node_eq A bool-valued binary functor determinining
1.320 +    ///whether a node is mappable to another. By default it is an
1.321 +    ///always true operator.
1.322      template<class T>
1.323      Vf2Wizard< SetNodeEqBase<T> > nodeEq(const T &node_eq)
1.324      {
1.325 @@ -468,6 +558,11 @@
1.326      ///
1.327      ///\ref named-templ-param "Named parameter" function for setting
1.328      ///the node labels defining equivalence relation between them.
1.329 +    ///
1.330 +    ///\param m1 It is arbitrary \ref ReadMap "readable node map" of g1.
1.331 +    ///\param m1 It is arbitrary \ref ReadMap "readable node map" of g2.
1.332 +    ///
1.333 +    ///The value type of these maps must be equal comparable.
1.334      template<class M1, class M2>
1.335      Vf2Wizard< SetNodeEqBase<bits::vf2::MapEq<M1,M2> > >
1.336      nodeLabels(const M1 &m1,const M2 &m2)
1.337 @@ -475,24 +570,49 @@
1.338        return nodeEq(bits::vf2::MapEq<M1,M2>(m1,m2));
1.339      }
1.340
1.341 -    Vf2Wizard<Base> &mappingType(MappingType m_type)
1.342 +    ///\brief \ref named-templ-param "Named parameter" for setting
1.343 +    ///the mapping type.
1.344 +    ///
1.345 +    ///\ref named-templ-param "Named parameter" for setting
1.346 +    ///the mapping type.
1.347 +    ///
1.348 +    ///The mapping type is set to \ref SUBGRAPH by default.
1.349 +    ///
1.350 +    ///\sa See \ref for the possible values.
1.351 +    Vf2Wizard<Base> &mappingType(Vf2MappingType m_type)
1.352      {
1.353        _mapping_type = m_type;
1.354        return *this;
1.355      }
1.356
1.357 +    ///\brief \ref named-templ-param "Named parameter" for setting
1.358 +    ///the mapping type to \ref INDUCED.
1.359 +    ///
1.360 +    ///\ref named-templ-param "Named parameter" for setting
1.361 +    ///the mapping type to \ref INDUCED.
1.362      Vf2Wizard<Base> &induced()
1.363      {
1.364        _mapping_type = INDUCED;
1.365        return *this;
1.366      }
1.367
1.368 +    ///\brief \ref named-templ-param "Named parameter" for setting
1.369 +    ///the mapping type to \ref ISOMORPH.
1.370 +    ///
1.371 +    ///\ref named-templ-param "Named parameter" for setting
1.372 +    ///the mapping type to \ref ISOMORPH.
1.373      Vf2Wizard<Base> &iso()
1.374      {
1.375        _mapping_type = ISOMORPH;
1.376        return *this;
1.377      }
1.378
1.379 +    ///Runs VF2 algorithm.
1.380 +
1.381 +    ///This method runs VF2 algorithm.
1.382 +    ///
1.383 +    ///\retval true if a mapping is found.
1.384 +    ///\retval false if there is no (more) mapping.
1.385      bool run()
1.386      {
1.387        if(Base::_local_mapping)
1.388 @@ -512,6 +632,26 @@
1.389      }
1.390    };
1.391
1.392 +  ///Function-type interface for VF2 algorithm.
1.393 +
1.394 +  /// \ingroup graph_isomorphism
1.395 +  ///Function-type interface for VF2 algorithm \cite cordella2004sub.
1.396 +  ///
1.397 +  ///This function has several \ref named-func-param "named parameters"
1.398 +  ///declared as the members of class \ref Vf2Wizard.
1.399 +  ///The following examples show how to use these parameters.
1.400 +  ///\code
1.401 +  ///  // Find an embedding of graph g into graph h
1.402 +  ///  ListGraph::NodeMap<ListGraph::Node> m(g);
1.403 +  ///  vf2(g,h).mapping(m).run();
1.404 +  ///
1.405 +  ///  // Check whether graphs g and h are isomorphic
1.406 +  ///  bool is_iso = vf2(g,h).iso().run();
1.407 +  ///\endcode
1.408 +  ///\warning Don't forget to put the \ref Vf2Wizard::run() "run()"
1.409 +  ///to the end of the expression.
1.410 +  ///\sa Vf2Wizard
1.411 +  ///\sa Vf2
1.412    template<class G1, class G2>
1.413    Vf2Wizard<Vf2WizardBase<G1,G2> > vf2(const G1 &g1, const G2 &g2)
1.414    {