1.1 --- a/doc/groups.dox Mon Mar 30 17:42:30 2015 +0200
1.2 +++ b/doc/groups.dox Thu May 14 16:07:38 2015 +0200
1.3 @@ -561,6 +561,35 @@
1.4 */
1.5
1.6 /**
1.7 +@defgroup graph_isomorphism Graph Isomorphism
1.8 +@ingroup algs
1.9 +\brief Algorithms for testing (sub)graph isomorphism
1.10 +
1.11 +This group contains algorithms for finding isomorph copies of a
1.12 +given graph in another one, or simply check whether two graphs are isomorphic.
1.13 +
1.14 +The formal definition of subgraph isomorphism is as follows.
1.15 +
1.16 +We are given two graphs, \f$G_1=(V_1,E_1)\f$ and \f$G_2=(V_2,E_2)\f$. A
1.17 +function \f$f:V_1\longrightarrow V_2\f$ is called \e mapping or \e
1.18 +embedding if \f$f(u)\neq f(v)\f$ whenever \f$u\neq v\f$.
1.19 +
1.20 +The standard <em>Subgraph Isomorphism Problem (SIP)</em> looks for a
1.21 +mapping with the property that whenever \f$(u,v)\in E_1\f$, then
1.22 +\f$(f(u),f(v))\in E_2\f$.
1.23 +
1.24 +In case of <em>Induced Subgraph Isomorphism Problem (ISIP)</em> one
1.25 +also requires that if \f$(u,v)\not\in E_1\f$, then \f$(f(u),f(v))\not\in
1.26 +E_2\f$
1.27 +
1.28 +In addition, the graph nodes may be \e labeled, i.e. we are given two
1.29 +node labelings \f$l_1:V_1\longrightarrow L\f$ and \f$l_2:V_2\longrightarrow
1.30 +L\f$ and we require that \f$l_1(u)=l_2(f(u))\f$ holds for all nodes \f$u \in
1.31 +G\f$.
1.32 +
1.33 +*/
1.34 +
1.35 +/**
1.36 @defgroup planar Planar Embedding and Drawing
1.37 @ingroup algs
1.38 \brief Algorithms for planarity checking, embedding and drawing
2.1 --- a/doc/named-param.dox Mon Mar 30 17:42:30 2015 +0200
2.2 +++ b/doc/named-param.dox Thu May 14 16:07:38 2015 +0200
2.3 @@ -25,7 +25,7 @@
2.4 Several modern languages provide a convenient way to refer the
2.5 function parameters by name also when you call the function. It is
2.6 especially comfortable in case of a function having tons of parameters
2.7 -with natural default values. Sadly, C++ lack this amenity.
2.8 +with natural default values. Sadly, C++ lacks this amenity.
2.9
2.10 However, with a crafty trick and with some little
2.11 inconvenience, it is possible to emulate is.
3.1 --- a/doc/references.bib Mon Mar 30 17:42:30 2015 +0200
3.2 +++ b/doc/references.bib Thu May 14 16:07:38 2015 +0200
3.3 @@ -354,3 +354,17 @@
3.4 number = 6,
3.5 pages = {587--612}
3.6 }
3.7 +
3.8 +@article{cordella2004sub,
3.9 + title = {A (sub) graph isomorphism algorithm for matching
3.10 + large graphs},
3.11 + author = {Cordella, Luigi P and Foggia, Pasquale and Sansone,
3.12 + Carlo and Vento, Mario},
3.13 + journal = {Pattern Analysis and Machine Intelligence, IEEE
3.14 + Transactions on},
3.15 + volume = 26,
3.16 + number = 10,
3.17 + pages = {1367--1372},
3.18 + year = 2004,
3.19 + publisher = {IEEE}
3.20 +}
4.1 --- a/lemon/vf2.h Mon Mar 30 17:42:30 2015 +0200
4.2 +++ b/lemon/vf2.h Thu May 14 16:07:38 2015 +0200
4.3 @@ -18,6 +18,10 @@
4.4 #ifndef LEMON_VF2_H
4.5 #define LEMON_VF2_H
4.6
4.7 +///\ingroup graph_properties
4.8 +///\file
4.9 +///\brief VF2 algorithm \cite cordella2004sub.
4.10 +
4.11 #include <lemon/core.h>
4.12 #include <lemon/concepts/graph.h>
4.13 #include <lemon/dfs.h>
4.14 @@ -90,25 +94,69 @@
4.15 }
4.16 }
4.17
4.18 - enum MappingType {
4.19 + ///Graph mapping types.
4.20 +
4.21 + ///\ingroup graph_isomorphism
4.22 + ///The \ref Vf2 "VF2" algorithm is capable of finding different kind of
4.23 + ///embeddings, this enum specifies its type.
4.24 + ///
4.25 + ///See \ref graph_isomorphism for a more detailed description.
4.26 + enum Vf2MappingType {
4.27 + /// Subgraph isomorphism
4.28 SUBGRAPH = 0,
4.29 + /// Induced subgraph isomorphism
4.30 INDUCED = 1,
4.31 + /// Graph isomorphism
4.32 +
4.33 + /// If the two graph has the same number of nodes, than it is
4.34 + /// equivalent to \ref INDUCED, and if they also have the same
4.35 + /// number of edges, then it is also equivalent to \ref SUBGRAPH.
4.36 + ///
4.37 + /// However, using this setting is faster than the other two
4.38 + /// options.
4.39 ISOMORPH = 2
4.40 };
4.41
4.42 - template<class G1, class G2, class I, class NEq = bits::vf2::AlwaysEq >
4.43 + ///%VF2 algorithm class.
4.44 +
4.45 + ///\ingroup graph_isomorphism This class provides an efficient
4.46 + ///implementation of the %VF2 algorithm \cite cordella2004sub
4.47 + ///for variants of the (Sub)graph Isomorphism problem.
4.48 + ///
4.49 + ///There is also a \ref vf2() "function-type interface" called \ref vf2()
4.50 + ///for the %VF2 algorithm, which is probably more convenient in most
4.51 + ///use-cases.
4.52 + ///
4.53 + ///\tparam G1 The type of the graph to be embedded.
4.54 + ///The default type is \ref ListDigraph.
4.55 + ///\tparam G2 The type of the graph g1 will be embedded into.
4.56 + ///The default type is \ref ListDigraph.
4.57 + ///\tparam M The type of the NodeMap storing the mapping.
4.58 + ///By default, it is G1::NodeMap<G2::Node>
4.59 + ///\tparam NEQ A bool-valued binary functor determinining whether a node is
4.60 + ///mappable to another. By default it is an always true operator.
4.61 + ///
4.62 + ///\sa vf2()
4.63 +#ifdef DOXYGEN
4.64 + template<class G1, class G2, class M, class NEQ >
4.65 +#else
4.66 + template<class G1=ListDigraph,
4.67 + class G2=ListDigraph,
4.68 + class M = typename G1::template NodeMap<G2::Node>,
4.69 + class NEQ = bits::vf2::AlwaysEq >
4.70 +#endif
4.71 class Vf2
4.72 {
4.73 //Current depth in the DFS tree.
4.74 int _depth;
4.75 //Functor with bool operator()(G1::Node,G2::Node), which returns 1
4.76 //if and only if the 2 nodes are equivalent.
4.77 - NEq _nEq;
4.78 + NEQ _nEq;
4.79
4.80 typename G2::template NodeMap<int> _conn;
4.81 - //Current matching. We index it by the nodes of g1, and match[v] is
4.82 + //Current mapping. We index it by the nodes of g1, and match[v] is
4.83 //a node of g2.
4.84 - I &_match;
4.85 + M &_mapping;
4.86 //order[i] is the node of g1, for which we find a pair if depth=i
4.87 std::vector<typename G1::Node> order;
4.88 //currEdgeIts[i] is an edge iterator, witch is last used in the ith
4.89 @@ -121,10 +169,10 @@
4.90 //lookup tables for cut the searchtree
4.91 typename G1::template NodeMap<int> rNew1t,rInOut1t;
4.92
4.93 - MappingType _mapping_type;
4.94 + Vf2MappingType _mapping_type;
4.95
4.96 //cut the search tree
4.97 - template<MappingType MT>
4.98 + template<Vf2MappingType MT>
4.99 bool cut(const typename G1::Node n1,const typename G2::Node n2) const
4.100 {
4.101 int rNew2=0,rInOut2=0;
4.102 @@ -149,7 +197,7 @@
4.103 }
4.104 }
4.105
4.106 - template<MappingType MT>
4.107 + template<Vf2MappingType MT>
4.108 bool feas(const typename G1::Node n1,const typename G2::Node n2)
4.109 {
4.110 if(!_nEq(n1,n2))
4.111 @@ -158,8 +206,8 @@
4.112 for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1)
4.113 {
4.114 const typename G1::Node currNode=_g1.oppositeNode(n1,e1);
4.115 - if(_match[currNode]!=INVALID)
4.116 - --_conn[_match[currNode]];
4.117 + if(_mapping[currNode]!=INVALID)
4.118 + --_conn[_mapping[currNode]];
4.119 }
4.120 bool isIso=1;
4.121 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2)
4.122 @@ -177,7 +225,7 @@
4.123 for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1)
4.124 {
4.125 const typename G1::Node currNode=_g1.oppositeNode(n1,e1);
4.126 - if(_match[currNode]!=INVALID&&_conn[_match[currNode]]!=-1)
4.127 + if(_mapping[currNode]!=INVALID&&_conn[_mapping[currNode]]!=-1)
4.128 {
4.129 switch(MT)
4.130 {
4.131 @@ -186,11 +234,11 @@
4.132 isIso=0;
4.133 break;
4.134 case SUBGRAPH:
4.135 - if(_conn[_match[currNode]]<-1)
4.136 + if(_conn[_mapping[currNode]]<-1)
4.137 isIso=0;
4.138 break;
4.139 }
4.140 - _conn[_match[currNode]]=-1;
4.141 + _conn[_mapping[currNode]]=-1;
4.142 }
4.143 }
4.144 return isIso&&cut<MT>(n1,n2);
4.145 @@ -199,7 +247,7 @@
4.146 void addPair(const typename G1::Node n1,const typename G2::Node n2)
4.147 {
4.148 _conn[n2]=-1;
4.149 - _match.set(n1,n2);
4.150 + _mapping.set(n1,n2);
4.151 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2)
4.152 if(_conn[_g2.oppositeNode(n2,e2)]!=-1)
4.153 ++_conn[_g2.oppositeNode(n2,e2)];
4.154 @@ -208,7 +256,7 @@
4.155 void subPair(const typename G1::Node n1,const typename G2::Node n2)
4.156 {
4.157 _conn[n2]=0;
4.158 - _match.set(n1,INVALID);
4.159 + _mapping.set(n1,INVALID);
4.160 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2)
4.161 {
4.162 const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
4.163 @@ -231,9 +279,7 @@
4.164 bfs.run();
4.165 }
4.166
4.167 - public:
4.168 -
4.169 - template<MappingType MT>
4.170 + template<Vf2MappingType MT>
4.171 bool extMatch()
4.172 {
4.173 while(_depth>=0)
4.174 @@ -250,14 +296,14 @@
4.175 if(currEdgeIts[_depth]==INVALID)
4.176 {
4.177 typename G1::IncEdgeIt fstMatchedE(_g1,order[_depth]);
4.178 - //if _match[order[_depth]]!=INVALID, we dont use
4.179 + //if _mapping[order[_depth]]!=INVALID, we dont use
4.180 //fstMatchedE
4.181 - if(_match[order[_depth]]==INVALID)
4.182 + if(_mapping[order[_depth]]==INVALID)
4.183 for(; fstMatchedE!=INVALID &&
4.184 - _match[_g1.oppositeNode(order[_depth],
4.185 + _mapping[_g1.oppositeNode(order[_depth],
4.186 fstMatchedE)]==INVALID;
4.187 ++fstMatchedE) ; //find fstMatchedE
4.188 - if(fstMatchedE==INVALID||_match[order[_depth]]!=INVALID)
4.189 + if(fstMatchedE==INVALID||_mapping[order[_depth]]!=INVALID)
4.190 {
4.191 //We did not find an covered neighbour, this means
4.192 //the graph is not connected(or _depth==0). Every
4.193 @@ -268,10 +314,10 @@
4.194 //try(match[order[_depth]]!=INVALID)
4.195 typename G2::NodeIt n2(_g2);
4.196 //if its not the first try
4.197 - if(_match[order[_depth]]!=INVALID)
4.198 + if(_mapping[order[_depth]]!=INVALID)
4.199 {
4.200 - n2=++typename G2::NodeIt(_g2,_match[order[_depth]]);
4.201 - subPair(order[_depth],_match[order[_depth]]);
4.202 + n2=++typename G2::NodeIt(_g2,_mapping[order[_depth]]);
4.203 + subPair(order[_depth],_mapping[order[_depth]]);
4.204 }
4.205 for(; n2!=INVALID; ++n2)
4.206 if(MT!=SUBGRAPH&&_conn[n2]==0)
4.207 @@ -294,15 +340,16 @@
4.208 }
4.209 else
4.210 {
4.211 - currPNode=_match[_g1.oppositeNode(order[_depth],fstMatchedE)];
4.212 + currPNode=_mapping[_g1.oppositeNode(order[_depth],
4.213 + fstMatchedE)];
4.214 currEdgeIts[_depth]=typename G2::IncEdgeIt(_g2,currPNode);
4.215 }
4.216 }
4.217 else
4.218 {
4.219 - currPNode=_g2.oppositeNode(_match[order[_depth]],
4.220 + currPNode=_g2.oppositeNode(_mapping[order[_depth]],
4.221 currEdgeIts[_depth]);
4.222 - subPair(order[_depth],_match[order[_depth]]);
4.223 + subPair(order[_depth],_mapping[order[_depth]]);
4.224 ++currEdgeIts[_depth];
4.225 }
4.226 for(; currEdgeIts[_depth]!=INVALID; ++currEdgeIts[_depth])
4.227 @@ -345,8 +392,18 @@
4.228 }
4.229 }
4.230 public:
4.231 - Vf2(const G1 &g1, const G2 &g2,I &i, const NEq &nEq = NEq() ) :
4.232 - _nEq(nEq), _conn(g2,0), _match(i), order(countNodes(g1)),
4.233 + ///Constructor
4.234 +
4.235 + ///Constructor
4.236 +
4.237 + ///\param g1 The graph to be embedded into \e g2.
4.238 + ///\param g2 The graph \e g1 will be embedded into.
4.239 + ///\param m \ref concepts::ReadWriteMap "read-write" NodeMap
4.240 + ///storing the found mapping.
4.241 + ///\param neq A bool-valued binary functor determinining whether a node is
4.242 + ///mappable to another. By default it is an always true operator.
4.243 + Vf2(const G1 &g1, const G2 &g2,M &m, const NEQ &neq = NEQ() ) :
4.244 + _nEq(neq), _conn(g2,0), _mapping(m), order(countNodes(g1)),
4.245 currEdgeIts(countNodes(g1),INVALID), _g1(g1), _g2(g2), rNew1t(g1,0),
4.246 rInOut1t(g1,0), _mapping_type(SUBGRAPH)
4.247 {
4.248 @@ -355,9 +412,29 @@
4.249 setRNew1tRInOut1t();
4.250 }
4.251
4.252 - MappingType mappingType() const { return _mapping_type; }
4.253 - void mappingType(MappingType m_type) { _mapping_type = m_type; }
4.254 + ///Returns the current mapping type
4.255
4.256 + ///Returns the current mapping type
4.257 + ///
4.258 + Vf2MappingType mappingType() const { return _mapping_type; }
4.259 + ///Sets mapping type
4.260 +
4.261 + ///Sets mapping type.
4.262 + ///
4.263 + ///The mapping type is set to \ref SUBGRAPH by default.
4.264 + ///
4.265 + ///\sa See \ref for the possible values.
4.266 + void mappingType(Vf2MappingType m_type) { _mapping_type = m_type; }
4.267 +
4.268 + ///Find a mapping
4.269 +
4.270 + ///It finds a mapping between from g1 into g2 according to the mapping
4.271 + ///type set by \ref mappingType(Vf2MappingType) "mappingType()".
4.272 + ///
4.273 + ///By subsequent calls, it returns all possible mappings one-by-one.
4.274 + ///
4.275 + ///\retval true if a mapping is found.
4.276 + ///\retval false if there is no (more) mapping.
4.277 bool find()
4.278 {
4.279 switch(_mapping_type)
4.280 @@ -384,7 +461,7 @@
4.281 const G1 &_g1;
4.282 const G2 &_g2;
4.283
4.284 - MappingType _mapping_type;
4.285 + Vf2MappingType _mapping_type;
4.286
4.287 typedef typename G1::template NodeMap<typename G2::Node> Mapping;
4.288 bool _local_mapping;
4.289 @@ -401,6 +478,15 @@
4.290 : _g1(g1), _g2(g2), _mapping_type(SUBGRAPH), _local_mapping(true) {}
4.291 };
4.292
4.293 + /// Auxiliary class for the function-type interface of %VF2 algorithm.
4.294 +
4.295 + /// This auxiliary class implements the named parameters of
4.296 + /// \ref vf2() "function-type interface" of \ref Vf2 algorithm.
4.297 + ///
4.298 + /// \warning This class should only be used through the function \ref vf2().
4.299 + ///
4.300 + /// \tparam TR The traits class that defines various types used by the
4.301 + /// algorithm.
4.302 template<class TR>
4.303 class Vf2Wizard : public TR
4.304 {
4.305 @@ -418,7 +504,7 @@
4.306 using TR::_node_eq;
4.307
4.308 public:
4.309 - ///Copy constructor
4.310 + ///Constructor
4.311 Vf2Wizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {}
4.312
4.313 ///Copy constructor
4.314 @@ -457,6 +543,10 @@
4.315 ///
4.316 ///\ref named-templ-param "Named parameter" function for setting
4.317 ///the equivalence relation between the nodes.
4.318 + ///
4.319 + ///\param node_eq A bool-valued binary functor determinining
4.320 + ///whether a node is mappable to another. By default it is an
4.321 + ///always true operator.
4.322 template<class T>
4.323 Vf2Wizard< SetNodeEqBase<T> > nodeEq(const T &node_eq)
4.324 {
4.325 @@ -468,6 +558,11 @@
4.326 ///
4.327 ///\ref named-templ-param "Named parameter" function for setting
4.328 ///the node labels defining equivalence relation between them.
4.329 + ///
4.330 + ///\param m1 It is arbitrary \ref ReadMap "readable node map" of g1.
4.331 + ///\param m1 It is arbitrary \ref ReadMap "readable node map" of g2.
4.332 + ///
4.333 + ///The value type of these maps must be equal comparable.
4.334 template<class M1, class M2>
4.335 Vf2Wizard< SetNodeEqBase<bits::vf2::MapEq<M1,M2> > >
4.336 nodeLabels(const M1 &m1,const M2 &m2)
4.337 @@ -475,24 +570,49 @@
4.338 return nodeEq(bits::vf2::MapEq<M1,M2>(m1,m2));
4.339 }
4.340
4.341 - Vf2Wizard<Base> &mappingType(MappingType m_type)
4.342 + ///\brief \ref named-templ-param "Named parameter" for setting
4.343 + ///the mapping type.
4.344 + ///
4.345 + ///\ref named-templ-param "Named parameter" for setting
4.346 + ///the mapping type.
4.347 + ///
4.348 + ///The mapping type is set to \ref SUBGRAPH by default.
4.349 + ///
4.350 + ///\sa See \ref for the possible values.
4.351 + Vf2Wizard<Base> &mappingType(Vf2MappingType m_type)
4.352 {
4.353 _mapping_type = m_type;
4.354 return *this;
4.355 }
4.356
4.357 + ///\brief \ref named-templ-param "Named parameter" for setting
4.358 + ///the mapping type to \ref INDUCED.
4.359 + ///
4.360 + ///\ref named-templ-param "Named parameter" for setting
4.361 + ///the mapping type to \ref INDUCED.
4.362 Vf2Wizard<Base> &induced()
4.363 {
4.364 _mapping_type = INDUCED;
4.365 return *this;
4.366 }
4.367
4.368 + ///\brief \ref named-templ-param "Named parameter" for setting
4.369 + ///the mapping type to \ref ISOMORPH.
4.370 + ///
4.371 + ///\ref named-templ-param "Named parameter" for setting
4.372 + ///the mapping type to \ref ISOMORPH.
4.373 Vf2Wizard<Base> &iso()
4.374 {
4.375 _mapping_type = ISOMORPH;
4.376 return *this;
4.377 }
4.378
4.379 + ///Runs VF2 algorithm.
4.380 +
4.381 + ///This method runs VF2 algorithm.
4.382 + ///
4.383 + ///\retval true if a mapping is found.
4.384 + ///\retval false if there is no (more) mapping.
4.385 bool run()
4.386 {
4.387 if(Base::_local_mapping)
4.388 @@ -512,6 +632,26 @@
4.389 }
4.390 };
4.391
4.392 + ///Function-type interface for VF2 algorithm.
4.393 +
4.394 + /// \ingroup graph_isomorphism
4.395 + ///Function-type interface for VF2 algorithm \cite cordella2004sub.
4.396 + ///
4.397 + ///This function has several \ref named-func-param "named parameters"
4.398 + ///declared as the members of class \ref Vf2Wizard.
4.399 + ///The following examples show how to use these parameters.
4.400 + ///\code
4.401 + /// // Find an embedding of graph g into graph h
4.402 + /// ListGraph::NodeMap<ListGraph::Node> m(g);
4.403 + /// vf2(g,h).mapping(m).run();
4.404 + ///
4.405 + /// // Check whether graphs g and h are isomorphic
4.406 + /// bool is_iso = vf2(g,h).iso().run();
4.407 + ///\endcode
4.408 + ///\warning Don't forget to put the \ref Vf2Wizard::run() "run()"
4.409 + ///to the end of the expression.
4.410 + ///\sa Vf2Wizard
4.411 + ///\sa Vf2
4.412 template<class G1, class G2>
4.413 Vf2Wizard<Vf2WizardBase<G1,G2> > vf2(const G1 &g1, const G2 &g2)
4.414 {