[1350] | 1 | /* -*- mode: C++; indent-tabs-mode: nil; -*- |
---|
| 2 | * |
---|
| 3 | * This file is a part of LEMON, a generic C++ optimization library. |
---|
| 4 | * |
---|
| 5 | * Copyright (C) 2015 |
---|
| 6 | * EMAXA Kutato-fejleszto Kft. (EMAXA Research Ltd.) |
---|
| 7 | * |
---|
| 8 | * Permission to use, modify and distribute this software is granted |
---|
| 9 | * provided that this copyright notice appears in all copies. For |
---|
| 10 | * precise terms see the accompanying LICENSE file. |
---|
| 11 | * |
---|
| 12 | * This software is provided "AS IS" with no warranty of any kind, |
---|
| 13 | * express or implied, and with no claim as to its suitability for any |
---|
| 14 | * purpose. |
---|
| 15 | * |
---|
| 16 | */ |
---|
| 17 | |
---|
| 18 | #ifndef LEMON_VF2_H |
---|
| 19 | #define LEMON_VF2_H |
---|
| 20 | |
---|
[1351] | 21 | ///\ingroup graph_properties |
---|
| 22 | ///\file |
---|
| 23 | ///\brief VF2 algorithm \cite cordella2004sub. |
---|
| 24 | |
---|
[1350] | 25 | #include <lemon/core.h> |
---|
| 26 | #include <lemon/concepts/graph.h> |
---|
| 27 | #include <lemon/dfs.h> |
---|
| 28 | #include <lemon/bfs.h> |
---|
| 29 | #include <test/test_tools.h> |
---|
| 30 | |
---|
| 31 | #include <vector> |
---|
| 32 | #include <set> |
---|
| 33 | |
---|
| 34 | namespace lemon |
---|
| 35 | { |
---|
| 36 | namespace bits |
---|
| 37 | { |
---|
| 38 | namespace vf2 |
---|
| 39 | { |
---|
| 40 | class AlwaysEq |
---|
| 41 | { |
---|
| 42 | public: |
---|
| 43 | template<class T1, class T2> |
---|
| 44 | bool operator()(T1, T2) const |
---|
| 45 | { |
---|
| 46 | return true; |
---|
| 47 | } |
---|
| 48 | }; |
---|
| 49 | |
---|
| 50 | template<class M1, class M2> |
---|
| 51 | class MapEq |
---|
| 52 | { |
---|
| 53 | const M1 &_m1; |
---|
| 54 | const M2 &_m2; |
---|
| 55 | public: |
---|
| 56 | MapEq(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} |
---|
| 57 | bool operator()(typename M1::Key k1, typename M2::Key k2) const |
---|
| 58 | { |
---|
| 59 | return _m1[k1] == _m2[k2]; |
---|
| 60 | } |
---|
| 61 | }; |
---|
| 62 | |
---|
| 63 | template <class G> |
---|
| 64 | class DfsLeaveOrder : public DfsVisitor<G> |
---|
| 65 | { |
---|
| 66 | const G &_g; |
---|
| 67 | std::vector<typename G::Node> &_order; |
---|
| 68 | int i; |
---|
| 69 | public: |
---|
| 70 | DfsLeaveOrder(const G &g, std::vector<typename G::Node> &order) |
---|
| 71 | : i(countNodes(g)), _g(g), _order(order) |
---|
| 72 | {} |
---|
| 73 | void leave(const typename G::Node &node) |
---|
| 74 | { |
---|
| 75 | _order[--i]=node; |
---|
| 76 | } |
---|
| 77 | }; |
---|
| 78 | |
---|
| 79 | template <class G> |
---|
| 80 | class BfsLeaveOrder : public BfsVisitor<G> |
---|
| 81 | { |
---|
| 82 | int i; |
---|
| 83 | const G &_g; |
---|
| 84 | std::vector<typename G::Node> &_order; |
---|
| 85 | public: |
---|
| 86 | BfsLeaveOrder(const G &g, std::vector<typename G::Node> &order) |
---|
| 87 | : i(0), _g(g), _order(order) |
---|
| 88 | {} |
---|
| 89 | void process(const typename G::Node &node) |
---|
| 90 | { |
---|
| 91 | _order[i++]=node; |
---|
| 92 | } |
---|
| 93 | }; |
---|
| 94 | } |
---|
| 95 | } |
---|
| 96 | |
---|
[1351] | 97 | ///Graph mapping types. |
---|
| 98 | |
---|
| 99 | ///\ingroup graph_isomorphism |
---|
| 100 | ///The \ref Vf2 "VF2" algorithm is capable of finding different kind of |
---|
| 101 | ///embeddings, this enum specifies its type. |
---|
| 102 | /// |
---|
| 103 | ///See \ref graph_isomorphism for a more detailed description. |
---|
| 104 | enum Vf2MappingType { |
---|
| 105 | /// Subgraph isomorphism |
---|
[1350] | 106 | SUBGRAPH = 0, |
---|
[1351] | 107 | /// Induced subgraph isomorphism |
---|
[1350] | 108 | INDUCED = 1, |
---|
[1351] | 109 | /// Graph isomorphism |
---|
| 110 | |
---|
| 111 | /// If the two graph has the same number of nodes, than it is |
---|
| 112 | /// equivalent to \ref INDUCED, and if they also have the same |
---|
| 113 | /// number of edges, then it is also equivalent to \ref SUBGRAPH. |
---|
| 114 | /// |
---|
| 115 | /// However, using this setting is faster than the other two |
---|
| 116 | /// options. |
---|
[1350] | 117 | ISOMORPH = 2 |
---|
| 118 | }; |
---|
| 119 | |
---|
[1351] | 120 | ///%VF2 algorithm class. |
---|
| 121 | |
---|
| 122 | ///\ingroup graph_isomorphism This class provides an efficient |
---|
| 123 | ///implementation of the %VF2 algorithm \cite cordella2004sub |
---|
| 124 | ///for variants of the (Sub)graph Isomorphism problem. |
---|
| 125 | /// |
---|
| 126 | ///There is also a \ref vf2() "function-type interface" called \ref vf2() |
---|
| 127 | ///for the %VF2 algorithm, which is probably more convenient in most |
---|
| 128 | ///use-cases. |
---|
| 129 | /// |
---|
| 130 | ///\tparam G1 The type of the graph to be embedded. |
---|
| 131 | ///The default type is \ref ListDigraph. |
---|
| 132 | ///\tparam G2 The type of the graph g1 will be embedded into. |
---|
| 133 | ///The default type is \ref ListDigraph. |
---|
| 134 | ///\tparam M The type of the NodeMap storing the mapping. |
---|
| 135 | ///By default, it is G1::NodeMap<G2::Node> |
---|
| 136 | ///\tparam NEQ A bool-valued binary functor determinining whether a node is |
---|
| 137 | ///mappable to another. By default it is an always true operator. |
---|
| 138 | /// |
---|
| 139 | ///\sa vf2() |
---|
| 140 | #ifdef DOXYGEN |
---|
| 141 | template<class G1, class G2, class M, class NEQ > |
---|
| 142 | #else |
---|
| 143 | template<class G1=ListDigraph, |
---|
| 144 | class G2=ListDigraph, |
---|
| 145 | class M = typename G1::template NodeMap<G2::Node>, |
---|
| 146 | class NEQ = bits::vf2::AlwaysEq > |
---|
| 147 | #endif |
---|
[1350] | 148 | class Vf2 |
---|
| 149 | { |
---|
| 150 | //Current depth in the DFS tree. |
---|
| 151 | int _depth; |
---|
| 152 | //Functor with bool operator()(G1::Node,G2::Node), which returns 1 |
---|
| 153 | //if and only if the 2 nodes are equivalent. |
---|
[1351] | 154 | NEQ _nEq; |
---|
[1350] | 155 | |
---|
| 156 | typename G2::template NodeMap<int> _conn; |
---|
[1351] | 157 | //Current mapping. We index it by the nodes of g1, and match[v] is |
---|
[1350] | 158 | //a node of g2. |
---|
[1351] | 159 | M &_mapping; |
---|
[1350] | 160 | //order[i] is the node of g1, for which we find a pair if depth=i |
---|
| 161 | std::vector<typename G1::Node> order; |
---|
| 162 | //currEdgeIts[i] is an edge iterator, witch is last used in the ith |
---|
| 163 | //depth to find a pair for order[i]. |
---|
| 164 | std::vector<typename G2::IncEdgeIt> currEdgeIts; |
---|
| 165 | //The small graph. |
---|
| 166 | const G1 &_g1; |
---|
| 167 | //The big graph. |
---|
| 168 | const G2 &_g2; |
---|
| 169 | //lookup tables for cut the searchtree |
---|
| 170 | typename G1::template NodeMap<int> rNew1t,rInOut1t; |
---|
| 171 | |
---|
[1351] | 172 | Vf2MappingType _mapping_type; |
---|
[1350] | 173 | |
---|
| 174 | //cut the search tree |
---|
[1351] | 175 | template<Vf2MappingType MT> |
---|
[1350] | 176 | bool cut(const typename G1::Node n1,const typename G2::Node n2) const |
---|
| 177 | { |
---|
| 178 | int rNew2=0,rInOut2=0; |
---|
| 179 | for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) |
---|
| 180 | { |
---|
| 181 | const typename G2::Node currNode=_g2.oppositeNode(n2,e2); |
---|
| 182 | if(_conn[currNode]>0) |
---|
| 183 | ++rInOut2; |
---|
| 184 | else if(MT!=SUBGRAPH&&_conn[currNode]==0) |
---|
| 185 | ++rNew2; |
---|
| 186 | } |
---|
| 187 | switch(MT) |
---|
| 188 | { |
---|
| 189 | case INDUCED: |
---|
| 190 | return rInOut1t[n1]<=rInOut2&&rNew1t[n1]<=rNew2; |
---|
| 191 | case SUBGRAPH: |
---|
| 192 | return rInOut1t[n1]<=rInOut2; |
---|
| 193 | case ISOMORPH: |
---|
| 194 | return rInOut1t[n1]==rInOut2&&rNew1t[n1]==rNew2; |
---|
| 195 | default: |
---|
| 196 | return false; |
---|
| 197 | } |
---|
| 198 | } |
---|
| 199 | |
---|
[1351] | 200 | template<Vf2MappingType MT> |
---|
[1350] | 201 | bool feas(const typename G1::Node n1,const typename G2::Node n2) |
---|
| 202 | { |
---|
| 203 | if(!_nEq(n1,n2)) |
---|
| 204 | return 0; |
---|
| 205 | |
---|
| 206 | for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) |
---|
| 207 | { |
---|
| 208 | const typename G1::Node currNode=_g1.oppositeNode(n1,e1); |
---|
[1351] | 209 | if(_mapping[currNode]!=INVALID) |
---|
| 210 | --_conn[_mapping[currNode]]; |
---|
[1350] | 211 | } |
---|
| 212 | bool isIso=1; |
---|
| 213 | for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) |
---|
| 214 | { |
---|
| 215 | const typename G2::Node currNode=_g2.oppositeNode(n2,e2); |
---|
| 216 | if(_conn[currNode]<-1) |
---|
| 217 | ++_conn[currNode]; |
---|
| 218 | else if(MT!=SUBGRAPH&&_conn[currNode]==-1) |
---|
| 219 | { |
---|
| 220 | isIso=0; |
---|
| 221 | break; |
---|
| 222 | } |
---|
| 223 | } |
---|
| 224 | |
---|
| 225 | for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) |
---|
| 226 | { |
---|
| 227 | const typename G1::Node currNode=_g1.oppositeNode(n1,e1); |
---|
[1351] | 228 | if(_mapping[currNode]!=INVALID&&_conn[_mapping[currNode]]!=-1) |
---|
[1350] | 229 | { |
---|
| 230 | switch(MT) |
---|
| 231 | { |
---|
| 232 | case INDUCED: |
---|
| 233 | case ISOMORPH: |
---|
| 234 | isIso=0; |
---|
| 235 | break; |
---|
| 236 | case SUBGRAPH: |
---|
[1351] | 237 | if(_conn[_mapping[currNode]]<-1) |
---|
[1350] | 238 | isIso=0; |
---|
| 239 | break; |
---|
| 240 | } |
---|
[1351] | 241 | _conn[_mapping[currNode]]=-1; |
---|
[1350] | 242 | } |
---|
| 243 | } |
---|
| 244 | return isIso&&cut<MT>(n1,n2); |
---|
| 245 | } |
---|
| 246 | |
---|
| 247 | void addPair(const typename G1::Node n1,const typename G2::Node n2) |
---|
| 248 | { |
---|
| 249 | _conn[n2]=-1; |
---|
[1351] | 250 | _mapping.set(n1,n2); |
---|
[1350] | 251 | for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) |
---|
| 252 | if(_conn[_g2.oppositeNode(n2,e2)]!=-1) |
---|
| 253 | ++_conn[_g2.oppositeNode(n2,e2)]; |
---|
| 254 | } |
---|
| 255 | |
---|
| 256 | void subPair(const typename G1::Node n1,const typename G2::Node n2) |
---|
| 257 | { |
---|
| 258 | _conn[n2]=0; |
---|
[1351] | 259 | _mapping.set(n1,INVALID); |
---|
[1350] | 260 | for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) |
---|
| 261 | { |
---|
| 262 | const typename G2::Node currNode=_g2.oppositeNode(n2,e2); |
---|
| 263 | if(_conn[currNode]>0) |
---|
| 264 | --_conn[currNode]; |
---|
| 265 | else if(_conn[currNode]==-1) |
---|
| 266 | ++_conn[n2]; |
---|
| 267 | } |
---|
| 268 | } |
---|
| 269 | |
---|
| 270 | void setOrder()//we will find pairs for the nodes of g1 in this order |
---|
| 271 | { |
---|
| 272 | // bits::vf2::DfsLeaveOrder<G1> v(_g1,order); |
---|
| 273 | // DfsVisit<G1,bits::vf2::DfsLeaveOrder<G1> >dfs(_g1, v); |
---|
| 274 | // dfs.run(); |
---|
| 275 | |
---|
| 276 | //it is more efficient in practice than DFS |
---|
| 277 | bits::vf2::BfsLeaveOrder<G1> v(_g1,order); |
---|
| 278 | BfsVisit<G1,bits::vf2::BfsLeaveOrder<G1> >bfs(_g1, v); |
---|
| 279 | bfs.run(); |
---|
| 280 | } |
---|
| 281 | |
---|
[1351] | 282 | template<Vf2MappingType MT> |
---|
[1350] | 283 | bool extMatch() |
---|
| 284 | { |
---|
| 285 | while(_depth>=0) |
---|
| 286 | { |
---|
| 287 | //there are not nodes in g1, which has not pair in g2. |
---|
| 288 | if(_depth==static_cast<int>(order.size())) |
---|
| 289 | { |
---|
| 290 | --_depth; |
---|
| 291 | return true; |
---|
| 292 | } |
---|
| 293 | //the node of g2, which neighbours are the candidates for |
---|
| 294 | //the pair of order[_depth] |
---|
| 295 | typename G2::Node currPNode; |
---|
| 296 | if(currEdgeIts[_depth]==INVALID) |
---|
| 297 | { |
---|
| 298 | typename G1::IncEdgeIt fstMatchedE(_g1,order[_depth]); |
---|
[1351] | 299 | //if _mapping[order[_depth]]!=INVALID, we dont use |
---|
[1350] | 300 | //fstMatchedE |
---|
[1351] | 301 | if(_mapping[order[_depth]]==INVALID) |
---|
[1350] | 302 | for(; fstMatchedE!=INVALID && |
---|
[1351] | 303 | _mapping[_g1.oppositeNode(order[_depth], |
---|
[1350] | 304 | fstMatchedE)]==INVALID; |
---|
| 305 | ++fstMatchedE) ; //find fstMatchedE |
---|
[1351] | 306 | if(fstMatchedE==INVALID||_mapping[order[_depth]]!=INVALID) |
---|
[1350] | 307 | { |
---|
| 308 | //We did not find an covered neighbour, this means |
---|
| 309 | //the graph is not connected(or _depth==0). Every |
---|
| 310 | //uncovered(and there are some other properties due |
---|
| 311 | //to the spec. problem types) node of g2 is |
---|
| 312 | //candidate. We can read the iterator of the last |
---|
| 313 | //tryed node from the match if it is not the first |
---|
| 314 | //try(match[order[_depth]]!=INVALID) |
---|
| 315 | typename G2::NodeIt n2(_g2); |
---|
| 316 | //if its not the first try |
---|
[1351] | 317 | if(_mapping[order[_depth]]!=INVALID) |
---|
[1350] | 318 | { |
---|
[1351] | 319 | n2=++typename G2::NodeIt(_g2,_mapping[order[_depth]]); |
---|
| 320 | subPair(order[_depth],_mapping[order[_depth]]); |
---|
[1350] | 321 | } |
---|
| 322 | for(; n2!=INVALID; ++n2) |
---|
| 323 | if(MT!=SUBGRAPH&&_conn[n2]==0) |
---|
| 324 | { |
---|
| 325 | if(feas<MT>(order[_depth],n2)) |
---|
| 326 | break; |
---|
| 327 | } |
---|
| 328 | else if(MT==SUBGRAPH&&_conn[n2]>=0) |
---|
| 329 | if(feas<MT>(order[_depth],n2)) |
---|
| 330 | break; |
---|
| 331 | // n2 is the next candidate |
---|
| 332 | if(n2!=INVALID) |
---|
| 333 | { |
---|
| 334 | addPair(order[_depth],n2); |
---|
| 335 | ++_depth; |
---|
| 336 | } |
---|
| 337 | else // there is no more candidate |
---|
| 338 | --_depth; |
---|
| 339 | continue; |
---|
| 340 | } |
---|
| 341 | else |
---|
| 342 | { |
---|
[1351] | 343 | currPNode=_mapping[_g1.oppositeNode(order[_depth], |
---|
| 344 | fstMatchedE)]; |
---|
[1350] | 345 | currEdgeIts[_depth]=typename G2::IncEdgeIt(_g2,currPNode); |
---|
| 346 | } |
---|
| 347 | } |
---|
| 348 | else |
---|
| 349 | { |
---|
[1351] | 350 | currPNode=_g2.oppositeNode(_mapping[order[_depth]], |
---|
[1350] | 351 | currEdgeIts[_depth]); |
---|
[1351] | 352 | subPair(order[_depth],_mapping[order[_depth]]); |
---|
[1350] | 353 | ++currEdgeIts[_depth]; |
---|
| 354 | } |
---|
| 355 | for(; currEdgeIts[_depth]!=INVALID; ++currEdgeIts[_depth]) |
---|
| 356 | { |
---|
| 357 | const typename G2::Node currNode = |
---|
| 358 | _g2.oppositeNode(currPNode, currEdgeIts[_depth]); |
---|
| 359 | //if currNode is uncovered |
---|
| 360 | if(_conn[currNode]>0&&feas<MT>(order[_depth],currNode)) |
---|
| 361 | { |
---|
| 362 | addPair(order[_depth],currNode); |
---|
| 363 | break; |
---|
| 364 | } |
---|
| 365 | } |
---|
| 366 | currEdgeIts[_depth]==INVALID?--_depth:++_depth; |
---|
| 367 | } |
---|
| 368 | return false; |
---|
| 369 | } |
---|
| 370 | |
---|
| 371 | //calc. the lookup table for cut the searchtree |
---|
| 372 | void setRNew1tRInOut1t() |
---|
| 373 | { |
---|
| 374 | typename G1::template NodeMap<int> tmp(_g1,0); |
---|
| 375 | for(unsigned int i=0; i<order.size(); ++i) |
---|
| 376 | { |
---|
| 377 | tmp[order[i]]=-1; |
---|
| 378 | for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1) |
---|
| 379 | { |
---|
| 380 | const typename G1::Node currNode=_g1.oppositeNode(order[i],e1); |
---|
| 381 | if(tmp[currNode]>0) |
---|
| 382 | ++rInOut1t[order[i]]; |
---|
| 383 | else if(tmp[currNode]==0) |
---|
| 384 | ++rNew1t[order[i]]; |
---|
| 385 | } |
---|
| 386 | for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1) |
---|
| 387 | { |
---|
| 388 | const typename G1::Node currNode=_g1.oppositeNode(order[i],e1); |
---|
| 389 | if(tmp[currNode]!=-1) |
---|
| 390 | ++tmp[currNode]; |
---|
| 391 | } |
---|
| 392 | } |
---|
| 393 | } |
---|
| 394 | public: |
---|
[1351] | 395 | ///Constructor |
---|
| 396 | |
---|
| 397 | ///Constructor |
---|
| 398 | |
---|
| 399 | ///\param g1 The graph to be embedded into \e g2. |
---|
| 400 | ///\param g2 The graph \e g1 will be embedded into. |
---|
| 401 | ///\param m \ref concepts::ReadWriteMap "read-write" NodeMap |
---|
| 402 | ///storing the found mapping. |
---|
| 403 | ///\param neq A bool-valued binary functor determinining whether a node is |
---|
| 404 | ///mappable to another. By default it is an always true operator. |
---|
| 405 | Vf2(const G1 &g1, const G2 &g2,M &m, const NEQ &neq = NEQ() ) : |
---|
| 406 | _nEq(neq), _conn(g2,0), _mapping(m), order(countNodes(g1)), |
---|
[1350] | 407 | currEdgeIts(countNodes(g1),INVALID), _g1(g1), _g2(g2), rNew1t(g1,0), |
---|
| 408 | rInOut1t(g1,0), _mapping_type(SUBGRAPH) |
---|
| 409 | { |
---|
| 410 | _depth=0; |
---|
| 411 | setOrder(); |
---|
| 412 | setRNew1tRInOut1t(); |
---|
[1352] | 413 | for(typename G1::NodeIt n(g1);n!=INVALID;++n) |
---|
| 414 | m[n]=INVALID; |
---|
[1350] | 415 | } |
---|
| 416 | |
---|
[1351] | 417 | ///Returns the current mapping type |
---|
[1350] | 418 | |
---|
[1351] | 419 | ///Returns the current mapping type |
---|
| 420 | /// |
---|
| 421 | Vf2MappingType mappingType() const { return _mapping_type; } |
---|
| 422 | ///Sets mapping type |
---|
| 423 | |
---|
| 424 | ///Sets mapping type. |
---|
| 425 | /// |
---|
| 426 | ///The mapping type is set to \ref SUBGRAPH by default. |
---|
| 427 | /// |
---|
[1353] | 428 | ///\sa See \ref Vf2MappingType for the possible values. |
---|
[1351] | 429 | void mappingType(Vf2MappingType m_type) { _mapping_type = m_type; } |
---|
| 430 | |
---|
[1366] | 431 | ///Finds a mapping |
---|
[1351] | 432 | |
---|
| 433 | ///It finds a mapping between from g1 into g2 according to the mapping |
---|
| 434 | ///type set by \ref mappingType(Vf2MappingType) "mappingType()". |
---|
| 435 | /// |
---|
| 436 | ///By subsequent calls, it returns all possible mappings one-by-one. |
---|
| 437 | /// |
---|
| 438 | ///\retval true if a mapping is found. |
---|
| 439 | ///\retval false if there is no (more) mapping. |
---|
[1350] | 440 | bool find() |
---|
| 441 | { |
---|
| 442 | switch(_mapping_type) |
---|
| 443 | { |
---|
| 444 | case SUBGRAPH: |
---|
| 445 | return extMatch<SUBGRAPH>(); |
---|
| 446 | case INDUCED: |
---|
| 447 | return extMatch<INDUCED>(); |
---|
| 448 | case ISOMORPH: |
---|
| 449 | return extMatch<ISOMORPH>(); |
---|
| 450 | default: |
---|
| 451 | return false; |
---|
| 452 | } |
---|
| 453 | } |
---|
| 454 | }; |
---|
| 455 | |
---|
| 456 | template<class G1, class G2> |
---|
| 457 | class Vf2WizardBase |
---|
| 458 | { |
---|
| 459 | protected: |
---|
| 460 | typedef G1 Graph1; |
---|
| 461 | typedef G2 Graph2; |
---|
| 462 | |
---|
| 463 | const G1 &_g1; |
---|
| 464 | const G2 &_g2; |
---|
| 465 | |
---|
[1351] | 466 | Vf2MappingType _mapping_type; |
---|
[1350] | 467 | |
---|
| 468 | typedef typename G1::template NodeMap<typename G2::Node> Mapping; |
---|
| 469 | bool _local_mapping; |
---|
| 470 | void *_mapping; |
---|
| 471 | void createMapping() |
---|
| 472 | { |
---|
| 473 | _mapping = new Mapping(_g1); |
---|
| 474 | } |
---|
| 475 | |
---|
| 476 | typedef bits::vf2::AlwaysEq NodeEq; |
---|
| 477 | NodeEq _node_eq; |
---|
| 478 | |
---|
| 479 | Vf2WizardBase(const G1 &g1,const G2 &g2) |
---|
| 480 | : _g1(g1), _g2(g2), _mapping_type(SUBGRAPH), _local_mapping(true) {} |
---|
| 481 | }; |
---|
| 482 | |
---|
[1351] | 483 | /// Auxiliary class for the function-type interface of %VF2 algorithm. |
---|
| 484 | |
---|
| 485 | /// This auxiliary class implements the named parameters of |
---|
| 486 | /// \ref vf2() "function-type interface" of \ref Vf2 algorithm. |
---|
| 487 | /// |
---|
| 488 | /// \warning This class should only be used through the function \ref vf2(). |
---|
| 489 | /// |
---|
| 490 | /// \tparam TR The traits class that defines various types used by the |
---|
| 491 | /// algorithm. |
---|
[1350] | 492 | template<class TR> |
---|
| 493 | class Vf2Wizard : public TR |
---|
| 494 | { |
---|
| 495 | typedef TR Base; |
---|
| 496 | typedef typename TR::Graph1 Graph1; |
---|
| 497 | typedef typename TR::Graph2 Graph2; |
---|
| 498 | |
---|
| 499 | typedef typename TR::Mapping Mapping; |
---|
| 500 | typedef typename TR::NodeEq NodeEq; |
---|
| 501 | |
---|
| 502 | using TR::_g1; |
---|
| 503 | using TR::_g2; |
---|
| 504 | using TR::_mapping_type; |
---|
| 505 | using TR::_mapping; |
---|
| 506 | using TR::_node_eq; |
---|
| 507 | |
---|
| 508 | public: |
---|
[1351] | 509 | ///Constructor |
---|
[1350] | 510 | Vf2Wizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {} |
---|
| 511 | |
---|
| 512 | ///Copy constructor |
---|
| 513 | Vf2Wizard(const Base &b) : Base(b) {} |
---|
| 514 | |
---|
| 515 | |
---|
| 516 | template<class T> |
---|
| 517 | struct SetMappingBase : public Base { |
---|
| 518 | typedef T Mapping; |
---|
| 519 | SetMappingBase(const Base &b) : Base(b) {} |
---|
| 520 | }; |
---|
| 521 | |
---|
| 522 | ///\brief \ref named-templ-param "Named parameter" for setting |
---|
| 523 | ///the mapping. |
---|
| 524 | /// |
---|
| 525 | ///\ref named-templ-param "Named parameter" function for setting |
---|
| 526 | ///the map that stores the found embedding. |
---|
| 527 | template<class T> |
---|
| 528 | Vf2Wizard< SetMappingBase<T> > mapping(const T &t) |
---|
| 529 | { |
---|
| 530 | Base::_mapping=reinterpret_cast<void*>(const_cast<T*>(&t)); |
---|
| 531 | Base::_local_mapping = false; |
---|
| 532 | return Vf2Wizard<SetMappingBase<T> >(*this); |
---|
| 533 | } |
---|
| 534 | |
---|
| 535 | template<class NE> |
---|
| 536 | struct SetNodeEqBase : public Base { |
---|
| 537 | typedef NE NodeEq; |
---|
| 538 | NodeEq _node_eq; |
---|
| 539 | SetNodeEqBase(const Base &b, const NE &node_eq) |
---|
| 540 | : Base(b), _node_eq(node_eq) {} |
---|
| 541 | }; |
---|
| 542 | |
---|
| 543 | ///\brief \ref named-templ-param "Named parameter" for setting |
---|
| 544 | ///the node equivalence relation. |
---|
| 545 | /// |
---|
| 546 | ///\ref named-templ-param "Named parameter" function for setting |
---|
| 547 | ///the equivalence relation between the nodes. |
---|
[1351] | 548 | /// |
---|
| 549 | ///\param node_eq A bool-valued binary functor determinining |
---|
| 550 | ///whether a node is mappable to another. By default it is an |
---|
| 551 | ///always true operator. |
---|
[1350] | 552 | template<class T> |
---|
| 553 | Vf2Wizard< SetNodeEqBase<T> > nodeEq(const T &node_eq) |
---|
| 554 | { |
---|
| 555 | return Vf2Wizard<SetNodeEqBase<T> >(SetNodeEqBase<T>(*this,node_eq)); |
---|
| 556 | } |
---|
| 557 | |
---|
| 558 | ///\brief \ref named-templ-param "Named parameter" for setting |
---|
| 559 | ///the node labels. |
---|
| 560 | /// |
---|
| 561 | ///\ref named-templ-param "Named parameter" function for setting |
---|
| 562 | ///the node labels defining equivalence relation between them. |
---|
[1351] | 563 | /// |
---|
[1353] | 564 | ///\param m1 It is arbitrary \ref concepts::ReadMap "readable node map" |
---|
| 565 | ///of g1. |
---|
| 566 | ///\param m2 It is arbitrary \ref concepts::ReadMap "readable node map" |
---|
| 567 | ///of g2. |
---|
[1351] | 568 | /// |
---|
| 569 | ///The value type of these maps must be equal comparable. |
---|
[1350] | 570 | template<class M1, class M2> |
---|
| 571 | Vf2Wizard< SetNodeEqBase<bits::vf2::MapEq<M1,M2> > > |
---|
| 572 | nodeLabels(const M1 &m1,const M2 &m2) |
---|
| 573 | { |
---|
| 574 | return nodeEq(bits::vf2::MapEq<M1,M2>(m1,m2)); |
---|
| 575 | } |
---|
| 576 | |
---|
[1351] | 577 | ///\brief \ref named-templ-param "Named parameter" for setting |
---|
| 578 | ///the mapping type. |
---|
| 579 | /// |
---|
| 580 | ///\ref named-templ-param "Named parameter" for setting |
---|
| 581 | ///the mapping type. |
---|
| 582 | /// |
---|
| 583 | ///The mapping type is set to \ref SUBGRAPH by default. |
---|
| 584 | /// |
---|
[1353] | 585 | ///\sa See \ref Vf2MappingType for the possible values. |
---|
[1351] | 586 | Vf2Wizard<Base> &mappingType(Vf2MappingType m_type) |
---|
[1350] | 587 | { |
---|
| 588 | _mapping_type = m_type; |
---|
| 589 | return *this; |
---|
| 590 | } |
---|
| 591 | |
---|
[1351] | 592 | ///\brief \ref named-templ-param "Named parameter" for setting |
---|
| 593 | ///the mapping type to \ref INDUCED. |
---|
| 594 | /// |
---|
| 595 | ///\ref named-templ-param "Named parameter" for setting |
---|
| 596 | ///the mapping type to \ref INDUCED. |
---|
[1350] | 597 | Vf2Wizard<Base> &induced() |
---|
| 598 | { |
---|
| 599 | _mapping_type = INDUCED; |
---|
| 600 | return *this; |
---|
| 601 | } |
---|
| 602 | |
---|
[1351] | 603 | ///\brief \ref named-templ-param "Named parameter" for setting |
---|
| 604 | ///the mapping type to \ref ISOMORPH. |
---|
| 605 | /// |
---|
| 606 | ///\ref named-templ-param "Named parameter" for setting |
---|
| 607 | ///the mapping type to \ref ISOMORPH. |
---|
[1350] | 608 | Vf2Wizard<Base> &iso() |
---|
| 609 | { |
---|
| 610 | _mapping_type = ISOMORPH; |
---|
| 611 | return *this; |
---|
| 612 | } |
---|
| 613 | |
---|
[1351] | 614 | ///Runs VF2 algorithm. |
---|
| 615 | |
---|
| 616 | ///This method runs VF2 algorithm. |
---|
| 617 | /// |
---|
| 618 | ///\retval true if a mapping is found. |
---|
| 619 | ///\retval false if there is no (more) mapping. |
---|
[1350] | 620 | bool run() |
---|
| 621 | { |
---|
| 622 | if(Base::_local_mapping) |
---|
| 623 | Base::createMapping(); |
---|
| 624 | |
---|
| 625 | Vf2<Graph1, Graph2, Mapping, NodeEq > |
---|
| 626 | alg(_g1, _g2, *reinterpret_cast<Mapping*>(_mapping), _node_eq); |
---|
| 627 | |
---|
| 628 | alg.mappingType(_mapping_type); |
---|
| 629 | |
---|
| 630 | bool ret = alg.find(); |
---|
| 631 | |
---|
| 632 | if(Base::_local_mapping) |
---|
| 633 | delete reinterpret_cast<Mapping*>(_mapping); |
---|
| 634 | |
---|
| 635 | return ret; |
---|
| 636 | } |
---|
| 637 | }; |
---|
| 638 | |
---|
[1351] | 639 | ///Function-type interface for VF2 algorithm. |
---|
| 640 | |
---|
| 641 | /// \ingroup graph_isomorphism |
---|
| 642 | ///Function-type interface for VF2 algorithm \cite cordella2004sub. |
---|
| 643 | /// |
---|
| 644 | ///This function has several \ref named-func-param "named parameters" |
---|
| 645 | ///declared as the members of class \ref Vf2Wizard. |
---|
| 646 | ///The following examples show how to use these parameters. |
---|
| 647 | ///\code |
---|
| 648 | /// // Find an embedding of graph g into graph h |
---|
| 649 | /// ListGraph::NodeMap<ListGraph::Node> m(g); |
---|
| 650 | /// vf2(g,h).mapping(m).run(); |
---|
| 651 | /// |
---|
| 652 | /// // Check whether graphs g and h are isomorphic |
---|
| 653 | /// bool is_iso = vf2(g,h).iso().run(); |
---|
| 654 | ///\endcode |
---|
| 655 | ///\warning Don't forget to put the \ref Vf2Wizard::run() "run()" |
---|
| 656 | ///to the end of the expression. |
---|
| 657 | ///\sa Vf2Wizard |
---|
| 658 | ///\sa Vf2 |
---|
[1350] | 659 | template<class G1, class G2> |
---|
| 660 | Vf2Wizard<Vf2WizardBase<G1,G2> > vf2(const G1 &g1, const G2 &g2) |
---|
| 661 | { |
---|
| 662 | return Vf2Wizard<Vf2WizardBase<G1,G2> >(g1,g2); |
---|
| 663 | } |
---|
| 664 | |
---|
| 665 | } |
---|
| 666 | |
---|
| 667 | #endif |
---|