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)