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.239 + ///\param m \ref concepts::ReadWriteMap "read-write" NodeMap
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 {