Changeset 1405:3feba0ea1bda in lemon
 Timestamp:
 09/19/17 14:08:20 (5 years ago)
 Branch:
 default
 Phase:
 public
 Files:

 3 added
 3 edited
Legend:
 Unmodified
 Added
 Removed

lemon/vf2.h
r1370 r1405 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2015 5 * Copyright (C) 20152017 6 6 * EMAXA Kutatofejleszto Kft. (EMAXA Research Ltd.) 7 7 * … … 27 27 #include <lemon/dfs.h> 28 28 #include <lemon/bfs.h> 29 #include <lemon/bits/vf2_internals.h> 29 30 30 31 #include <vector> 31 #include <set> 32 33 namespace lemon 34 { 35 namespace bits 36 { 37 namespace vf2 38 { 39 class AlwaysEq 40 { 32 33 namespace lemon { 34 namespace bits { 35 namespace vf2 { 36 37 class AlwaysEq { 41 38 public: 42 39 template<class T1, class T2> 43 bool operator()(T1, T2) const 44 { 40 bool operator()(T1&, T2&) const { 45 41 return true; 46 42 } … … 48 44 49 45 template<class M1, class M2> 50 class MapEq 51 { 46 class MapEq{ 52 47 const M1 &_m1; 53 48 const M2 &_m2; 54 49 public: 55 MapEq(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} 56 bool operator()(typename M1::Key k1, typename M2::Key k2) const 57 { 50 MapEq(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) { } 51 bool operator()(typename M1::Key k1, typename M2::Key k2) const { 58 52 return _m1[k1] == _m2[k2]; 59 53 } 60 54 }; 61 55 56 57 62 58 template <class G> 63 class DfsLeaveOrder : public DfsVisitor<G> 64 { 59 class DfsLeaveOrder : public DfsVisitor<G> { 65 60 const G &_g; 66 61 std::vector<typename G::Node> &_order; … … 68 63 public: 69 64 DfsLeaveOrder(const G &g, std::vector<typename G::Node> &order) 70 : i(countNodes(g)), _g(g), _order(order) 71 {} 72 void leave(const typename G::Node &node) 73 { 65 : i(countNodes(g)), _g(g), _order(order) { } 66 void leave(const typename G::Node &node) { 74 67 _order[i]=node; 75 68 } … … 77 70 78 71 template <class G> 79 class BfsLeaveOrder : public BfsVisitor<G> 80 { 72 class BfsLeaveOrder : public BfsVisitor<G> { 81 73 int i; 82 74 const G &_g; … … 84 76 public: 85 77 BfsLeaveOrder(const G &g, std::vector<typename G::Node> &order) 86 : i(0), _g(g), _order(order) 87 {} 88 void process(const typename G::Node &node) 89 { 78 : i(0), _g(g), _order(order){ 79 } 80 void process(const typename G::Node &node) { 90 81 _order[i++]=node; 91 82 } … … 94 85 } 95 86 96 ///Graph mapping types.97 98 ///\ingroup graph_isomorphism99 ///The \ref Vf2 "VF2" algorithm is capable of finding different kind of100 ///embeddings, this enum specifies its type.101 ///102 ///See \ref graph_isomorphism for a more detailed description.103 enum Vf2MappingType {104 /// Subgraph isomorphism105 SUBGRAPH = 0,106 /// Induced subgraph isomorphism107 INDUCED = 1,108 /// Graph isomorphism109 110 /// If the two graph has the same number of nodes, than it is111 /// equivalent to \ref INDUCED, and if they also have the same112 /// number of edges, then it is also equivalent to \ref SUBGRAPH.113 ///114 /// However, using this setting is faster than the other two115 /// options.116 ISOMORPH = 2117 };118 87 119 88 ///%VF2 algorithm class. … … 145 114 class NEQ = bits::vf2::AlwaysEq > 146 115 #endif 147 class Vf2 148 { 116 class Vf2 { 149 117 //Current depth in the DFS tree. 150 118 int _depth; 151 119 //Functor with bool operator()(G1::Node,G2::Node), which returns 1 152 //if and only if the 2nodes are equivalent.120 //ifff the two nodes are equivalent. 153 121 NEQ _nEq; 154 122 … … 157 125 //a node of g2. 158 126 M &_mapping; 159 //order[i] is the node of g1, for which we finda pair if depth=i127 //order[i] is the node of g1, for which we search a pair if depth=i 160 128 std::vector<typename G1::Node> order; 161 129 //currEdgeIts[i] is an edge iterator, witch is last used in the ith … … 164 132 //The small graph. 165 133 const G1 &_g1; 166 //The biggraph.134 //The large graph. 167 135 const G2 &_g2; 168 //lookup tables for cut the searchtree136 //lookup tables for cutting the searchtree 169 137 typename G1::template NodeMap<int> rNew1t,rInOut1t; 170 138 171 Vf2MappingType _mapping_type; 139 MappingType _mapping_type; 140 141 bool _deallocMappingAfterUse; 172 142 173 143 //cut the search tree 174 template<Vf2MappingType MT> 175 bool cut(const typename G1::Node n1,const typename G2::Node n2) const 176 { 144 template<MappingType MT> 145 bool cut(const typename G1::Node n1,const typename G2::Node n2) const { 177 146 int rNew2=0,rInOut2=0; 178 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) 179 { 180 const typename G2::Node currNode=_g2.oppositeNode(n2,e2); 181 if(_conn[currNode]>0) 182 ++rInOut2; 183 else if(MT!=SUBGRAPH&&_conn[currNode]==0) 184 ++rNew2; 185 } 186 switch(MT) 187 { 188 case INDUCED: 189 return rInOut1t[n1]<=rInOut2&&rNew1t[n1]<=rNew2; 190 case SUBGRAPH: 191 return rInOut1t[n1]<=rInOut2; 192 case ISOMORPH: 193 return rInOut1t[n1]==rInOut2&&rNew1t[n1]==rNew2; 194 default: 195 return false; 196 } 197 } 198 199 template<Vf2MappingType MT> 200 bool feas(const typename G1::Node n1,const typename G2::Node n2) 201 { 147 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) { 148 const typename G2::Node currNode=_g2.oppositeNode(n2,e2); 149 if(_conn[currNode]>0) 150 ++rInOut2; 151 else if(MT!=SUBGRAPH&&_conn[currNode]==0) 152 ++rNew2; 153 } 154 switch(MT) { 155 case INDUCED: 156 return rInOut1t[n1]<=rInOut2&&rNew1t[n1]<=rNew2; 157 case SUBGRAPH: 158 return rInOut1t[n1]<=rInOut2; 159 case ISOMORPH: 160 return rInOut1t[n1]==rInOut2&&rNew1t[n1]==rNew2; 161 default: 162 return false; 163 } 164 } 165 166 template<MappingType MT> 167 bool feas(const typename G1::Node n1,const typename G2::Node n2) { 202 168 if(!_nEq(n1,n2)) 203 169 return 0; 204 170 205 for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) 206 { 207 const typename G1::Node currNode=_g1.oppositeNode(n1,e1); 208 if(_mapping[currNode]!=INVALID) 209 _conn[_mapping[currNode]]; 210 } 171 for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) { 172 const typename G1::Node& currNode=_g1.oppositeNode(n1,e1); 173 if(_mapping[currNode]!=INVALID) 174 _conn[_mapping[currNode]]; 175 } 211 176 bool isIso=1; 212 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) 213 { 214 const typename G2::Node currNode=_g2.oppositeNode(n2,e2); 215 if(_conn[currNode]<1) 216 ++_conn[currNode]; 217 else if(MT!=SUBGRAPH&&_conn[currNode]==1) 218 { 177 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) { 178 int& connCurrNode = _conn[_g2.oppositeNode(n2,e2)]; 179 if(connCurrNode<1) 180 ++connCurrNode; 181 else if(MT!=SUBGRAPH&&connCurrNode==1) { 182 isIso=0; 183 break; 184 } 185 } 186 187 for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) { 188 const typename G2::Node& currNodePair=_mapping[_g1.oppositeNode(n1,e1)]; 189 int& connCurrNodePair=_conn[currNodePair]; 190 if(currNodePair!=INVALID&&connCurrNodePair!=1) { 191 switch(MT) { 192 case INDUCED: 193 case ISOMORPH: 194 isIso=0; 195 break; 196 case SUBGRAPH: 197 if(connCurrNodePair<1) 219 198 isIso=0; 220 break; 221 } 222 } 223 224 for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) 225 { 226 const typename G1::Node currNode=_g1.oppositeNode(n1,e1); 227 if(_mapping[currNode]!=INVALID&&_conn[_mapping[currNode]]!=1) 228 { 229 switch(MT) 230 { 231 case INDUCED: 232 case ISOMORPH: 233 isIso=0; 234 break; 235 case SUBGRAPH: 236 if(_conn[_mapping[currNode]]<1) 237 isIso=0; 238 break; 239 } 240 _conn[_mapping[currNode]]=1; 241 } 242 } 199 break; 200 } 201 connCurrNodePair=1; 202 } 203 } 243 204 return isIso&&cut<MT>(n1,n2); 244 205 } 245 206 246 void addPair(const typename G1::Node n1,const typename G2::Node n2) 247 { 207 void addPair(const typename G1::Node n1,const typename G2::Node n2) { 248 208 _conn[n2]=1; 249 209 _mapping.set(n1,n2); 250 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) 251 if(_conn[_g2.oppositeNode(n2,e2)]!=1) 252 ++_conn[_g2.oppositeNode(n2,e2)]; 253 } 254 255 void subPair(const typename G1::Node n1,const typename G2::Node n2) 256 { 210 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) { 211 int& currConn = _conn[_g2.oppositeNode(n2,e2)]; 212 if(currConn!=1) 213 ++currConn; 214 } 215 } 216 217 void subPair(const typename G1::Node n1,const typename G2::Node n2) { 257 218 _conn[n2]=0; 258 219 _mapping.set(n1,INVALID); 259 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) 260 {261 const typename G2::Node currNode=_g2.oppositeNode(n2,e2);262 if(_conn[currNode]>0)263 _conn[currNode];264 else if(_conn[currNode]==1)265 ++_conn[n2];266 267 } 268 269 void setOrder()//we will find pairs for the nodes of g1 in this order270 { 220 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) { 221 int& currConn = _conn[_g2.oppositeNode(n2,e2)]; 222 if(currConn>0) 223 currConn; 224 else if(currConn==1) 225 ++_conn[n2]; 226 } 227 } 228 229 void setOrder() { 230 // we will find pairs for the nodes of g1 in this order 231 271 232 // bits::vf2::DfsLeaveOrder<G1> v(_g1,order); 272 233 // DfsVisit<G1,bits::vf2::DfsLeaveOrder<G1> >dfs(_g1, v); … … 279 240 } 280 241 281 template<Vf2MappingType MT> 282 bool extMatch() 283 { 284 while(_depth>=0) 285 { 286 //there are not nodes in g1, which has not pair in g2. 287 if(_depth==static_cast<int>(order.size())) 288 { 242 template<MappingType MT> 243 bool extMatch() { 244 while(_depth>=0) { 245 //there are not nodes in g1, which has not pair in g2. 246 if(_depth==static_cast<int>(order.size())) { 247 _depth; 248 return true; 249 } 250 typename G1::Node& nodeOfDepth = order[_depth]; 251 const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth]; 252 typename G2::IncEdgeIt &edgeItOfDepth = currEdgeIts[_depth]; 253 //the node of g2, which neighbours are the candidates for 254 //the pair of nodeOfDepth 255 typename G2::Node currPNode; 256 if(edgeItOfDepth==INVALID) { 257 typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth); 258 //if pairOfNodeOfDepth!=INVALID, we dont use 259 //fstMatchedE 260 if(pairOfNodeOfDepth==INVALID) 261 for(; fstMatchedE!=INVALID && 262 _mapping[_g1.oppositeNode(nodeOfDepth, 263 fstMatchedE)]==INVALID; 264 ++fstMatchedE) ; //find fstMatchedE 265 if(fstMatchedE==INVALIDpairOfNodeOfDepth!=INVALID) { 266 //We found no covered neighbours, this means 267 //the graph is not connected(or _depth==0). Each 268 //uncovered(and there are some other properties due 269 //to the spec. problem types) node of g2 is 270 //candidate. We can read the iterator of the last 271 //tried node from the match if it is not the first 272 //try(match[nodeOfDepth]!=INVALID) 273 typename G2::NodeIt n2(_g2); 274 //if it's not the first try 275 if(pairOfNodeOfDepth!=INVALID) { 276 n2=++typename G2::NodeIt(_g2,pairOfNodeOfDepth); 277 subPair(nodeOfDepth,pairOfNodeOfDepth); 278 } 279 for(; n2!=INVALID; ++n2) 280 if(MT!=SUBGRAPH) { 281 if(_conn[n2]==0&&feas<MT>(nodeOfDepth,n2)) 282 break; 283 } 284 else if(_conn[n2]>=0&&feas<MT>(nodeOfDepth,n2)) 285 break; 286 // n2 is the next candidate 287 if(n2!=INVALID){ 288 addPair(nodeOfDepth,n2); 289 ++_depth; 290 } 291 else // there are no more candidates 289 292 _depth; 290 return true; 291 } 292 //the node of g2, which neighbours are the candidates for 293 //the pair of order[_depth] 294 typename G2::Node currPNode; 295 if(currEdgeIts[_depth]==INVALID) 296 { 297 typename G1::IncEdgeIt fstMatchedE(_g1,order[_depth]); 298 //if _mapping[order[_depth]]!=INVALID, we dont use 299 //fstMatchedE 300 if(_mapping[order[_depth]]==INVALID) 301 for(; fstMatchedE!=INVALID && 302 _mapping[_g1.oppositeNode(order[_depth], 303 fstMatchedE)]==INVALID; 304 ++fstMatchedE) ; //find fstMatchedE 305 if(fstMatchedE==INVALID_mapping[order[_depth]]!=INVALID) 306 { 307 //We did not find an covered neighbour, this means 308 //the graph is not connected(or _depth==0). Every 309 //uncovered(and there are some other properties due 310 //to the spec. problem types) node of g2 is 311 //candidate. We can read the iterator of the last 312 //tryed node from the match if it is not the first 313 //try(match[order[_depth]]!=INVALID) 314 typename G2::NodeIt n2(_g2); 315 //if its not the first try 316 if(_mapping[order[_depth]]!=INVALID) 317 { 318 n2=++typename G2::NodeIt(_g2,_mapping[order[_depth]]); 319 subPair(order[_depth],_mapping[order[_depth]]); 320 } 321 for(; n2!=INVALID; ++n2) 322 if(MT!=SUBGRAPH&&_conn[n2]==0) 323 { 324 if(feas<MT>(order[_depth],n2)) 325 break; 326 } 327 else if(MT==SUBGRAPH&&_conn[n2]>=0) 328 if(feas<MT>(order[_depth],n2)) 329 break; 330 // n2 is the next candidate 331 if(n2!=INVALID) 332 { 333 addPair(order[_depth],n2); 334 ++_depth; 335 } 336 else // there is no more candidate 337 _depth; 338 continue; 339 } 340 else 341 { 342 currPNode=_mapping[_g1.oppositeNode(order[_depth], 343 fstMatchedE)]; 344 currEdgeIts[_depth]=typename G2::IncEdgeIt(_g2,currPNode); 345 } 346 } 347 else 348 { 349 currPNode=_g2.oppositeNode(_mapping[order[_depth]], 350 currEdgeIts[_depth]); 351 subPair(order[_depth],_mapping[order[_depth]]); 352 ++currEdgeIts[_depth]; 353 } 354 for(; currEdgeIts[_depth]!=INVALID; ++currEdgeIts[_depth]) 355 { 356 const typename G2::Node currNode = 357 _g2.oppositeNode(currPNode, currEdgeIts[_depth]); 358 //if currNode is uncovered 359 if(_conn[currNode]>0&&feas<MT>(order[_depth],currNode)) 360 { 361 addPair(order[_depth],currNode); 362 break; 363 } 364 } 365 currEdgeIts[_depth]==INVALID?_depth:++_depth; 366 } 293 continue; 294 } 295 else { 296 currPNode=_mapping[_g1.oppositeNode(nodeOfDepth, 297 fstMatchedE)]; 298 edgeItOfDepth=typename G2::IncEdgeIt(_g2,currPNode); 299 } 300 } 301 else { 302 currPNode=_g2.oppositeNode(pairOfNodeOfDepth, 303 edgeItOfDepth); 304 subPair(nodeOfDepth,pairOfNodeOfDepth); 305 ++edgeItOfDepth; 306 } 307 for(; edgeItOfDepth!=INVALID; ++edgeItOfDepth) { 308 const typename G2::Node currNode = 309 _g2.oppositeNode(currPNode, edgeItOfDepth); 310 if(_conn[currNode]>0&&feas<MT>(nodeOfDepth,currNode)) { 311 addPair(nodeOfDepth,currNode); 312 break; 313 } 314 } 315 edgeItOfDepth==INVALID?_depth:++_depth; 316 } 367 317 return false; 368 318 } 369 319 370 320 //calc. the lookup table for cut the searchtree 371 void setRNew1tRInOut1t() 372 { 321 void setRNew1tRInOut1t() { 373 322 typename G1::template NodeMap<int> tmp(_g1,0); 374 for(unsigned int i=0; i<order.size(); ++i) 375 { 376 tmp[order[i]]=1; 377 for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1) 378 { 379 const typename G1::Node currNode=_g1.oppositeNode(order[i],e1); 380 if(tmp[currNode]>0) 381 ++rInOut1t[order[i]]; 382 else if(tmp[currNode]==0) 383 ++rNew1t[order[i]]; 384 } 385 for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1) 386 { 387 const typename G1::Node currNode=_g1.oppositeNode(order[i],e1); 388 if(tmp[currNode]!=1) 389 ++tmp[currNode]; 390 } 391 } 323 for(unsigned int i=0; i<order.size(); ++i) { 324 const typename G1::Node& orderI = order[i]; 325 tmp[orderI]=1; 326 for(typename G1::IncEdgeIt e1(_g1,orderI); e1!=INVALID; ++e1) { 327 const typename G1::Node currNode=_g1.oppositeNode(orderI,e1); 328 if(tmp[currNode]>0) 329 ++rInOut1t[orderI]; 330 else if(tmp[currNode]==0) 331 ++rNew1t[orderI]; 332 } 333 for(typename G1::IncEdgeIt e1(_g1,orderI); e1!=INVALID; ++e1) { 334 const typename G1::Node currNode=_g1.oppositeNode(orderI,e1); 335 if(tmp[currNode]!=1) 336 ++tmp[currNode]; 337 } 338 } 392 339 } 393 340 public: … … 400 347 ///\param m \ref concepts::ReadWriteMap "readwrite" NodeMap 401 348 ///storing the found mapping. 402 ///\param neq A boolvalued binary functor determinin ing whether a node is349 ///\param neq A boolvalued binary functor determining whether a node is 403 350 ///mappable to another. By default it is an always true operator. 404 Vf2(const G1 &g1, const G2 &g2, M &m, const NEQ &neq = NEQ() ) :351 Vf2(const G1 &g1, const G2 &g2, M &m, const NEQ &neq = NEQ() ) : 405 352 _nEq(neq), _conn(g2,0), _mapping(m), order(countNodes(g1)), 406 353 currEdgeIts(countNodes(g1),INVALID), _g1(g1), _g2(g2), rNew1t(g1,0), 407 rInOut1t(g1,0), _mapping_type(SUBGRAPH) 408 { 354 rInOut1t(g1,0), _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0) { 409 355 _depth=0; 410 356 setOrder(); … … 414 360 } 415 361 362 ///Destructor 363 364 ///Destructor. 365 /// 366 367 ~Vf2(){ 368 if(_deallocMappingAfterUse) 369 delete &_mapping; 370 } 371 416 372 ///Returns the current mapping type 417 373 418 374 ///Returns the current mapping type 419 375 /// 420 Vf2MappingType mappingType() const { return _mapping_type; } 376 MappingType mappingType() const { 377 return _mapping_type; 378 } 421 379 ///Sets mapping type 422 380 … … 425 383 ///The mapping type is set to \ref SUBGRAPH by default. 426 384 /// 427 ///\sa See \ref Vf2MappingType for the possible values. 428 void mappingType(Vf2MappingType m_type) { _mapping_type = m_type; } 385 ///\sa See \ref MappingType for the possible values. 386 void mappingType(MappingType m_type) { 387 _mapping_type = m_type; 388 } 429 389 430 390 ///Finds a mapping 431 391 432 ///It finds a mapping betweenfrom g1 into g2 according to the mapping433 ///type set by \ref mappingType( Vf2MappingType) "mappingType()".392 ///It finds a mapping from g1 into g2 according to the mapping 393 ///type set by \ref mappingType(MappingType) "mappingType()". 434 394 /// 435 395 ///By subsequent calls, it returns all possible mappings onebyone. … … 437 397 ///\retval true if a mapping is found. 438 398 ///\retval false if there is no (more) mapping. 439 bool find() 440 { 441 switch(_mapping_type) 442 { 443 case SUBGRAPH: 444 return extMatch<SUBGRAPH>(); 445 case INDUCED: 446 return extMatch<INDUCED>(); 447 case ISOMORPH: 448 return extMatch<ISOMORPH>(); 449 default: 450 return false; 451 } 399 bool find() { 400 switch(_mapping_type) { 401 case SUBGRAPH: 402 return extMatch<SUBGRAPH>(); 403 case INDUCED: 404 return extMatch<INDUCED>(); 405 case ISOMORPH: 406 return extMatch<ISOMORPH>(); 407 default: 408 return false; 409 } 452 410 } 453 411 }; 454 412 455 413 template<class G1, class G2> 456 class Vf2WizardBase 457 { 414 class Vf2WizardBase { 458 415 protected: 459 416 typedef G1 Graph1; … … 463 420 const G2 &_g2; 464 421 465 Vf2MappingType _mapping_type;422 MappingType _mapping_type; 466 423 467 424 typedef typename G1::template NodeMap<typename G2::Node> Mapping; 468 425 bool _local_mapping; 469 426 void *_mapping; 470 void createMapping() 471 { 427 void createMapping() { 472 428 _mapping = new Mapping(_g1); 473 429 } 430 431 void *myVf2; //used in Vf2Wizard::find 432 474 433 475 434 typedef bits::vf2::AlwaysEq NodeEq; … … 477 436 478 437 Vf2WizardBase(const G1 &g1,const G2 &g2) 479 : _g1(g1), _g2(g2), _mapping_type(SUBGRAPH), _local_mapping(true) { }438 : _g1(g1), _g2(g2), _mapping_type(SUBGRAPH), _local_mapping(true) { } 480 439 }; 440 481 441 482 442 /// Auxiliary class for the functiontype interface of %VF2 algorithm. … … 490 450 /// algorithm. 491 451 template<class TR> 492 class Vf2Wizard : public TR 493 { 452 class Vf2Wizard : public TR { 494 453 typedef TR Base; 495 454 typedef typename TR::Graph1 Graph1; … … 507 466 public: 508 467 ///Constructor 509 Vf2Wizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {} 468 Vf2Wizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) { 469 } 510 470 511 471 ///Copy constructor 512 Vf2Wizard(const Base &b) : Base(b) {} 472 Vf2Wizard(const Base &b) : Base(b) { } 473 474 ///Copy constructor 475 Vf2Wizard(const Vf2Wizard &b) : Base(b) {} 513 476 514 477 515 478 template<class T> 516 struct SetMappingBase : public Base 479 struct SetMappingBase : public Base{ 517 480 typedef T Mapping; 518 481 SetMappingBase(const Base &b) : Base(b) {} … … 525 488 ///the map that stores the found embedding. 526 489 template<class T> 527 Vf2Wizard< SetMappingBase<T> > mapping(const T &t) 528 { 490 Vf2Wizard< SetMappingBase<T> > mapping(const T &t) { 529 491 Base::_mapping=reinterpret_cast<void*>(const_cast<T*>(&t)); 530 492 Base::_local_mapping = false; … … 537 499 NodeEq _node_eq; 538 500 SetNodeEqBase(const Base &b, const NE &node_eq) 539 : Base(b), _node_eq(node_eq) {} 501 : Base(b), _node_eq(node_eq){ 502 } 540 503 }; 541 504 … … 550 513 ///always true operator. 551 514 template<class T> 552 Vf2Wizard< SetNodeEqBase<T> > nodeEq(const T &node_eq) 553 { 515 Vf2Wizard< SetNodeEqBase<T> > nodeEq(const T &node_eq) { 554 516 return Vf2Wizard<SetNodeEqBase<T> >(SetNodeEqBase<T>(*this,node_eq)); 555 517 } … … 561 523 ///the node labels defining equivalence relation between them. 562 524 /// 563 ///\param m1 It isarbitrary \ref concepts::ReadMap "readable node map"525 ///\param m1 An arbitrary \ref concepts::ReadMap "readable node map" 564 526 ///of g1. 565 ///\param m2 It isarbitrary \ref concepts::ReadMap "readable node map"527 ///\param m2 An arbitrary \ref concepts::ReadMap "readable node map" 566 528 ///of g2. 567 529 /// … … 569 531 template<class M1, class M2> 570 532 Vf2Wizard< SetNodeEqBase<bits::vf2::MapEq<M1,M2> > > 571 nodeLabels(const M1 &m1,const M2 &m2) 572 { 533 nodeLabels(const M1 &m1,const M2 &m2){ 573 534 return nodeEq(bits::vf2::MapEq<M1,M2>(m1,m2)); 574 535 } … … 582 543 ///The mapping type is set to \ref SUBGRAPH by default. 583 544 /// 584 ///\sa See \ref Vf2MappingType for the possible values. 585 Vf2Wizard<Base> &mappingType(Vf2MappingType m_type) 586 { 545 ///\sa See \ref MappingType for the possible values. 546 Vf2Wizard<Base> &mappingType(MappingType m_type) { 587 547 _mapping_type = m_type; 588 548 return *this; … … 594 554 ///\ref namedtemplparam "Named parameter" for setting 595 555 ///the mapping type to \ref INDUCED. 596 Vf2Wizard<Base> &induced() 597 { 556 Vf2Wizard<Base> &induced() { 598 557 _mapping_type = INDUCED; 599 558 return *this; … … 605 564 ///\ref namedtemplparam "Named parameter" for setting 606 565 ///the mapping type to \ref ISOMORPH. 607 Vf2Wizard<Base> &iso() 608 { 566 Vf2Wizard<Base> &iso() { 609 567 _mapping_type = ISOMORPH; 610 568 return *this; 611 569 } 612 570 571 613 572 ///Runs VF2 algorithm. 614 573 … … 616 575 /// 617 576 ///\retval true if a mapping is found. 618 ///\retval false if there is no (more) mapping. 619 bool run() 620 { 577 ///\retval false if there is no mapping. 578 bool run(){ 621 579 if(Base::_local_mapping) 622 580 Base::createMapping(); … … 631 589 if(Base::_local_mapping) 632 590 delete reinterpret_cast<Mapping*>(_mapping); 591 592 return ret; 593 } 594 595 ///Get a pointer to the generated Vf2 object. 596 597 ///Gives a pointer to the generated Vf2 object. 598 /// 599 ///\return Pointer to the generated Vf2 object. 600 ///\warning Don't forget to delete the referred Vf2 object after use. 601 Vf2<Graph1, Graph2, Mapping, NodeEq >* getPtrToVf2Object() { 602 if(Base::_local_mapping) 603 Base::createMapping(); 604 Vf2<Graph1, Graph2, Mapping, NodeEq >* ptr = 605 new Vf2<Graph1, Graph2, Mapping, NodeEq> 606 (_g1, _g2, *reinterpret_cast<Mapping*>(_mapping), _node_eq); 607 ptr>mappingType(_mapping_type); 608 if(Base::_local_mapping) 609 ptr>_deallocMappingAfterUse = true; 610 return ptr; 611 } 612 613 ///Counts the number of mappings. 614 615 ///This method counts the number of mappings. 616 /// 617 /// \return The number of mappings. 618 int count() { 619 if(Base::_local_mapping) 620 Base::createMapping(); 621 622 Vf2<Graph1, Graph2, Mapping, NodeEq> 623 alg(_g1, _g2, *reinterpret_cast<Mapping*>(_mapping), _node_eq); 624 if(Base::_local_mapping) 625 alg._deallocMappingAfterUse = true; 626 alg.mappingType(_mapping_type); 627 628 int ret = 0; 629 while(alg.find()) 630 ++ret; 633 631 634 632 return ret; … … 645 643 ///The following examples show how to use these parameters. 646 644 ///\code 647 /// // Find an embedding of graph g into graph h645 /// // Find an embedding of graph g1 into graph g2 648 646 /// ListGraph::NodeMap<ListGraph::Node> m(g); 649 /// vf2(g,h).mapping(m).run(); 650 /// 651 /// // Check whether graphs g and h are isomorphic 652 /// bool is_iso = vf2(g,h).iso().run(); 647 /// vf2(g1,g2).mapping(m).run(); 648 /// 649 /// // Check whether graphs g1 and g2 are isomorphic 650 /// bool is_iso = vf2(g1,g2).iso().run(); 651 /// 652 /// // Count the number of isomorphisms 653 /// int num_isos = vf2(g1,g2).iso().count(); 654 /// 655 /// // Iterate through all the induced subgraph mappings of graph g1 into g2 656 /// auto* myVf2 = vf2(g1,g2).mapping(m).nodeLabels(c1,c2) 657 /// .induced().getPtrToVf2Object(); 658 /// while(myVf2>find()){ 659 /// //process the current mapping m 660 /// } 661 /// delete myVf22; 653 662 ///\endcode 654 ///\warning Don't forget to put the \ref Vf2Wizard::run() "run()" 663 ///\warning Don't forget to put the \ref Vf2Wizard::run() "run()", 664 ///\ref Vf2Wizard::count() "count()" or 665 ///the \ref Vf2Wizard::getPtrToVf2Object() "getPtrToVf2Object()" 655 666 ///to the end of the expression. 656 667 ///\sa Vf2Wizard 657 668 ///\sa Vf2 658 669 template<class G1, class G2> 659 Vf2Wizard<Vf2WizardBase<G1,G2> > vf2(const G1 &g1, const G2 &g2) 660 { 670 Vf2Wizard<Vf2WizardBase<G1,G2> > vf2(const G1 &g1, const G2 &g2) { 661 671 return Vf2Wizard<Vf2WizardBase<G1,G2> >(g1,g2); 662 672 } 
test/CMakeLists.txt
r1350 r1405 56 56 unionfind_test 57 57 vf2_test 58 vf2pp_test 58 59 ) 59 60 
test/vf2_test.cc
r1352 r1405 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2015 5 * Copyright (C) 20152017 6 6 * EMAXA Kutatofejleszto Kft. (EMAXA Research Ltd.) 7 7 * … … 184 184 class EqComparable { 185 185 public: 186 bool operator==(const EqComparable&) { return false; } 186 bool operator==(const EqComparable&) { 187 return false; 188 } 187 189 }; 188 190 … … 190 192 class EqClass { 191 193 public: 192 bool operator()(A, B) { return false; } 194 bool operator()(A, B){ 195 return false; 196 } 193 197 }; 194 198 195 199 template<class G1,class G2> 196 void checkVf2Compile() 197 { 200 void checkVf2Compile() { 198 201 G1 g; 199 202 G2 h; … … 206 209 succ = vf2(g,h).iso().run(); 207 210 succ = vf2(g,h).mapping(r).run(); 211 212 Vf2<G1,G2,concepts::ReadWriteMap<typename G1::Node, typename G2::Node>, 213 EqClass<typename G1::Node,typename G2::Node> > 214 myVf2(g,h,r,EqClass<typename G1::Node,typename G2::Node>()); 215 myVf2.find(); 216 208 217 succ = vf2(g,h).induced().mapping(r).run(); 209 218 succ = vf2(g,h).iso().mapping(r).run(); 219 210 220 concepts::ReadMap<typename G1::Node, EqComparable> l1; 211 221 concepts::ReadMap<typename G2::Node, EqComparable> l2; … … 215 225 } 216 226 217 void justCompile() 218 { 227 void justCompile() { 219 228 checkVf2Compile<concepts::Graph,concepts::Graph>(); 220 229 checkVf2Compile<concepts::Graph,SmartGraph>(); … … 223 232 224 233 template<class G1, class G2, class I> 225 void checkSub(const G1 &g1, const G2 &g2, const I &i) 226 { 234 void checkSub(const G1 &g1, const G2 &g2, const I &i) { 227 235 { 228 236 std::set<typename G2::Node> image; 229 for(typename G1::NodeIt n(g1);n!=INVALID;++n) 230 { 231 check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping."); 232 check(image.count(i[n])==0,"Wrong isomorphism: not injective."); 233 image.insert(i[n]); 234 } 237 for(typename G1::NodeIt n(g1);n!=INVALID;++n){ 238 check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping."); 239 check(image.count(i[n])==0,"Wrong isomorphism: not injective."); 240 image.insert(i[n]); 241 } 235 242 } 236 243 for(typename G1::EdgeIt e(g1);e!=INVALID;++e) … … 240 247 241 248 template<class G1, class G2, class I> 242 void checkInd(const G1 &g1, const G2 &g2, const I &i) 243 { 249 void checkInd(const G1 &g1, const G2 &g2, const I &i) { 244 250 std::set<typename G2::Node> image; 245 for(typename G1::NodeIt n(g1);n!=INVALID;++n) 246 { 251 for(typename G1::NodeIt n(g1);n!=INVALID;++n) { 247 252 check(i[n]!=INVALID, "Wrong isomorphism: incomplete mapping."); 248 253 check(image.count(i[n])==0,"Wrong isomorphism: not injective."); 249 254 image.insert(i[n]); 250 255 } 251 256 for(typename G1::NodeIt n(g1); n!=INVALID; ++n) 252 257 for(typename G1::NodeIt m(g1); m!=INVALID; ++m) 253 if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID)) 254 { 258 if((findEdge(g1,n,m)==INVALID) != (findEdge(g2,i[n],i[m])==INVALID)) { 255 259 std::cout << "Wrong isomorphism: edge mismatch"; 256 260 exit(1); 257 258 261 } 262 } 259 263 260 264 template<class G1,class G2> 261 int checkSub(const G1 &g1, const G2 &g2) 262 { 265 int checkSub(const G1 &g1, const G2 &g2) { 263 266 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID); 264 if(vf2(g1,g2).mapping(iso).run()) 265 {266 checkSub(g1,g2,iso);267 return true;268 }269 elsereturn false;267 if(vf2(g1,g2).mapping(iso).run()) { 268 checkSub(g1,g2,iso); 269 return true; 270 } 271 else 272 return false; 270 273 } 271 274 272 275 template<class G1,class G2> 273 int checkInd(const G1 &g1, const G2 &g2) 274 { 276 int checkInd(const G1 &g1, const G2 &g2) { 275 277 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID); 276 if(vf2(g1,g2).induced().mapping(iso).run()) 277 {278 checkInd(g1,g2,iso);279 return true;280 }281 elsereturn false;278 if(vf2(g1,g2).induced().mapping(iso).run()) { 279 checkInd(g1,g2,iso); 280 return true; 281 } 282 else 283 return false; 282 284 } 283 285 284 286 template<class G1,class G2> 285 int checkIso(const G1 &g1, const G2 &g2) 286 { 287 int checkIso(const G1 &g1, const G2 &g2) { 287 288 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID); 288 if(vf2(g1,g2).iso().mapping(iso).run()) 289 {290 check(countNodes(g1)==countNodes(g2),291 "Wrong iso alg.: they are not isomophic.");292 checkInd(g1,g2,iso);293 return true;294 }295 elsereturn false;289 if(vf2(g1,g2).iso().mapping(iso).run()) { 290 check(countNodes(g1)==countNodes(g2), 291 "Wrong iso alg.: they are not isomophic."); 292 checkInd(g1,g2,iso); 293 return true; 294 } 295 else 296 return false; 296 297 } 297 298 298 299 template<class G1, class G2, class L1, class L2, class I> 299 300 void checkLabel(const G1 &g1, const G2 &, 300 const L1 &l1, const L2 &l2,const I &i) 301 { 301 const L1 &l1, const L2 &l2,const I &i) { 302 302 for(typename G1::NodeIt n(g1);n!=INVALID;++n) 303 { 304 check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch."); 305 } 303 check(l1[n]==l2[i[n]],"Wrong isomorphism: label mismatch."); 306 304 } 307 305 308 306 template<class G1,class G2,class L1,class L2> 309 int checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2) 310 { 307 int checkSub(const G1 &g1, const G2 &g2, const L1 &l1, const L2 &l2) { 311 308 typename G1:: template NodeMap<typename G2::Node> iso(g1,INVALID); 312 if(vf2(g1,g2).nodeLabels(l1,l2).mapping(iso).run()) 313 {314 checkSub(g1,g2,iso);315 checkLabel(g1,g2,l1,l2,iso);316 return true;317 }318 elsereturn false;309 if(vf2(g1,g2).nodeLabels(l1,l2).mapping(iso).run()){ 310 checkSub(g1,g2,iso); 311 checkLabel(g1,g2,l1,l2,iso); 312 return true; 313 } 314 else 315 return false; 319 316 } 320 317 321 318 int main() { 322 319 make_graphs(); 320 // justCompile(); 323 321 check(checkSub(c5,petersen), "There should exist a C5>Petersen mapping."); 324 322 check(!checkSub(c7,petersen),
Note: See TracChangeset
for help on using the changeset viewer.