1.1 --- a/lemon/vf2pp.h Sat Oct 07 03:18:49 2017 +0200
1.2 +++ b/lemon/vf2pp.h Sat Oct 07 15:45:56 2017 +0200
1.3 @@ -28,12 +28,10 @@
1.4 #include <lemon/bfs.h>
1.5 #include <lemon/bits/vf2_internals.h>
1.6
1.7 -
1.8 #include <vector>
1.9 #include <algorithm>
1.10 #include <utility>
1.11
1.12 -
1.13 namespace lemon {
1.14 namespace bits {
1.15 namespace vf2pp {
1.16 @@ -101,38 +99,38 @@
1.17 class M2 = typename G2::template NodeMap<int> >
1.18 #endif
1.19 class Vf2pp {
1.20 - //Current depth in the search tree.
1.21 - int _depth;
1.22 -
1.23 - //_conn[v2] = number of covered neighbours of v2
1.24 - typename G2::template NodeMap<int> _conn;
1.25 -
1.26 - //The current mapping. _mapping[v1]=v2 iff v1 has been mapped to v2,
1.27 - //where v1 is a node of G1 and v2 is a node of G2
1.28 - M &_mapping;
1.29 -
1.30 - //order[i] is a node of g1 for which a pair is searched if depth=i
1.31 - std::vector<typename G1::Node> order;
1.32 -
1.33 - //currEdgeIts[i] is the last used edge iterator in the i-th
1.34 - //depth to find a pair for node order[i]
1.35 - std::vector<typename G2::IncEdgeIt> currEdgeIts;
1.36 -
1.37 //The graph to be embedded
1.38 const G1 &_g1;
1.39
1.40 //The graph into which g1 is to be embedded
1.41 const G2 &_g2;
1.42
1.43 - //rNewLabels1[v] is a pair of form
1.44 + //Current depth in the search tree.
1.45 + int _depth;
1.46 +
1.47 + //The current mapping. _mapping[v1]=v2 iff v1 has been mapped to v2,
1.48 + //where v1 is a node of G1 and v2 is a node of G2
1.49 + M &_mapping;
1.50 +
1.51 + //_order[i] is a node of g1 for which a pair is searched if depth=i
1.52 + std::vector<typename G1::Node> _order;
1.53 +
1.54 + //_conn[v2] = number of covered neighbours of v2
1.55 + typename G2::template NodeMap<int> _conn;
1.56 +
1.57 + //_currEdgeIts[i] is the last used edge iterator in the i-th
1.58 + //depth to find a pair for node _order[i]
1.59 + std::vector<typename G2::IncEdgeIt> _currEdgeIts;
1.60 +
1.61 + //_rNewLabels1[v] is a pair of form
1.62 //(label; num. of uncov. nodes with such label and no covered neighbours)
1.63 typename G1::template NodeMap<std::vector<std::pair<int,int> > >
1.64 - rNewLabels1;
1.65 + _rNewLabels1;
1.66
1.67 - //rInOutLabels1[v] is the number of covered neighbours of v for each label
1.68 + //_rInOutLabels1[v] is the number of covered neighbours of v for each label
1.69 //in form (label,number of such labels)
1.70 typename G1::template NodeMap<std::vector<std::pair<int,int> > >
1.71 - rInOutLabels1;
1.72 + _rInOutLabels1;
1.73
1.74 //_intLabels1[v]==i means that node v has label i in _g1
1.75 //(i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
1.76 @@ -143,11 +141,11 @@
1.77 M2 &_intLabels2;
1.78
1.79 //largest label
1.80 - const int maxLabel;
1.81 + const int _maxLabel;
1.82
1.83 //lookup tables for manipulating with label class cardinalities
1.84 //(after use they have to be reset to 0..0)
1.85 - std::vector<int> labelTmp1,labelTmp2;
1.86 + std::vector<int> _labelTmp1,_labelTmp2;
1.87
1.88 MappingType _mapping_type;
1.89
1.90 @@ -161,50 +159,50 @@
1.91 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
1.92 const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
1.93 if(_conn[currNode]>0)
1.94 - --labelTmp1[_intLabels2[currNode]];
1.95 + --_labelTmp1[_intLabels2[currNode]];
1.96 else if(MT!=SUBGRAPH&&_conn[currNode]==0)
1.97 - --labelTmp2[_intLabels2[currNode]];
1.98 + --_labelTmp2[_intLabels2[currNode]];
1.99 }
1.100
1.101 bool ret=1;
1.102 if(ret) {
1.103 - for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i)
1.104 - labelTmp1[rInOutLabels1[n1][i].first]+=rInOutLabels1[n1][i].second;
1.105 + for(unsigned int i = 0; i < _rInOutLabels1[n1].size(); ++i)
1.106 + _labelTmp1[_rInOutLabels1[n1][i].first]+=_rInOutLabels1[n1][i].second;
1.107
1.108 if(MT!=SUBGRAPH)
1.109 - for(unsigned int i = 0; i < rNewLabels1[n1].size(); ++i)
1.110 - labelTmp2[rNewLabels1[n1][i].first]+=rNewLabels1[n1][i].second;
1.111 + for(unsigned int i = 0; i < _rNewLabels1[n1].size(); ++i)
1.112 + _labelTmp2[_rNewLabels1[n1][i].first]+=_rNewLabels1[n1][i].second;
1.113
1.114 switch(MT) {
1.115 case INDUCED:
1.116 - for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i)
1.117 - if(labelTmp1[rInOutLabels1[n1][i].first]>0) {
1.118 + for(unsigned int i = 0; i < _rInOutLabels1[n1].size(); ++i)
1.119 + if(_labelTmp1[_rInOutLabels1[n1][i].first]>0) {
1.120 ret=0;
1.121 break;
1.122 }
1.123 if(ret)
1.124 - for(unsigned int i = 0; i < rNewLabels1[n1].size(); ++i)
1.125 - if(labelTmp2[rNewLabels1[n1][i].first]>0) {
1.126 + for(unsigned int i = 0; i < _rNewLabels1[n1].size(); ++i)
1.127 + if(_labelTmp2[_rNewLabels1[n1][i].first]>0) {
1.128 ret=0;
1.129 break;
1.130 }
1.131 break;
1.132 case SUBGRAPH:
1.133 - for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i)
1.134 - if(labelTmp1[rInOutLabels1[n1][i].first]>0) {
1.135 + for(unsigned int i = 0; i < _rInOutLabels1[n1].size(); ++i)
1.136 + if(_labelTmp1[_rInOutLabels1[n1][i].first]>0) {
1.137 ret=0;
1.138 break;
1.139 }
1.140 break;
1.141 case ISOMORPH:
1.142 - for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i)
1.143 - if(labelTmp1[rInOutLabels1[n1][i].first]!=0) {
1.144 + for(unsigned int i = 0; i < _rInOutLabels1[n1].size(); ++i)
1.145 + if(_labelTmp1[_rInOutLabels1[n1][i].first]!=0) {
1.146 ret=0;
1.147 break;
1.148 }
1.149 if(ret)
1.150 - for(unsigned int i = 0; i < rNewLabels1[n1].size(); ++i)
1.151 - if(labelTmp2[rNewLabels1[n1][i].first]!=0) {
1.152 + for(unsigned int i = 0; i < _rNewLabels1[n1].size(); ++i)
1.153 + if(_labelTmp2[_rNewLabels1[n1][i].first]!=0) {
1.154 ret=0;
1.155 break;
1.156 }
1.157 @@ -212,19 +210,19 @@
1.158 default:
1.159 return false;
1.160 }
1.161 - for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i)
1.162 - labelTmp1[rInOutLabels1[n1][i].first]=0;
1.163 + for(unsigned int i = 0; i < _rInOutLabels1[n1].size(); ++i)
1.164 + _labelTmp1[_rInOutLabels1[n1][i].first]=0;
1.165
1.166 if(MT!=SUBGRAPH)
1.167 - for(unsigned int i = 0; i < rNewLabels1[n1].size(); ++i)
1.168 - labelTmp2[rNewLabels1[n1][i].first]=0;
1.169 + for(unsigned int i = 0; i < _rNewLabels1[n1].size(); ++i)
1.170 + _labelTmp2[_rNewLabels1[n1][i].first]=0;
1.171 }
1.172
1.173 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
1.174 const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
1.175 - labelTmp1[_intLabels2[currNode]]=0;
1.176 + _labelTmp1[_intLabels2[currNode]]=0;
1.177 if(MT!=SUBGRAPH&&_conn[currNode]==0)
1.178 - labelTmp2[_intLabels2[currNode]]=0;
1.179 + _labelTmp2[_intLabels2[currNode]]=0;
1.180 }
1.181
1.182 return ret;
1.183 @@ -310,7 +308,7 @@
1.184 void processBFSLevel(typename G1::Node source,unsigned int& orderIndex,
1.185 typename G1::template NodeMap<int>& dm1,
1.186 typename G1::template NodeMap<bool>& added) {
1.187 - order[orderIndex]=source;
1.188 + _order[orderIndex]=source;
1.189 added[source]=1;
1.190
1.191 unsigned int endPosOfLevel=orderIndex,
1.192 @@ -320,11 +318,11 @@
1.193 typename G1::template NodeMap<int> currConn(_g1,0);
1.194
1.195 while(orderIndex<=lastAdded){
1.196 - typename G1::Node currNode = order[orderIndex];
1.197 + typename G1::Node currNode = _order[orderIndex];
1.198 for(typename G1::IncEdgeIt e(_g1,currNode); e!=INVALID; ++e) {
1.199 typename G1::Node n = _g1.oppositeNode(currNode,e);
1.200 if(!added[n]) {
1.201 - order[++lastAdded]=n;
1.202 + _order[++lastAdded]=n;
1.203 added[n]=1;
1.204 }
1.205 }
1.206 @@ -332,18 +330,18 @@
1.207 for(unsigned int j = startPosOfLevel; j <= endPosOfLevel; ++j) {
1.208 int minInd=j;
1.209 for(unsigned int i = j+1; i <= endPosOfLevel; ++i)
1.210 - if(currConn[order[i]]>currConn[order[minInd]]||
1.211 - (currConn[order[i]]==currConn[order[minInd]]&&
1.212 - (dm1[order[i]]>dm1[order[minInd]]||
1.213 - (dm1[order[i]]==dm1[order[minInd]]&&
1.214 - labelTmp1[_intLabels1[order[minInd]]]>
1.215 - labelTmp1[_intLabels1[order[i]]]))))
1.216 + if(currConn[_order[i]]>currConn[_order[minInd]]||
1.217 + (currConn[_order[i]]==currConn[_order[minInd]]&&
1.218 + (dm1[_order[i]]>dm1[_order[minInd]]||
1.219 + (dm1[_order[i]]==dm1[_order[minInd]]&&
1.220 + _labelTmp1[_intLabels1[_order[minInd]]]>
1.221 + _labelTmp1[_intLabels1[_order[i]]]))))
1.222 minInd=i;
1.223
1.224 - --labelTmp1[_intLabels1[order[minInd]]];
1.225 - for(typename G1::IncEdgeIt e(_g1,order[minInd]); e!=INVALID; ++e)
1.226 - ++currConn[_g1.oppositeNode(order[minInd],e)];
1.227 - std::swap(order[j],order[minInd]);
1.228 + --_labelTmp1[_intLabels1[_order[minInd]]];
1.229 + for(typename G1::IncEdgeIt e(_g1,_order[minInd]); e!=INVALID; ++e)
1.230 + ++currConn[_g1.oppositeNode(_order[minInd],e)];
1.231 + std::swap(_order[j],_order[minInd]);
1.232 }
1.233 startPosOfLevel=endPosOfLevel+1;
1.234 endPosOfLevel=lastAdded;
1.235 @@ -356,7 +354,7 @@
1.236 //we will find pairs for the nodes of g1 in this order
1.237 void setOrder(){
1.238 for(typename G2::NodeIt n2(_g2); n2!=INVALID; ++n2)
1.239 - ++labelTmp1[_intLabels2[n2]];
1.240 + ++_labelTmp1[_intLabels2[n2]];
1.241
1.242 typename G1::template NodeMap<int> dm1(_g1,0);
1.243 for(typename G1::EdgeIt e(_g1); e!=INVALID; ++e) {
1.244 @@ -372,38 +370,38 @@
1.245 typename G1::Node minNode = n;
1.246 for(typename G1::NodeIt n1(_g1,minNode); n1!=INVALID; ++n1)
1.247 if(!added[n1] &&
1.248 - (labelTmp1[_intLabels1[minNode]]>
1.249 - labelTmp1[_intLabels1[n1]]||(dm1[minNode]<dm1[n1]&&
1.250 - labelTmp1[_intLabels1[minNode]]==
1.251 - labelTmp1[_intLabels1[n1]])))
1.252 + (_labelTmp1[_intLabels1[minNode]]>
1.253 + _labelTmp1[_intLabels1[n1]]||(dm1[minNode]<dm1[n1]&&
1.254 + _labelTmp1[_intLabels1[minNode]]==
1.255 + _labelTmp1[_intLabels1[n1]])))
1.256 minNode=n1;
1.257 processBFSLevel(minNode,orderIndex,dm1,added);
1.258 }
1.259 else
1.260 ++n;
1.261 }
1.262 - for(unsigned int i = 0; i < labelTmp1.size(); ++i)
1.263 - labelTmp1[i]=0;
1.264 + for(unsigned int i = 0; i < _labelTmp1.size(); ++i)
1.265 + _labelTmp1[i]=0;
1.266 }
1.267
1.268
1.269 template<MappingType MT>
1.270 bool extMatch(){
1.271 while(_depth>=0) {
1.272 - if(_depth==static_cast<int>(order.size())) {
1.273 + if(_depth==static_cast<int>(_order.size())) {
1.274 //all nodes of g1 are mapped to nodes of g2
1.275 --_depth;
1.276 return true;
1.277 }
1.278 - typename G1::Node& nodeOfDepth = order[_depth];
1.279 + typename G1::Node& nodeOfDepth = _order[_depth];
1.280 const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth];
1.281 - typename G2::IncEdgeIt &edgeItOfDepth = currEdgeIts[_depth];
1.282 + typename G2::IncEdgeIt &edgeItOfDepth = _currEdgeIts[_depth];
1.283 //the node of g2 whose neighbours are the candidates for
1.284 - //the pair of order[_depth]
1.285 + //the pair of _order[_depth]
1.286 typename G2::Node currPNode;
1.287 if(edgeItOfDepth==INVALID){
1.288 typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth);
1.289 - //if _mapping[order[_depth]]!=INVALID, we don't need fstMatchedE
1.290 + //if _mapping[_order[_depth]]!=INVALID, we don't need fstMatchedE
1.291 if(pairOfNodeOfDepth==INVALID) {
1.292 for(; fstMatchedE!=INVALID &&
1.293 _mapping[_g1.oppositeNode(nodeOfDepth,
1.294 @@ -468,34 +466,34 @@
1.295 //calculate the lookup table for cutting the search tree
1.296 void setRNew1tRInOut1t(){
1.297 typename G1::template NodeMap<int> tmp(_g1,0);
1.298 - for(unsigned int i=0; i<order.size(); ++i) {
1.299 - tmp[order[i]]=-1;
1.300 - for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1) {
1.301 - const typename G1::Node currNode=_g1.oppositeNode(order[i],e1);
1.302 + for(unsigned int i=0; i<_order.size(); ++i) {
1.303 + tmp[_order[i]]=-1;
1.304 + for(typename G1::IncEdgeIt e1(_g1,_order[i]); e1!=INVALID; ++e1) {
1.305 + const typename G1::Node currNode=_g1.oppositeNode(_order[i],e1);
1.306 if(tmp[currNode]>0)
1.307 - ++labelTmp1[_intLabels1[currNode]];
1.308 + ++_labelTmp1[_intLabels1[currNode]];
1.309 else if(tmp[currNode]==0)
1.310 - ++labelTmp2[_intLabels1[currNode]];
1.311 + ++_labelTmp2[_intLabels1[currNode]];
1.312 }
1.313 - //labelTmp1[i]=number of neightbours with label i in set rInOut
1.314 - //labelTmp2[i]=number of neightbours with label i in set rNew
1.315 - for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1) {
1.316 - const int& currIntLabel = _intLabels1[_g1.oppositeNode(order[i],e1)];
1.317 - if(labelTmp1[currIntLabel]>0) {
1.318 - rInOutLabels1[order[i]]
1.319 + //_labelTmp1[i]=number of neightbours with label i in set rInOut
1.320 + //_labelTmp2[i]=number of neightbours with label i in set rNew
1.321 + for(typename G1::IncEdgeIt e1(_g1,_order[i]); e1!=INVALID; ++e1) {
1.322 + const int& currIntLabel = _intLabels1[_g1.oppositeNode(_order[i],e1)];
1.323 + if(_labelTmp1[currIntLabel]>0) {
1.324 + _rInOutLabels1[_order[i]]
1.325 .push_back(std::make_pair(currIntLabel,
1.326 - labelTmp1[currIntLabel]));
1.327 - labelTmp1[currIntLabel]=0;
1.328 + _labelTmp1[currIntLabel]));
1.329 + _labelTmp1[currIntLabel]=0;
1.330 }
1.331 - else if(labelTmp2[currIntLabel]>0) {
1.332 - rNewLabels1[order[i]].
1.333 - push_back(std::make_pair(currIntLabel,labelTmp2[currIntLabel]));
1.334 - labelTmp2[currIntLabel]=0;
1.335 + else if(_labelTmp2[currIntLabel]>0) {
1.336 + _rNewLabels1[_order[i]].
1.337 + push_back(std::make_pair(currIntLabel,_labelTmp2[currIntLabel]));
1.338 + _labelTmp2[currIntLabel]=0;
1.339 }
1.340 }
1.341
1.342 - for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1) {
1.343 - int& tmpCurrNode=tmp[_g1.oppositeNode(order[i],e1)];
1.344 + for(typename G1::IncEdgeIt e1(_g1,_order[i]); e1!=INVALID; ++e1) {
1.345 + int& tmpCurrNode=tmp[_g1.oppositeNode(_order[i],e1)];
1.346 if(tmpCurrNode!=-1)
1.347 ++tmpCurrNode;
1.348 }
1.349 @@ -532,10 +530,10 @@
1.350 ///The labels must be the numbers {0,1,2,..,K-1}, where K is the number of
1.351 ///different labels.
1.352 Vf2pp(const G1 &g1, const G2 &g2,M &m, M1 &intLabels1, M2 &intLabels2) :
1.353 - _depth(0), _conn(g2,0), _mapping(m), order(countNodes(g1),INVALID),
1.354 - currEdgeIts(countNodes(g1),INVALID), _g1(g1), _g2(g2), rNewLabels1(_g1),
1.355 - rInOutLabels1(_g1), _intLabels1(intLabels1) ,_intLabels2(intLabels2),
1.356 - maxLabel(getMaxLabel()), labelTmp1(maxLabel+1),labelTmp2(maxLabel+1),
1.357 + _g1(g1), _g2(g2), _depth(0), _mapping(m), _order(countNodes(g1),INVALID),
1.358 + _conn(g2,0), _currEdgeIts(countNodes(g1),INVALID), _rNewLabels1(_g1),
1.359 + _rInOutLabels1(_g1), _intLabels1(intLabels1) ,_intLabels2(intLabels2),
1.360 + _maxLabel(getMaxLabel()), _labelTmp1(_maxLabel+1),_labelTmp2(_maxLabel+1),
1.361 _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0),
1.362 _deallocLabelsAfterUse(0)
1.363 {