Changeset 1408:b9fad0f9f8ab in lemon
 Timestamp:
 10/07/17 15:45:56 (7 years ago)
 Branch:
 default
 Phase:
 public
 Location:
 lemon
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

lemon/vf2.h
r1407 r1408 113 113 #endif 114 114 class Vf2 { 115 //Current depth in the DFS tree. 116 int _depth; 115 //The graph to be embedded 116 const G1 &_g1; 117 118 //The graph into which g1 is to be embedded 119 const G2 &_g2; 117 120 118 121 //Functor with bool operator()(G1::Node,G2::Node), which returns 1 … … 120 123 NEQ _nEq; 121 124 122 // _conn[v2] = number of covered neighbours of v2123 typename G2::template NodeMap<int> _conn;125 //Current depth in the DFS tree. 126 int _depth; 124 127 125 128 //The current mapping. _mapping[v1]=v2 iff v1 has been mapped to v2, … … 127 130 M &_mapping; 128 131 129 //order[i] is the node of g1 for which a pair is searched if depth=i 130 std::vector<typename G1::Node> order; 131 132 //currEdgeIts[i] is the last used edge iterator in the ith 133 //depth to find a pair for node order[i] 134 std::vector<typename G2::IncEdgeIt> currEdgeIts; 132 //_order[i] is the node of g1 for which a pair is searched if depth=i 133 std::vector<typename G1::Node> _order; 135 134 136 //The graph to be embedded 137 const G1 &_g1; 138 139 //The graph into which g1 is to be embedded 140 const G2 &_g2; 135 //_conn[v2] = number of covered neighbours of v2 136 typename G2::template NodeMap<int> _conn; 137 138 //_currEdgeIts[i] is the last used edge iterator in the ith 139 //depth to find a pair for node _order[i] 140 std::vector<typename G2::IncEdgeIt> _currEdgeIts; 141 141 142 142 //lookup tables for cutting the searchtree 143 typename G1::template NodeMap<int> rNew1t,rInOut1t;143 typename G1::template NodeMap<int> _rNew1t, _rInOut1t; 144 144 145 145 MappingType _mapping_type; … … 160 160 switch(MT) { 161 161 case INDUCED: 162 return rInOut1t[n1]<=rInOut2&&rNew1t[n1]<=rNew2;162 return _rInOut1t[n1]<=rInOut2&&_rNew1t[n1]<=rNew2; 163 163 case SUBGRAPH: 164 return rInOut1t[n1]<=rInOut2;164 return _rInOut1t[n1]<=rInOut2; 165 165 case ISOMORPH: 166 return rInOut1t[n1]==rInOut2&&rNew1t[n1]==rNew2;166 return _rInOut1t[n1]==rInOut2&&_rNew1t[n1]==rNew2; 167 167 default: 168 168 return false; … … 236 236 // we will find pairs for the nodes of g1 in this order 237 237 238 // bits::vf2::DfsLeaveOrder<G1> v(_g1, order);238 // bits::vf2::DfsLeaveOrder<G1> v(_g1,_order); 239 239 // DfsVisit<G1,bits::vf2::DfsLeaveOrder<G1> >dfs(_g1, v); 240 240 // dfs.run(); 241 241 242 242 //it is more efficient in practice than DFS 243 bits::vf2::BfsLeaveOrder<G1> v(_g1, order);243 bits::vf2::BfsLeaveOrder<G1> v(_g1,_order); 244 244 BfsVisit<G1,bits::vf2::BfsLeaveOrder<G1> >bfs(_g1, v); 245 245 bfs.run(); … … 249 249 bool extMatch() { 250 250 while(_depth>=0) { 251 if(_depth==static_cast<int>( order.size())) {251 if(_depth==static_cast<int>(_order.size())) { 252 252 //all nodes of g1 are mapped to nodes of g2 253 253 _depth; 254 254 return true; 255 255 } 256 typename G1::Node& nodeOfDepth = order[_depth];256 typename G1::Node& nodeOfDepth = _order[_depth]; 257 257 const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth]; 258 typename G2::IncEdgeIt &edgeItOfDepth = currEdgeIts[_depth];258 typename G2::IncEdgeIt &edgeItOfDepth = _currEdgeIts[_depth]; 259 259 //the node of g2 whose neighbours are the candidates for 260 260 //the pair of nodeOfDepth … … 327 327 void setRNew1tRInOut1t() { 328 328 typename G1::template NodeMap<int> tmp(_g1,0); 329 for(unsigned int i=0; i< order.size(); ++i) {330 const typename G1::Node& orderI = order[i];329 for(unsigned int i=0; i<_order.size(); ++i) { 330 const typename G1::Node& orderI = _order[i]; 331 331 tmp[orderI]=1; 332 332 for(typename G1::IncEdgeIt e1(_g1,orderI); e1!=INVALID; ++e1) { 333 333 const typename G1::Node currNode=_g1.oppositeNode(orderI,e1); 334 334 if(tmp[currNode]>0) 335 ++ rInOut1t[orderI];335 ++_rInOut1t[orderI]; 336 336 else if(tmp[currNode]==0) 337 ++ rNew1t[orderI];337 ++_rNew1t[orderI]; 338 338 } 339 339 for(typename G1::IncEdgeIt e1(_g1,orderI); e1!=INVALID; ++e1) { … … 356 356 ///mappable to another. By default it is an always true operator. 357 357 Vf2(const G1 &g1, const G2 &g2, M &m, const NEQ &neq = NEQ() ) : 358 _nEq(neq), _conn(g2,0), _mapping(m), order(countNodes(g1)), 359 currEdgeIts(countNodes(g1),INVALID), _g1(g1), _g2(g2), rNew1t(g1,0), 360 rInOut1t(g1,0), _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0) 358 _g1(g1), _g2(g2), _nEq(neq), _depth(0), _mapping(m), 359 _order(countNodes(g1)), _conn(g2,0), 360 _currEdgeIts(countNodes(g1),INVALID), _rNew1t(g1,0), _rInOut1t(g1,0), 361 _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0) 361 362 { 362 _depth=0;363 363 setOrder(); 364 364 setRNew1tRInOut1t(); 
lemon/vf2pp.h
r1407 r1408 29 29 #include <lemon/bits/vf2_internals.h> 30 30 31 32 31 #include <vector> 33 32 #include <algorithm> 34 33 #include <utility> 35 36 34 37 35 namespace lemon { … … 102 100 #endif 103 101 class Vf2pp { 102 //The graph to be embedded 103 const G1 &_g1; 104 105 //The graph into which g1 is to be embedded 106 const G2 &_g2; 107 104 108 //Current depth in the search tree. 105 109 int _depth; 106 107 //_conn[v2] = number of covered neighbours of v2108 typename G2::template NodeMap<int> _conn;109 110 110 111 //The current mapping. _mapping[v1]=v2 iff v1 has been mapped to v2, … … 112 113 M &_mapping; 113 114 114 //order[i] is a node of g1 for which a pair is searched if depth=i 115 std::vector<typename G1::Node> order; 116 117 //currEdgeIts[i] is the last used edge iterator in the ith 118 //depth to find a pair for node order[i] 119 std::vector<typename G2::IncEdgeIt> currEdgeIts; 115 //_order[i] is a node of g1 for which a pair is searched if depth=i 116 std::vector<typename G1::Node> _order; 117 118 //_conn[v2] = number of covered neighbours of v2 119 typename G2::template NodeMap<int> _conn; 120 121 //_currEdgeIts[i] is the last used edge iterator in the ith 122 //depth to find a pair for node _order[i] 123 std::vector<typename G2::IncEdgeIt> _currEdgeIts; 120 124 121 //The graph to be embedded 122 const G1 &_g1; 123 124 //The graph into which g1 is to be embedded 125 const G2 &_g2; 126 127 //rNewLabels1[v] is a pair of form 125 //_rNewLabels1[v] is a pair of form 128 126 //(label; num. of uncov. nodes with such label and no covered neighbours) 129 127 typename G1::template NodeMap<std::vector<std::pair<int,int> > > 130 rNewLabels1;131 132 // rInOutLabels1[v] is the number of covered neighbours of v for each label128 _rNewLabels1; 129 130 //_rInOutLabels1[v] is the number of covered neighbours of v for each label 133 131 //in form (label,number of such labels) 134 132 typename G1::template NodeMap<std::vector<std::pair<int,int> > > 135 rInOutLabels1;133 _rInOutLabels1; 136 134 137 135 //_intLabels1[v]==i means that node v has label i in _g1 … … 144 142 145 143 //largest label 146 const int maxLabel;144 const int _maxLabel; 147 145 148 146 //lookup tables for manipulating with label class cardinalities 149 147 //(after use they have to be reset to 0..0) 150 std::vector<int> labelTmp1,labelTmp2;148 std::vector<int> _labelTmp1,_labelTmp2; 151 149 152 150 MappingType _mapping_type; … … 162 160 const typename G2::Node currNode=_g2.oppositeNode(n2,e2); 163 161 if(_conn[currNode]>0) 164  labelTmp1[_intLabels2[currNode]];162 _labelTmp1[_intLabels2[currNode]]; 165 163 else if(MT!=SUBGRAPH&&_conn[currNode]==0) 166  labelTmp2[_intLabels2[currNode]];164 _labelTmp2[_intLabels2[currNode]]; 167 165 } 168 166 169 167 bool ret=1; 170 168 if(ret) { 171 for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i)172 labelTmp1[rInOutLabels1[n1][i].first]+=rInOutLabels1[n1][i].second;169 for(unsigned int i = 0; i < _rInOutLabels1[n1].size(); ++i) 170 _labelTmp1[_rInOutLabels1[n1][i].first]+=_rInOutLabels1[n1][i].second; 173 171 174 172 if(MT!=SUBGRAPH) 175 for(unsigned int i = 0; i < rNewLabels1[n1].size(); ++i)176 labelTmp2[rNewLabels1[n1][i].first]+=rNewLabels1[n1][i].second;173 for(unsigned int i = 0; i < _rNewLabels1[n1].size(); ++i) 174 _labelTmp2[_rNewLabels1[n1][i].first]+=_rNewLabels1[n1][i].second; 177 175 178 176 switch(MT) { 179 177 case INDUCED: 180 for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i)181 if( labelTmp1[rInOutLabels1[n1][i].first]>0) {178 for(unsigned int i = 0; i < _rInOutLabels1[n1].size(); ++i) 179 if(_labelTmp1[_rInOutLabels1[n1][i].first]>0) { 182 180 ret=0; 183 181 break; 184 182 } 185 183 if(ret) 186 for(unsigned int i = 0; i < rNewLabels1[n1].size(); ++i)187 if( labelTmp2[rNewLabels1[n1][i].first]>0) {184 for(unsigned int i = 0; i < _rNewLabels1[n1].size(); ++i) 185 if(_labelTmp2[_rNewLabels1[n1][i].first]>0) { 188 186 ret=0; 189 187 break; … … 191 189 break; 192 190 case SUBGRAPH: 193 for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i)194 if( labelTmp1[rInOutLabels1[n1][i].first]>0) {191 for(unsigned int i = 0; i < _rInOutLabels1[n1].size(); ++i) 192 if(_labelTmp1[_rInOutLabels1[n1][i].first]>0) { 195 193 ret=0; 196 194 break; … … 198 196 break; 199 197 case ISOMORPH: 200 for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i)201 if( labelTmp1[rInOutLabels1[n1][i].first]!=0) {198 for(unsigned int i = 0; i < _rInOutLabels1[n1].size(); ++i) 199 if(_labelTmp1[_rInOutLabels1[n1][i].first]!=0) { 202 200 ret=0; 203 201 break; 204 202 } 205 203 if(ret) 206 for(unsigned int i = 0; i < rNewLabels1[n1].size(); ++i)207 if( labelTmp2[rNewLabels1[n1][i].first]!=0) {204 for(unsigned int i = 0; i < _rNewLabels1[n1].size(); ++i) 205 if(_labelTmp2[_rNewLabels1[n1][i].first]!=0) { 208 206 ret=0; 209 207 break; … … 213 211 return false; 214 212 } 215 for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i)216 labelTmp1[rInOutLabels1[n1][i].first]=0;213 for(unsigned int i = 0; i < _rInOutLabels1[n1].size(); ++i) 214 _labelTmp1[_rInOutLabels1[n1][i].first]=0; 217 215 218 216 if(MT!=SUBGRAPH) 219 for(unsigned int i = 0; i < rNewLabels1[n1].size(); ++i)220 labelTmp2[rNewLabels1[n1][i].first]=0;217 for(unsigned int i = 0; i < _rNewLabels1[n1].size(); ++i) 218 _labelTmp2[_rNewLabels1[n1][i].first]=0; 221 219 } 222 220 223 221 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) { 224 222 const typename G2::Node currNode=_g2.oppositeNode(n2,e2); 225 labelTmp1[_intLabels2[currNode]]=0;223 _labelTmp1[_intLabels2[currNode]]=0; 226 224 if(MT!=SUBGRAPH&&_conn[currNode]==0) 227 labelTmp2[_intLabels2[currNode]]=0;225 _labelTmp2[_intLabels2[currNode]]=0; 228 226 } 229 227 … … 311 309 typename G1::template NodeMap<int>& dm1, 312 310 typename G1::template NodeMap<bool>& added) { 313 order[orderIndex]=source;311 _order[orderIndex]=source; 314 312 added[source]=1; 315 313 … … 321 319 322 320 while(orderIndex<=lastAdded){ 323 typename G1::Node currNode = order[orderIndex];321 typename G1::Node currNode = _order[orderIndex]; 324 322 for(typename G1::IncEdgeIt e(_g1,currNode); e!=INVALID; ++e) { 325 323 typename G1::Node n = _g1.oppositeNode(currNode,e); 326 324 if(!added[n]) { 327 order[++lastAdded]=n;325 _order[++lastAdded]=n; 328 326 added[n]=1; 329 327 } … … 333 331 int minInd=j; 334 332 for(unsigned int i = j+1; i <= endPosOfLevel; ++i) 335 if(currConn[ order[i]]>currConn[order[minInd]]336 (currConn[ order[i]]==currConn[order[minInd]]&&337 (dm1[ order[i]]>dm1[order[minInd]]338 (dm1[ order[i]]==dm1[order[minInd]]&&339 labelTmp1[_intLabels1[order[minInd]]]>340 labelTmp1[_intLabels1[order[i]]]))))333 if(currConn[_order[i]]>currConn[_order[minInd]] 334 (currConn[_order[i]]==currConn[_order[minInd]]&& 335 (dm1[_order[i]]>dm1[_order[minInd]] 336 (dm1[_order[i]]==dm1[_order[minInd]]&& 337 _labelTmp1[_intLabels1[_order[minInd]]]> 338 _labelTmp1[_intLabels1[_order[i]]])))) 341 339 minInd=i; 342 340 343  labelTmp1[_intLabels1[order[minInd]]];344 for(typename G1::IncEdgeIt e(_g1, order[minInd]); e!=INVALID; ++e)345 ++currConn[_g1.oppositeNode( order[minInd],e)];346 std::swap( order[j],order[minInd]);341 _labelTmp1[_intLabels1[_order[minInd]]]; 342 for(typename G1::IncEdgeIt e(_g1,_order[minInd]); e!=INVALID; ++e) 343 ++currConn[_g1.oppositeNode(_order[minInd],e)]; 344 std::swap(_order[j],_order[minInd]); 347 345 } 348 346 startPosOfLevel=endPosOfLevel+1; … … 357 355 void setOrder(){ 358 356 for(typename G2::NodeIt n2(_g2); n2!=INVALID; ++n2) 359 ++ labelTmp1[_intLabels2[n2]];357 ++_labelTmp1[_intLabels2[n2]]; 360 358 361 359 typename G1::template NodeMap<int> dm1(_g1,0); … … 373 371 for(typename G1::NodeIt n1(_g1,minNode); n1!=INVALID; ++n1) 374 372 if(!added[n1] && 375 ( labelTmp1[_intLabels1[minNode]]>376 labelTmp1[_intLabels1[n1]](dm1[minNode]<dm1[n1]&&377 labelTmp1[_intLabels1[minNode]]==378 labelTmp1[_intLabels1[n1]])))373 (_labelTmp1[_intLabels1[minNode]]> 374 _labelTmp1[_intLabels1[n1]](dm1[minNode]<dm1[n1]&& 375 _labelTmp1[_intLabels1[minNode]]== 376 _labelTmp1[_intLabels1[n1]]))) 379 377 minNode=n1; 380 378 processBFSLevel(minNode,orderIndex,dm1,added); … … 383 381 ++n; 384 382 } 385 for(unsigned int i = 0; i < labelTmp1.size(); ++i)386 labelTmp1[i]=0;383 for(unsigned int i = 0; i < _labelTmp1.size(); ++i) 384 _labelTmp1[i]=0; 387 385 } 388 386 … … 391 389 bool extMatch(){ 392 390 while(_depth>=0) { 393 if(_depth==static_cast<int>( order.size())) {391 if(_depth==static_cast<int>(_order.size())) { 394 392 //all nodes of g1 are mapped to nodes of g2 395 393 _depth; 396 394 return true; 397 395 } 398 typename G1::Node& nodeOfDepth = order[_depth];396 typename G1::Node& nodeOfDepth = _order[_depth]; 399 397 const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth]; 400 typename G2::IncEdgeIt &edgeItOfDepth = currEdgeIts[_depth];398 typename G2::IncEdgeIt &edgeItOfDepth = _currEdgeIts[_depth]; 401 399 //the node of g2 whose neighbours are the candidates for 402 //the pair of order[_depth]400 //the pair of _order[_depth] 403 401 typename G2::Node currPNode; 404 402 if(edgeItOfDepth==INVALID){ 405 403 typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth); 406 //if _mapping[ order[_depth]]!=INVALID, we don't need fstMatchedE404 //if _mapping[_order[_depth]]!=INVALID, we don't need fstMatchedE 407 405 if(pairOfNodeOfDepth==INVALID) { 408 406 for(; fstMatchedE!=INVALID && … … 469 467 void setRNew1tRInOut1t(){ 470 468 typename G1::template NodeMap<int> tmp(_g1,0); 471 for(unsigned int i=0; i< order.size(); ++i) {472 tmp[ order[i]]=1;473 for(typename G1::IncEdgeIt e1(_g1, order[i]); e1!=INVALID; ++e1) {474 const typename G1::Node currNode=_g1.oppositeNode( order[i],e1);469 for(unsigned int i=0; i<_order.size(); ++i) { 470 tmp[_order[i]]=1; 471 for(typename G1::IncEdgeIt e1(_g1,_order[i]); e1!=INVALID; ++e1) { 472 const typename G1::Node currNode=_g1.oppositeNode(_order[i],e1); 475 473 if(tmp[currNode]>0) 476 ++ labelTmp1[_intLabels1[currNode]];474 ++_labelTmp1[_intLabels1[currNode]]; 477 475 else if(tmp[currNode]==0) 478 ++ labelTmp2[_intLabels1[currNode]];479 } 480 // labelTmp1[i]=number of neightbours with label i in set rInOut481 // labelTmp2[i]=number of neightbours with label i in set rNew482 for(typename G1::IncEdgeIt e1(_g1, order[i]); e1!=INVALID; ++e1) {483 const int& currIntLabel = _intLabels1[_g1.oppositeNode( order[i],e1)];484 if( labelTmp1[currIntLabel]>0) {485 rInOutLabels1[order[i]]476 ++_labelTmp2[_intLabels1[currNode]]; 477 } 478 //_labelTmp1[i]=number of neightbours with label i in set rInOut 479 //_labelTmp2[i]=number of neightbours with label i in set rNew 480 for(typename G1::IncEdgeIt e1(_g1,_order[i]); e1!=INVALID; ++e1) { 481 const int& currIntLabel = _intLabels1[_g1.oppositeNode(_order[i],e1)]; 482 if(_labelTmp1[currIntLabel]>0) { 483 _rInOutLabels1[_order[i]] 486 484 .push_back(std::make_pair(currIntLabel, 487 labelTmp1[currIntLabel]));488 labelTmp1[currIntLabel]=0;485 _labelTmp1[currIntLabel])); 486 _labelTmp1[currIntLabel]=0; 489 487 } 490 else if( labelTmp2[currIntLabel]>0) {491 rNewLabels1[order[i]].492 push_back(std::make_pair(currIntLabel, labelTmp2[currIntLabel]));493 labelTmp2[currIntLabel]=0;488 else if(_labelTmp2[currIntLabel]>0) { 489 _rNewLabels1[_order[i]]. 490 push_back(std::make_pair(currIntLabel,_labelTmp2[currIntLabel])); 491 _labelTmp2[currIntLabel]=0; 494 492 } 495 493 } 496 494 497 for(typename G1::IncEdgeIt e1(_g1, order[i]); e1!=INVALID; ++e1) {498 int& tmpCurrNode=tmp[_g1.oppositeNode( order[i],e1)];495 for(typename G1::IncEdgeIt e1(_g1,_order[i]); e1!=INVALID; ++e1) { 496 int& tmpCurrNode=tmp[_g1.oppositeNode(_order[i],e1)]; 499 497 if(tmpCurrNode!=1) 500 498 ++tmpCurrNode; … … 533 531 ///different labels. 534 532 Vf2pp(const G1 &g1, const G2 &g2,M &m, M1 &intLabels1, M2 &intLabels2) : 535 _ depth(0), _conn(g2,0), _mapping(m),order(countNodes(g1),INVALID),536 currEdgeIts(countNodes(g1),INVALID), _g1(g1), _g2(g2),rNewLabels1(_g1),537 rInOutLabels1(_g1), _intLabels1(intLabels1) ,_intLabels2(intLabels2),538 maxLabel(getMaxLabel()), labelTmp1(maxLabel+1),labelTmp2(maxLabel+1),533 _g1(g1), _g2(g2), _depth(0), _mapping(m), _order(countNodes(g1),INVALID), 534 _conn(g2,0), _currEdgeIts(countNodes(g1),INVALID), _rNewLabels1(_g1), 535 _rInOutLabels1(_g1), _intLabels1(intLabels1) ,_intLabels2(intLabels2), 536 _maxLabel(getMaxLabel()), _labelTmp1(_maxLabel+1),_labelTmp2(_maxLabel+1), 539 537 _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0), 540 538 _deallocLabelsAfterUse(0)
Note: See TracChangeset
for help on using the changeset viewer.