1.1 --- a/lemon/vf2.h Sat Oct 07 03:18:49 2017 +0200
1.2 +++ b/lemon/vf2.h Sat Oct 07 15:45:56 2017 +0200
1.3 @@ -112,35 +112,35 @@
1.4 class NEQ = bits::vf2::AlwaysEq >
1.5 #endif
1.6 class Vf2 {
1.7 - //Current depth in the DFS tree.
1.8 - int _depth;
1.9 -
1.10 - //Functor with bool operator()(G1::Node,G2::Node), which returns 1
1.11 - //if and only if the two nodes are equivalent
1.12 - NEQ _nEq;
1.13 -
1.14 - //_conn[v2] = number of covered neighbours of v2
1.15 - typename G2::template NodeMap<int> _conn;
1.16 -
1.17 - //The current mapping. _mapping[v1]=v2 iff v1 has been mapped to v2,
1.18 - //where v1 is a node of G1 and v2 is a node of G2
1.19 - M &_mapping;
1.20 -
1.21 - //order[i] is the node of g1 for which a pair is searched if depth=i
1.22 - std::vector<typename G1::Node> order;
1.23 -
1.24 - //currEdgeIts[i] is the last used edge iterator in the i-th
1.25 - //depth to find a pair for node order[i]
1.26 - std::vector<typename G2::IncEdgeIt> currEdgeIts;
1.27 -
1.28 //The graph to be embedded
1.29 const G1 &_g1;
1.30
1.31 //The graph into which g1 is to be embedded
1.32 const G2 &_g2;
1.33
1.34 + //Functor with bool operator()(G1::Node,G2::Node), which returns 1
1.35 + //if and only if the two nodes are equivalent
1.36 + NEQ _nEq;
1.37 +
1.38 + //Current depth in the DFS tree.
1.39 + int _depth;
1.40 +
1.41 + //The current mapping. _mapping[v1]=v2 iff v1 has been mapped to v2,
1.42 + //where v1 is a node of G1 and v2 is a node of G2
1.43 + M &_mapping;
1.44 +
1.45 + //_order[i] is the node of g1 for which a pair is searched if depth=i
1.46 + std::vector<typename G1::Node> _order;
1.47 +
1.48 + //_conn[v2] = number of covered neighbours of v2
1.49 + typename G2::template NodeMap<int> _conn;
1.50 +
1.51 + //_currEdgeIts[i] is the last used edge iterator in the i-th
1.52 + //depth to find a pair for node _order[i]
1.53 + std::vector<typename G2::IncEdgeIt> _currEdgeIts;
1.54 +
1.55 //lookup tables for cutting the searchtree
1.56 - typename G1::template NodeMap<int> rNew1t,rInOut1t;
1.57 + typename G1::template NodeMap<int> _rNew1t, _rInOut1t;
1.58
1.59 MappingType _mapping_type;
1.60
1.61 @@ -159,11 +159,11 @@
1.62 }
1.63 switch(MT) {
1.64 case INDUCED:
1.65 - return rInOut1t[n1]<=rInOut2&&rNew1t[n1]<=rNew2;
1.66 + return _rInOut1t[n1]<=rInOut2&&_rNew1t[n1]<=rNew2;
1.67 case SUBGRAPH:
1.68 - return rInOut1t[n1]<=rInOut2;
1.69 + return _rInOut1t[n1]<=rInOut2;
1.70 case ISOMORPH:
1.71 - return rInOut1t[n1]==rInOut2&&rNew1t[n1]==rNew2;
1.72 + return _rInOut1t[n1]==rInOut2&&_rNew1t[n1]==rNew2;
1.73 default:
1.74 return false;
1.75 }
1.76 @@ -235,12 +235,12 @@
1.77 void setOrder() {
1.78 // we will find pairs for the nodes of g1 in this order
1.79
1.80 - // bits::vf2::DfsLeaveOrder<G1> v(_g1,order);
1.81 + // bits::vf2::DfsLeaveOrder<G1> v(_g1,_order);
1.82 // DfsVisit<G1,bits::vf2::DfsLeaveOrder<G1> >dfs(_g1, v);
1.83 // dfs.run();
1.84
1.85 //it is more efficient in practice than DFS
1.86 - bits::vf2::BfsLeaveOrder<G1> v(_g1,order);
1.87 + bits::vf2::BfsLeaveOrder<G1> v(_g1,_order);
1.88 BfsVisit<G1,bits::vf2::BfsLeaveOrder<G1> >bfs(_g1, v);
1.89 bfs.run();
1.90 }
1.91 @@ -248,14 +248,14 @@
1.92 template<MappingType MT>
1.93 bool extMatch() {
1.94 while(_depth>=0) {
1.95 - if(_depth==static_cast<int>(order.size())) {
1.96 + if(_depth==static_cast<int>(_order.size())) {
1.97 //all nodes of g1 are mapped to nodes of g2
1.98 --_depth;
1.99 return true;
1.100 }
1.101 - typename G1::Node& nodeOfDepth = order[_depth];
1.102 + typename G1::Node& nodeOfDepth = _order[_depth];
1.103 const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth];
1.104 - typename G2::IncEdgeIt &edgeItOfDepth = currEdgeIts[_depth];
1.105 + typename G2::IncEdgeIt &edgeItOfDepth = _currEdgeIts[_depth];
1.106 //the node of g2 whose neighbours are the candidates for
1.107 //the pair of nodeOfDepth
1.108 typename G2::Node currPNode;
1.109 @@ -326,15 +326,15 @@
1.110 //calculate the lookup table for cutting the search tree
1.111 void setRNew1tRInOut1t() {
1.112 typename G1::template NodeMap<int> tmp(_g1,0);
1.113 - for(unsigned int i=0; i<order.size(); ++i) {
1.114 - const typename G1::Node& orderI = order[i];
1.115 + for(unsigned int i=0; i<_order.size(); ++i) {
1.116 + const typename G1::Node& orderI = _order[i];
1.117 tmp[orderI]=-1;
1.118 for(typename G1::IncEdgeIt e1(_g1,orderI); e1!=INVALID; ++e1) {
1.119 const typename G1::Node currNode=_g1.oppositeNode(orderI,e1);
1.120 if(tmp[currNode]>0)
1.121 - ++rInOut1t[orderI];
1.122 + ++_rInOut1t[orderI];
1.123 else if(tmp[currNode]==0)
1.124 - ++rNew1t[orderI];
1.125 + ++_rNew1t[orderI];
1.126 }
1.127 for(typename G1::IncEdgeIt e1(_g1,orderI); e1!=INVALID; ++e1) {
1.128 const typename G1::Node currNode=_g1.oppositeNode(orderI,e1);
1.129 @@ -355,11 +355,11 @@
1.130 ///\param neq A bool-valued binary functor determining whether a node is
1.131 ///mappable to another. By default it is an always true operator.
1.132 Vf2(const G1 &g1, const G2 &g2, M &m, const NEQ &neq = NEQ() ) :
1.133 - _nEq(neq), _conn(g2,0), _mapping(m), order(countNodes(g1)),
1.134 - currEdgeIts(countNodes(g1),INVALID), _g1(g1), _g2(g2), rNew1t(g1,0),
1.135 - rInOut1t(g1,0), _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0)
1.136 + _g1(g1), _g2(g2), _nEq(neq), _depth(0), _mapping(m),
1.137 + _order(countNodes(g1)), _conn(g2,0),
1.138 + _currEdgeIts(countNodes(g1),INVALID), _rNew1t(g1,0), _rInOut1t(g1,0),
1.139 + _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0)
1.140 {
1.141 - _depth=0;
1.142 setOrder();
1.143 setRNew1tRInOut1t();
1.144 for(typename G1::NodeIt n(g1);n!=INVALID;++n)
2.1 --- a/lemon/vf2pp.h Sat Oct 07 03:18:49 2017 +0200
2.2 +++ b/lemon/vf2pp.h Sat Oct 07 15:45:56 2017 +0200
2.3 @@ -28,12 +28,10 @@
2.4 #include <lemon/bfs.h>
2.5 #include <lemon/bits/vf2_internals.h>
2.6
2.7 -
2.8 #include <vector>
2.9 #include <algorithm>
2.10 #include <utility>
2.11
2.12 -
2.13 namespace lemon {
2.14 namespace bits {
2.15 namespace vf2pp {
2.16 @@ -101,38 +99,38 @@
2.17 class M2 = typename G2::template NodeMap<int> >
2.18 #endif
2.19 class Vf2pp {
2.20 - //Current depth in the search tree.
2.21 - int _depth;
2.22 -
2.23 - //_conn[v2] = number of covered neighbours of v2
2.24 - typename G2::template NodeMap<int> _conn;
2.25 -
2.26 - //The current mapping. _mapping[v1]=v2 iff v1 has been mapped to v2,
2.27 - //where v1 is a node of G1 and v2 is a node of G2
2.28 - M &_mapping;
2.29 -
2.30 - //order[i] is a node of g1 for which a pair is searched if depth=i
2.31 - std::vector<typename G1::Node> order;
2.32 -
2.33 - //currEdgeIts[i] is the last used edge iterator in the i-th
2.34 - //depth to find a pair for node order[i]
2.35 - std::vector<typename G2::IncEdgeIt> currEdgeIts;
2.36 -
2.37 //The graph to be embedded
2.38 const G1 &_g1;
2.39
2.40 //The graph into which g1 is to be embedded
2.41 const G2 &_g2;
2.42
2.43 - //rNewLabels1[v] is a pair of form
2.44 + //Current depth in the search tree.
2.45 + int _depth;
2.46 +
2.47 + //The current mapping. _mapping[v1]=v2 iff v1 has been mapped to v2,
2.48 + //where v1 is a node of G1 and v2 is a node of G2
2.49 + M &_mapping;
2.50 +
2.51 + //_order[i] is a node of g1 for which a pair is searched if depth=i
2.52 + std::vector<typename G1::Node> _order;
2.53 +
2.54 + //_conn[v2] = number of covered neighbours of v2
2.55 + typename G2::template NodeMap<int> _conn;
2.56 +
2.57 + //_currEdgeIts[i] is the last used edge iterator in the i-th
2.58 + //depth to find a pair for node _order[i]
2.59 + std::vector<typename G2::IncEdgeIt> _currEdgeIts;
2.60 +
2.61 + //_rNewLabels1[v] is a pair of form
2.62 //(label; num. of uncov. nodes with such label and no covered neighbours)
2.63 typename G1::template NodeMap<std::vector<std::pair<int,int> > >
2.64 - rNewLabels1;
2.65 + _rNewLabels1;
2.66
2.67 - //rInOutLabels1[v] is the number of covered neighbours of v for each label
2.68 + //_rInOutLabels1[v] is the number of covered neighbours of v for each label
2.69 //in form (label,number of such labels)
2.70 typename G1::template NodeMap<std::vector<std::pair<int,int> > >
2.71 - rInOutLabels1;
2.72 + _rInOutLabels1;
2.73
2.74 //_intLabels1[v]==i means that node v has label i in _g1
2.75 //(i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
2.76 @@ -143,11 +141,11 @@
2.77 M2 &_intLabels2;
2.78
2.79 //largest label
2.80 - const int maxLabel;
2.81 + const int _maxLabel;
2.82
2.83 //lookup tables for manipulating with label class cardinalities
2.84 //(after use they have to be reset to 0..0)
2.85 - std::vector<int> labelTmp1,labelTmp2;
2.86 + std::vector<int> _labelTmp1,_labelTmp2;
2.87
2.88 MappingType _mapping_type;
2.89
2.90 @@ -161,50 +159,50 @@
2.91 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
2.92 const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
2.93 if(_conn[currNode]>0)
2.94 - --labelTmp1[_intLabels2[currNode]];
2.95 + --_labelTmp1[_intLabels2[currNode]];
2.96 else if(MT!=SUBGRAPH&&_conn[currNode]==0)
2.97 - --labelTmp2[_intLabels2[currNode]];
2.98 + --_labelTmp2[_intLabels2[currNode]];
2.99 }
2.100
2.101 bool ret=1;
2.102 if(ret) {
2.103 - for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i)
2.104 - labelTmp1[rInOutLabels1[n1][i].first]+=rInOutLabels1[n1][i].second;
2.105 + for(unsigned int i = 0; i < _rInOutLabels1[n1].size(); ++i)
2.106 + _labelTmp1[_rInOutLabels1[n1][i].first]+=_rInOutLabels1[n1][i].second;
2.107
2.108 if(MT!=SUBGRAPH)
2.109 - for(unsigned int i = 0; i < rNewLabels1[n1].size(); ++i)
2.110 - labelTmp2[rNewLabels1[n1][i].first]+=rNewLabels1[n1][i].second;
2.111 + for(unsigned int i = 0; i < _rNewLabels1[n1].size(); ++i)
2.112 + _labelTmp2[_rNewLabels1[n1][i].first]+=_rNewLabels1[n1][i].second;
2.113
2.114 switch(MT) {
2.115 case INDUCED:
2.116 - for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i)
2.117 - if(labelTmp1[rInOutLabels1[n1][i].first]>0) {
2.118 + for(unsigned int i = 0; i < _rInOutLabels1[n1].size(); ++i)
2.119 + if(_labelTmp1[_rInOutLabels1[n1][i].first]>0) {
2.120 ret=0;
2.121 break;
2.122 }
2.123 if(ret)
2.124 - for(unsigned int i = 0; i < rNewLabels1[n1].size(); ++i)
2.125 - if(labelTmp2[rNewLabels1[n1][i].first]>0) {
2.126 + for(unsigned int i = 0; i < _rNewLabels1[n1].size(); ++i)
2.127 + if(_labelTmp2[_rNewLabels1[n1][i].first]>0) {
2.128 ret=0;
2.129 break;
2.130 }
2.131 break;
2.132 case SUBGRAPH:
2.133 - for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i)
2.134 - if(labelTmp1[rInOutLabels1[n1][i].first]>0) {
2.135 + for(unsigned int i = 0; i < _rInOutLabels1[n1].size(); ++i)
2.136 + if(_labelTmp1[_rInOutLabels1[n1][i].first]>0) {
2.137 ret=0;
2.138 break;
2.139 }
2.140 break;
2.141 case ISOMORPH:
2.142 - for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i)
2.143 - if(labelTmp1[rInOutLabels1[n1][i].first]!=0) {
2.144 + for(unsigned int i = 0; i < _rInOutLabels1[n1].size(); ++i)
2.145 + if(_labelTmp1[_rInOutLabels1[n1][i].first]!=0) {
2.146 ret=0;
2.147 break;
2.148 }
2.149 if(ret)
2.150 - for(unsigned int i = 0; i < rNewLabels1[n1].size(); ++i)
2.151 - if(labelTmp2[rNewLabels1[n1][i].first]!=0) {
2.152 + for(unsigned int i = 0; i < _rNewLabels1[n1].size(); ++i)
2.153 + if(_labelTmp2[_rNewLabels1[n1][i].first]!=0) {
2.154 ret=0;
2.155 break;
2.156 }
2.157 @@ -212,19 +210,19 @@
2.158 default:
2.159 return false;
2.160 }
2.161 - for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i)
2.162 - labelTmp1[rInOutLabels1[n1][i].first]=0;
2.163 + for(unsigned int i = 0; i < _rInOutLabels1[n1].size(); ++i)
2.164 + _labelTmp1[_rInOutLabels1[n1][i].first]=0;
2.165
2.166 if(MT!=SUBGRAPH)
2.167 - for(unsigned int i = 0; i < rNewLabels1[n1].size(); ++i)
2.168 - labelTmp2[rNewLabels1[n1][i].first]=0;
2.169 + for(unsigned int i = 0; i < _rNewLabels1[n1].size(); ++i)
2.170 + _labelTmp2[_rNewLabels1[n1][i].first]=0;
2.171 }
2.172
2.173 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
2.174 const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
2.175 - labelTmp1[_intLabels2[currNode]]=0;
2.176 + _labelTmp1[_intLabels2[currNode]]=0;
2.177 if(MT!=SUBGRAPH&&_conn[currNode]==0)
2.178 - labelTmp2[_intLabels2[currNode]]=0;
2.179 + _labelTmp2[_intLabels2[currNode]]=0;
2.180 }
2.181
2.182 return ret;
2.183 @@ -310,7 +308,7 @@
2.184 void processBFSLevel(typename G1::Node source,unsigned int& orderIndex,
2.185 typename G1::template NodeMap<int>& dm1,
2.186 typename G1::template NodeMap<bool>& added) {
2.187 - order[orderIndex]=source;
2.188 + _order[orderIndex]=source;
2.189 added[source]=1;
2.190
2.191 unsigned int endPosOfLevel=orderIndex,
2.192 @@ -320,11 +318,11 @@
2.193 typename G1::template NodeMap<int> currConn(_g1,0);
2.194
2.195 while(orderIndex<=lastAdded){
2.196 - typename G1::Node currNode = order[orderIndex];
2.197 + typename G1::Node currNode = _order[orderIndex];
2.198 for(typename G1::IncEdgeIt e(_g1,currNode); e!=INVALID; ++e) {
2.199 typename G1::Node n = _g1.oppositeNode(currNode,e);
2.200 if(!added[n]) {
2.201 - order[++lastAdded]=n;
2.202 + _order[++lastAdded]=n;
2.203 added[n]=1;
2.204 }
2.205 }
2.206 @@ -332,18 +330,18 @@
2.207 for(unsigned int j = startPosOfLevel; j <= endPosOfLevel; ++j) {
2.208 int minInd=j;
2.209 for(unsigned int i = j+1; i <= endPosOfLevel; ++i)
2.210 - if(currConn[order[i]]>currConn[order[minInd]]||
2.211 - (currConn[order[i]]==currConn[order[minInd]]&&
2.212 - (dm1[order[i]]>dm1[order[minInd]]||
2.213 - (dm1[order[i]]==dm1[order[minInd]]&&
2.214 - labelTmp1[_intLabels1[order[minInd]]]>
2.215 - labelTmp1[_intLabels1[order[i]]]))))
2.216 + if(currConn[_order[i]]>currConn[_order[minInd]]||
2.217 + (currConn[_order[i]]==currConn[_order[minInd]]&&
2.218 + (dm1[_order[i]]>dm1[_order[minInd]]||
2.219 + (dm1[_order[i]]==dm1[_order[minInd]]&&
2.220 + _labelTmp1[_intLabels1[_order[minInd]]]>
2.221 + _labelTmp1[_intLabels1[_order[i]]]))))
2.222 minInd=i;
2.223
2.224 - --labelTmp1[_intLabels1[order[minInd]]];
2.225 - for(typename G1::IncEdgeIt e(_g1,order[minInd]); e!=INVALID; ++e)
2.226 - ++currConn[_g1.oppositeNode(order[minInd],e)];
2.227 - std::swap(order[j],order[minInd]);
2.228 + --_labelTmp1[_intLabels1[_order[minInd]]];
2.229 + for(typename G1::IncEdgeIt e(_g1,_order[minInd]); e!=INVALID; ++e)
2.230 + ++currConn[_g1.oppositeNode(_order[minInd],e)];
2.231 + std::swap(_order[j],_order[minInd]);
2.232 }
2.233 startPosOfLevel=endPosOfLevel+1;
2.234 endPosOfLevel=lastAdded;
2.235 @@ -356,7 +354,7 @@
2.236 //we will find pairs for the nodes of g1 in this order
2.237 void setOrder(){
2.238 for(typename G2::NodeIt n2(_g2); n2!=INVALID; ++n2)
2.239 - ++labelTmp1[_intLabels2[n2]];
2.240 + ++_labelTmp1[_intLabels2[n2]];
2.241
2.242 typename G1::template NodeMap<int> dm1(_g1,0);
2.243 for(typename G1::EdgeIt e(_g1); e!=INVALID; ++e) {
2.244 @@ -372,38 +370,38 @@
2.245 typename G1::Node minNode = n;
2.246 for(typename G1::NodeIt n1(_g1,minNode); n1!=INVALID; ++n1)
2.247 if(!added[n1] &&
2.248 - (labelTmp1[_intLabels1[minNode]]>
2.249 - labelTmp1[_intLabels1[n1]]||(dm1[minNode]<dm1[n1]&&
2.250 - labelTmp1[_intLabels1[minNode]]==
2.251 - labelTmp1[_intLabels1[n1]])))
2.252 + (_labelTmp1[_intLabels1[minNode]]>
2.253 + _labelTmp1[_intLabels1[n1]]||(dm1[minNode]<dm1[n1]&&
2.254 + _labelTmp1[_intLabels1[minNode]]==
2.255 + _labelTmp1[_intLabels1[n1]])))
2.256 minNode=n1;
2.257 processBFSLevel(minNode,orderIndex,dm1,added);
2.258 }
2.259 else
2.260 ++n;
2.261 }
2.262 - for(unsigned int i = 0; i < labelTmp1.size(); ++i)
2.263 - labelTmp1[i]=0;
2.264 + for(unsigned int i = 0; i < _labelTmp1.size(); ++i)
2.265 + _labelTmp1[i]=0;
2.266 }
2.267
2.268
2.269 template<MappingType MT>
2.270 bool extMatch(){
2.271 while(_depth>=0) {
2.272 - if(_depth==static_cast<int>(order.size())) {
2.273 + if(_depth==static_cast<int>(_order.size())) {
2.274 //all nodes of g1 are mapped to nodes of g2
2.275 --_depth;
2.276 return true;
2.277 }
2.278 - typename G1::Node& nodeOfDepth = order[_depth];
2.279 + typename G1::Node& nodeOfDepth = _order[_depth];
2.280 const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth];
2.281 - typename G2::IncEdgeIt &edgeItOfDepth = currEdgeIts[_depth];
2.282 + typename G2::IncEdgeIt &edgeItOfDepth = _currEdgeIts[_depth];
2.283 //the node of g2 whose neighbours are the candidates for
2.284 - //the pair of order[_depth]
2.285 + //the pair of _order[_depth]
2.286 typename G2::Node currPNode;
2.287 if(edgeItOfDepth==INVALID){
2.288 typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth);
2.289 - //if _mapping[order[_depth]]!=INVALID, we don't need fstMatchedE
2.290 + //if _mapping[_order[_depth]]!=INVALID, we don't need fstMatchedE
2.291 if(pairOfNodeOfDepth==INVALID) {
2.292 for(; fstMatchedE!=INVALID &&
2.293 _mapping[_g1.oppositeNode(nodeOfDepth,
2.294 @@ -468,34 +466,34 @@
2.295 //calculate the lookup table for cutting the search tree
2.296 void setRNew1tRInOut1t(){
2.297 typename G1::template NodeMap<int> tmp(_g1,0);
2.298 - for(unsigned int i=0; i<order.size(); ++i) {
2.299 - tmp[order[i]]=-1;
2.300 - for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1) {
2.301 - const typename G1::Node currNode=_g1.oppositeNode(order[i],e1);
2.302 + for(unsigned int i=0; i<_order.size(); ++i) {
2.303 + tmp[_order[i]]=-1;
2.304 + for(typename G1::IncEdgeIt e1(_g1,_order[i]); e1!=INVALID; ++e1) {
2.305 + const typename G1::Node currNode=_g1.oppositeNode(_order[i],e1);
2.306 if(tmp[currNode]>0)
2.307 - ++labelTmp1[_intLabels1[currNode]];
2.308 + ++_labelTmp1[_intLabels1[currNode]];
2.309 else if(tmp[currNode]==0)
2.310 - ++labelTmp2[_intLabels1[currNode]];
2.311 + ++_labelTmp2[_intLabels1[currNode]];
2.312 }
2.313 - //labelTmp1[i]=number of neightbours with label i in set rInOut
2.314 - //labelTmp2[i]=number of neightbours with label i in set rNew
2.315 - for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1) {
2.316 - const int& currIntLabel = _intLabels1[_g1.oppositeNode(order[i],e1)];
2.317 - if(labelTmp1[currIntLabel]>0) {
2.318 - rInOutLabels1[order[i]]
2.319 + //_labelTmp1[i]=number of neightbours with label i in set rInOut
2.320 + //_labelTmp2[i]=number of neightbours with label i in set rNew
2.321 + for(typename G1::IncEdgeIt e1(_g1,_order[i]); e1!=INVALID; ++e1) {
2.322 + const int& currIntLabel = _intLabels1[_g1.oppositeNode(_order[i],e1)];
2.323 + if(_labelTmp1[currIntLabel]>0) {
2.324 + _rInOutLabels1[_order[i]]
2.325 .push_back(std::make_pair(currIntLabel,
2.326 - labelTmp1[currIntLabel]));
2.327 - labelTmp1[currIntLabel]=0;
2.328 + _labelTmp1[currIntLabel]));
2.329 + _labelTmp1[currIntLabel]=0;
2.330 }
2.331 - else if(labelTmp2[currIntLabel]>0) {
2.332 - rNewLabels1[order[i]].
2.333 - push_back(std::make_pair(currIntLabel,labelTmp2[currIntLabel]));
2.334 - labelTmp2[currIntLabel]=0;
2.335 + else if(_labelTmp2[currIntLabel]>0) {
2.336 + _rNewLabels1[_order[i]].
2.337 + push_back(std::make_pair(currIntLabel,_labelTmp2[currIntLabel]));
2.338 + _labelTmp2[currIntLabel]=0;
2.339 }
2.340 }
2.341
2.342 - for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1) {
2.343 - int& tmpCurrNode=tmp[_g1.oppositeNode(order[i],e1)];
2.344 + for(typename G1::IncEdgeIt e1(_g1,_order[i]); e1!=INVALID; ++e1) {
2.345 + int& tmpCurrNode=tmp[_g1.oppositeNode(_order[i],e1)];
2.346 if(tmpCurrNode!=-1)
2.347 ++tmpCurrNode;
2.348 }
2.349 @@ -532,10 +530,10 @@
2.350 ///The labels must be the numbers {0,1,2,..,K-1}, where K is the number of
2.351 ///different labels.
2.352 Vf2pp(const G1 &g1, const G2 &g2,M &m, M1 &intLabels1, M2 &intLabels2) :
2.353 - _depth(0), _conn(g2,0), _mapping(m), order(countNodes(g1),INVALID),
2.354 - currEdgeIts(countNodes(g1),INVALID), _g1(g1), _g2(g2), rNewLabels1(_g1),
2.355 - rInOutLabels1(_g1), _intLabels1(intLabels1) ,_intLabels2(intLabels2),
2.356 - maxLabel(getMaxLabel()), labelTmp1(maxLabel+1),labelTmp2(maxLabel+1),
2.357 + _g1(g1), _g2(g2), _depth(0), _mapping(m), _order(countNodes(g1),INVALID),
2.358 + _conn(g2,0), _currEdgeIts(countNodes(g1),INVALID), _rNewLabels1(_g1),
2.359 + _rInOutLabels1(_g1), _intLabels1(intLabels1) ,_intLabels2(intLabels2),
2.360 + _maxLabel(getMaxLabel()), _labelTmp1(_maxLabel+1),_labelTmp2(_maxLabel+1),
2.361 _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0),
2.362 _deallocLabelsAfterUse(0)
2.363 {