1.1 --- a/lemon/vf2pp.h Sat Oct 07 00:14:05 2017 +0200
1.2 +++ b/lemon/vf2pp.h Sat Oct 07 03:18:49 2017 +0200
1.3 @@ -75,7 +75,7 @@
1.4 ///
1.5 ///There is also a \ref vf2pp() "function-type interface" called
1.6 ///\ref vf2pp() for the %VF2 Plus Plus algorithm, which is probably
1.7 - ///more convenient in most use-cases.
1.8 + ///more convenient in most use cases.
1.9 ///
1.10 ///\tparam G1 The type of the graph to be embedded.
1.11 ///The default type is \ref ListDigraph.
1.12 @@ -96,11 +96,8 @@
1.13 #else
1.14 template<class G1=ListDigraph,
1.15 class G2=ListDigraph,
1.16 - class M = typename G1::template NodeMap<G2::Node>,//the mapping
1.17 - //labels of G1,the labels are the numbers {0,1,2,..,K-1},
1.18 - //where K is the number of different labels
1.19 + class M = typename G1::template NodeMap<G2::Node>,
1.20 class M1 = typename G1::template NodeMap<int>,
1.21 - //labels of G2, ...
1.22 class M2 = typename G2::template NodeMap<int> >
1.23 #endif
1.24 class Vf2pp {
1.25 @@ -114,17 +111,17 @@
1.26 //where v1 is a node of G1 and v2 is a node of G2
1.27 M &_mapping;
1.28
1.29 - //order[i] is a node of g1, for which a pair is searched if depth=i
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 ith
1.34 + //currEdgeIts[i] is the last used edge iterator in the i-th
1.35 //depth to find a pair for node order[i]
1.36 std::vector<typename G2::IncEdgeIt> currEdgeIts;
1.37 -
1.38 - //The small graph.
1.39 +
1.40 + //The graph to be embedded
1.41 const G1 &_g1;
1.42
1.43 - //The large graph.
1.44 + //The graph into which g1 is to be embedded
1.45 const G2 &_g2;
1.46
1.47 //rNewLabels1[v] is a pair of form
1.48 @@ -137,24 +134,24 @@
1.49 typename G1::template NodeMap<std::vector<std::pair<int,int> > >
1.50 rInOutLabels1;
1.51
1.52 - //_intLabels1[v]==i means that vertex v has the i label in
1.53 - //_g1 (i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
1.54 + //_intLabels1[v]==i means that node v has label i in _g1
1.55 + //(i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
1.56 M1 &_intLabels1;
1.57
1.58 - //_intLabels2[v]==i means that vertex v has the i label in
1.59 - //_g2 (i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
1.60 + //_intLabels2[v]==i means that node v has label i in _g2
1.61 + //(i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
1.62 M2 &_intLabels2;
1.63
1.64 //largest label
1.65 const int maxLabel;
1.66
1.67 //lookup tables for manipulating with label class cardinalities
1.68 - //after use they have to be reset to 0..0
1.69 + //(after use they have to be reset to 0..0)
1.70 std::vector<int> labelTmp1,labelTmp2;
1.71
1.72 MappingType _mapping_type;
1.73
1.74 - //indicates whether the mapping or the labels must be deleted in the ctor
1.75 + //indicates whether the mapping or the labels must be deleted in the destructor
1.76 bool _deallocMappingAfterUse,_deallocLabelsAfterUse;
1.77
1.78
1.79 @@ -286,8 +283,7 @@
1.80 return isIso&&cutByLabels<MT>(n1,n2);
1.81 }
1.82
1.83 -
1.84 - //matches n1 and n2
1.85 + //maps n1 to n2
1.86 void addPair(const typename G1::Node n1,const typename G2::Node n2) {
1.87 _conn[n2]=-1;
1.88 _mapping.set(n1,n2);
1.89 @@ -298,8 +294,7 @@
1.90 }
1.91 }
1.92
1.93 -
1.94 - //dematches n1 and n2
1.95 + //removes mapping of n1 to n2
1.96 void subPair(const typename G1::Node n1,const typename G2::Node n2) {
1.97 _conn[n2]=0;
1.98 _mapping.set(n1,INVALID);
1.99 @@ -312,7 +307,6 @@
1.100 }
1.101 }
1.102
1.103 -
1.104 void processBFSLevel(typename G1::Node source,unsigned int& orderIndex,
1.105 typename G1::template NodeMap<int>& dm1,
1.106 typename G1::template NodeMap<bool>& added) {
1.107 @@ -364,7 +358,6 @@
1.108 for(typename G2::NodeIt n2(_g2); n2!=INVALID; ++n2)
1.109 ++labelTmp1[_intLabels2[n2]];
1.110
1.111 - // OutDegMap<G1> dm1(_g1);
1.112 typename G1::template NodeMap<int> dm1(_g1,0);
1.113 for(typename G1::EdgeIt e(_g1); e!=INVALID; ++e) {
1.114 ++dm1[_g1.u(e)];
1.115 @@ -397,34 +390,34 @@
1.116 template<MappingType MT>
1.117 bool extMatch(){
1.118 while(_depth>=0) {
1.119 - //there is no node in g1, which has not pair in g2.
1.120 if(_depth==static_cast<int>(order.size())) {
1.121 + //all nodes of g1 are mapped to nodes of g2
1.122 --_depth;
1.123 return true;
1.124 }
1.125 typename G1::Node& nodeOfDepth = order[_depth];
1.126 const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth];
1.127 typename G2::IncEdgeIt &edgeItOfDepth = currEdgeIts[_depth];
1.128 - //the node of g2, which neighbours are the candidates for
1.129 + //the node of g2 whose neighbours are the candidates for
1.130 //the pair of order[_depth]
1.131 typename G2::Node currPNode;
1.132 if(edgeItOfDepth==INVALID){
1.133 typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth);
1.134 - //if _mapping[order[_depth]]!=INVALID, we dont need
1.135 - //fstMatchedE
1.136 - if(pairOfNodeOfDepth==INVALID)
1.137 + //if _mapping[order[_depth]]!=INVALID, we don't need fstMatchedE
1.138 + if(pairOfNodeOfDepth==INVALID) {
1.139 for(; fstMatchedE!=INVALID &&
1.140 _mapping[_g1.oppositeNode(nodeOfDepth,
1.141 fstMatchedE)]==INVALID;
1.142 ++fstMatchedE); //find fstMatchedE, it could be preprocessed
1.143 + }
1.144 if(fstMatchedE==INVALID||pairOfNodeOfDepth!=INVALID) {
1.145 - //We found no covered neighbours, this means
1.146 - //the graph is not connected(or _depth==0). Each
1.147 - //uncovered(and there are some other properties due
1.148 + //We found no covered neighbours, this means that
1.149 + //the graph is not connected (or _depth==0). Each
1.150 + //uncovered (and there are some other properties due
1.151 //to the spec. problem types) node of g2 is
1.152 - //candidate. We can read the iterator of the last
1.153 + //candidate. We can read the iterator of the last
1.154 //tried node from the match if it is not the first
1.155 - //try(match[nodeOfDepth]!=INVALID)
1.156 + //try (match[nodeOfDepth]!=INVALID)
1.157 typename G2::NodeIt n2(_g2);
1.158 //if it's not the first try
1.159 if(pairOfNodeOfDepth!=INVALID) {
1.160 @@ -447,13 +440,13 @@
1.161 --_depth;
1.162 continue;
1.163 }
1.164 - else{
1.165 + else {
1.166 currPNode=_mapping[_g1.oppositeNode(nodeOfDepth,
1.167 fstMatchedE)];
1.168 edgeItOfDepth=typename G2::IncEdgeIt(_g2,currPNode);
1.169 }
1.170 }
1.171 - else{
1.172 + else {
1.173 currPNode=_g2.oppositeNode(pairOfNodeOfDepth,
1.174 edgeItOfDepth);
1.175 subPair(nodeOfDepth,pairOfNodeOfDepth);
1.176 @@ -472,7 +465,7 @@
1.177 return false;
1.178 }
1.179
1.180 - //calc. the lookup table for cutting the searchtree
1.181 + //calculate the lookup table for cutting the search tree
1.182 void setRNew1tRInOut1t(){
1.183 typename G1::template NodeMap<int> tmp(_g1,0);
1.184 for(unsigned int i=0; i<order.size(); ++i) {
1.185 @@ -675,7 +668,7 @@
1.186
1.187 public:
1.188 ///Constructor
1.189 - Vf2ppWizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) { }
1.190 + Vf2ppWizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {}
1.191
1.192 ///Copy constructor
1.193 Vf2ppWizard(const Base &b) : Base(b) {}
1.194 @@ -684,7 +677,7 @@
1.195 template<typename T>
1.196 struct SetMappingBase : public Base {
1.197 typedef T Mapping;
1.198 - SetMappingBase(const Base &b) : Base(b) { }
1.199 + SetMappingBase(const Base &b) : Base(b) {}
1.200 };
1.201
1.202 ///\brief \ref named-templ-param "Named parameter" for setting
1.203 @@ -713,11 +706,11 @@
1.204 ///the node labels.
1.205 ///
1.206 ///\param nodeLabels1 A \ref concepts::ReadMap "readable node map"
1.207 - ///of g1 with integer value. In case of K different labels, the labels
1.208 - ///must be the {0,1,..,K-1} numbers.
1.209 + ///of g1 with integer values. In case of K different labels, the labels
1.210 + ///must be the numbers {0,1,..,K-1}.
1.211 ///\param nodeLabels2 A \ref concepts::ReadMap "readable node map"
1.212 - ///of g2 with integer value. In case of K different labels, the labels
1.213 - ///must be the {0,1,..,K-1} numbers.
1.214 + ///of g2 with integer values. In case of K different labels, the labels
1.215 + ///must be the numbers {0,1,..,K-1}.
1.216 template<typename NL1, typename NL2>
1.217 Vf2ppWizard< SetNodeLabelsBase<NL1,NL2> >
1.218 nodeLabels(const NL1 &nodeLabels1, const NL2 &nodeLabels2) {
1.219 @@ -877,7 +870,7 @@
1.220 /// int num_isos = vf2pp(g1,g2).iso().count();
1.221 ///
1.222 /// // Iterate through all the induced subgraph mappings
1.223 - /// //of graph g1 into g2 using the labels c1 and c2
1.224 + /// // of graph g1 into g2 using the labels c1 and c2
1.225 /// auto* myVf2pp = vf2pp(g1,g2).mapping(m).nodeLabels(c1,c2)
1.226 /// .induced().getPtrToVf2Object();
1.227 /// while(myVf2pp->find()){