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