1.1 --- a/lemon/bits/vf2_internals.h Sat Oct 07 00:14:05 2017 +0200
1.2 +++ b/lemon/bits/vf2_internals.h Sat Oct 07 03:18:49 2017 +0200
1.3 @@ -26,7 +26,7 @@
1.4 namespace lemon {
1.5 ///\ingroup graph_isomorphism
1.6 ///The \ref Vf2 "VF2" algorithm is capable of finding different kind of
1.7 - ///embeddings, this enum specifies its type.
1.8 + ///graph embeddings, this enum specifies their types.
1.9 ///
1.10 ///See \ref graph_isomorphism for a more detailed description.
1.11 enum MappingType {
1.12 @@ -35,13 +35,12 @@
1.13 /// Induced subgraph isomorphism
1.14 INDUCED = 1,
1.15 /// Graph isomorphism
1.16 -
1.17 - /// If the two graph has the same number of nodes, than it is
1.18 + ///
1.19 + /// If the two graphs have the same number of nodes, than it is
1.20 /// equivalent to \ref INDUCED, and if they also have the same
1.21 /// number of edges, then it is also equivalent to \ref SUBGRAPH.
1.22 ///
1.23 - /// However, using this setting is faster than the other two
1.24 - /// options.
1.25 + /// However, using this setting is faster than the other two options.
1.26 ISOMORPH = 2
1.27 };
1.28 }
2.1 --- a/lemon/vf2.h Sat Oct 07 00:14:05 2017 +0200
2.2 +++ b/lemon/vf2.h Sat Oct 07 03:18:49 2017 +0200
2.3 @@ -53,8 +53,6 @@
2.4 }
2.5 };
2.6
2.7 -
2.8 -
2.9 template <class G>
2.10 class DfsLeaveOrder : public DfsVisitor<G> {
2.11 const G &_g;
2.12 @@ -93,7 +91,7 @@
2.13 ///
2.14 ///There is also a \ref vf2() "function-type interface" called \ref vf2()
2.15 ///for the %VF2 algorithm, which is probably more convenient in most
2.16 - ///use-cases.
2.17 + ///use cases.
2.18 ///
2.19 ///\tparam G1 The type of the graph to be embedded.
2.20 ///The default type is \ref ListDigraph.
2.21 @@ -102,7 +100,7 @@
2.22 ///\tparam M The type of the NodeMap storing the mapping.
2.23 ///By default, it is G1::NodeMap<G2::Node>
2.24 ///\tparam NEQ A bool-valued binary functor determinining whether a node is
2.25 - ///mappable to another. By default it is an always true operator.
2.26 + ///mappable to another. By default, it is an always-true operator.
2.27 ///
2.28 ///\sa vf2()
2.29 #ifdef DOXYGEN
2.30 @@ -116,23 +114,31 @@
2.31 class Vf2 {
2.32 //Current depth in the DFS tree.
2.33 int _depth;
2.34 +
2.35 //Functor with bool operator()(G1::Node,G2::Node), which returns 1
2.36 - //ifff the two nodes are equivalent.
2.37 + //if and only if the two nodes are equivalent
2.38 NEQ _nEq;
2.39
2.40 + //_conn[v2] = number of covered neighbours of v2
2.41 typename G2::template NodeMap<int> _conn;
2.42 - //Current mapping. We index it by the nodes of g1, and match[v] is
2.43 - //a node of g2.
2.44 +
2.45 + //The current mapping. _mapping[v1]=v2 iff v1 has been mapped to v2,
2.46 + //where v1 is a node of G1 and v2 is a node of G2
2.47 M &_mapping;
2.48 - //order[i] is the node of g1, for which we search a pair if depth=i
2.49 +
2.50 + //order[i] is the node of g1 for which a pair is searched if depth=i
2.51 std::vector<typename G1::Node> order;
2.52 - //currEdgeIts[i] is an edge iterator, witch is last used in the ith
2.53 - //depth to find a pair for order[i].
2.54 +
2.55 + //currEdgeIts[i] is the last used edge iterator in the i-th
2.56 + //depth to find a pair for node order[i]
2.57 std::vector<typename G2::IncEdgeIt> currEdgeIts;
2.58 - //The small graph.
2.59 +
2.60 + //The graph to be embedded
2.61 const G1 &_g1;
2.62 - //The large graph.
2.63 +
2.64 + //The graph into which g1 is to be embedded
2.65 const G2 &_g2;
2.66 +
2.67 //lookup tables for cutting the searchtree
2.68 typename G1::template NodeMap<int> rNew1t,rInOut1t;
2.69
2.70 @@ -242,34 +248,34 @@
2.71 template<MappingType MT>
2.72 bool extMatch() {
2.73 while(_depth>=0) {
2.74 - //there are not nodes in g1, which has not pair in g2.
2.75 if(_depth==static_cast<int>(order.size())) {
2.76 + //all nodes of g1 are mapped to nodes of g2
2.77 --_depth;
2.78 return true;
2.79 }
2.80 typename G1::Node& nodeOfDepth = order[_depth];
2.81 const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth];
2.82 typename G2::IncEdgeIt &edgeItOfDepth = currEdgeIts[_depth];
2.83 - //the node of g2, which neighbours are the candidates for
2.84 + //the node of g2 whose neighbours are the candidates for
2.85 //the pair of nodeOfDepth
2.86 typename G2::Node currPNode;
2.87 if(edgeItOfDepth==INVALID) {
2.88 typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth);
2.89 - //if pairOfNodeOfDepth!=INVALID, we dont use
2.90 - //fstMatchedE
2.91 - if(pairOfNodeOfDepth==INVALID)
2.92 + //if pairOfNodeOfDepth!=INVALID, we don't use fstMatchedE
2.93 + if(pairOfNodeOfDepth==INVALID) {
2.94 for(; fstMatchedE!=INVALID &&
2.95 _mapping[_g1.oppositeNode(nodeOfDepth,
2.96 fstMatchedE)]==INVALID;
2.97 ++fstMatchedE) ; //find fstMatchedE
2.98 + }
2.99 if(fstMatchedE==INVALID||pairOfNodeOfDepth!=INVALID) {
2.100 - //We found no covered neighbours, this means
2.101 - //the graph is not connected(or _depth==0). Each
2.102 - //uncovered(and there are some other properties due
2.103 + //We found no covered neighbours, this means that
2.104 + //the graph is not connected (or _depth==0). Each
2.105 + //uncovered (and there are some other properties due
2.106 //to the spec. problem types) node of g2 is
2.107 - //candidate. We can read the iterator of the last
2.108 + //candidate. We can read the iterator of the last
2.109 //tried node from the match if it is not the first
2.110 - //try(match[nodeOfDepth]!=INVALID)
2.111 + //try (match[nodeOfDepth]!=INVALID)
2.112 typename G2::NodeIt n2(_g2);
2.113 //if it's not the first try
2.114 if(pairOfNodeOfDepth!=INVALID) {
2.115 @@ -317,7 +323,7 @@
2.116 return false;
2.117 }
2.118
2.119 - //calc. the lookup table for cut the searchtree
2.120 + //calculate the lookup table for cutting the search tree
2.121 void setRNew1tRInOut1t() {
2.122 typename G1::template NodeMap<int> tmp(_g1,0);
2.123 for(unsigned int i=0; i<order.size(); ++i) {
2.124 @@ -351,7 +357,8 @@
2.125 Vf2(const G1 &g1, const G2 &g2, M &m, const NEQ &neq = NEQ() ) :
2.126 _nEq(neq), _conn(g2,0), _mapping(m), order(countNodes(g1)),
2.127 currEdgeIts(countNodes(g1),INVALID), _g1(g1), _g2(g2), rNew1t(g1,0),
2.128 - rInOut1t(g1,0), _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0) {
2.129 + rInOut1t(g1,0), _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0)
2.130 + {
2.131 _depth=0;
2.132 setOrder();
2.133 setRNew1tRInOut1t();
2.134 @@ -440,11 +447,11 @@
2.135
2.136
2.137 /// Auxiliary class for the function-type interface of %VF2 algorithm.
2.138 -
2.139 + ///
2.140 /// This auxiliary class implements the named parameters of
2.141 /// \ref vf2() "function-type interface" of \ref Vf2 algorithm.
2.142 ///
2.143 - /// \warning This class should only be used through the function \ref vf2().
2.144 + /// \warning This class is not to be used directly.
2.145 ///
2.146 /// \tparam TR The traits class that defines various types used by the
2.147 /// algorithm.
2.148 @@ -465,11 +472,10 @@
2.149
2.150 public:
2.151 ///Constructor
2.152 - Vf2Wizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {
2.153 - }
2.154 + Vf2Wizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {}
2.155
2.156 ///Copy constructor
2.157 - Vf2Wizard(const Base &b) : Base(b) { }
2.158 + Vf2Wizard(const Base &b) : Base(b) {}
2.159
2.160 ///Copy constructor
2.161 Vf2Wizard(const Vf2Wizard &b) : Base(b) {}
3.1 --- a/lemon/vf2pp.h Sat Oct 07 00:14:05 2017 +0200
3.2 +++ b/lemon/vf2pp.h Sat Oct 07 03:18:49 2017 +0200
3.3 @@ -75,7 +75,7 @@
3.4 ///
3.5 ///There is also a \ref vf2pp() "function-type interface" called
3.6 ///\ref vf2pp() for the %VF2 Plus Plus algorithm, which is probably
3.7 - ///more convenient in most use-cases.
3.8 + ///more convenient in most use cases.
3.9 ///
3.10 ///\tparam G1 The type of the graph to be embedded.
3.11 ///The default type is \ref ListDigraph.
3.12 @@ -96,11 +96,8 @@
3.13 #else
3.14 template<class G1=ListDigraph,
3.15 class G2=ListDigraph,
3.16 - class M = typename G1::template NodeMap<G2::Node>,//the mapping
3.17 - //labels of G1,the labels are the numbers {0,1,2,..,K-1},
3.18 - //where K is the number of different labels
3.19 + class M = typename G1::template NodeMap<G2::Node>,
3.20 class M1 = typename G1::template NodeMap<int>,
3.21 - //labels of G2, ...
3.22 class M2 = typename G2::template NodeMap<int> >
3.23 #endif
3.24 class Vf2pp {
3.25 @@ -114,17 +111,17 @@
3.26 //where v1 is a node of G1 and v2 is a node of G2
3.27 M &_mapping;
3.28
3.29 - //order[i] is a node of g1, for which a pair is searched if depth=i
3.30 + //order[i] is a node of g1 for which a pair is searched if depth=i
3.31 std::vector<typename G1::Node> order;
3.32
3.33 - //currEdgeIts[i] is the last used edge iterator in the ith
3.34 + //currEdgeIts[i] is the last used edge iterator in the i-th
3.35 //depth to find a pair for node order[i]
3.36 std::vector<typename G2::IncEdgeIt> currEdgeIts;
3.37 -
3.38 - //The small graph.
3.39 +
3.40 + //The graph to be embedded
3.41 const G1 &_g1;
3.42
3.43 - //The large graph.
3.44 + //The graph into which g1 is to be embedded
3.45 const G2 &_g2;
3.46
3.47 //rNewLabels1[v] is a pair of form
3.48 @@ -137,24 +134,24 @@
3.49 typename G1::template NodeMap<std::vector<std::pair<int,int> > >
3.50 rInOutLabels1;
3.51
3.52 - //_intLabels1[v]==i means that vertex v has the i label in
3.53 - //_g1 (i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
3.54 + //_intLabels1[v]==i means that node v has label i in _g1
3.55 + //(i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
3.56 M1 &_intLabels1;
3.57
3.58 - //_intLabels2[v]==i means that vertex v has the i label in
3.59 - //_g2 (i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
3.60 + //_intLabels2[v]==i means that node v has label i in _g2
3.61 + //(i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
3.62 M2 &_intLabels2;
3.63
3.64 //largest label
3.65 const int maxLabel;
3.66
3.67 //lookup tables for manipulating with label class cardinalities
3.68 - //after use they have to be reset to 0..0
3.69 + //(after use they have to be reset to 0..0)
3.70 std::vector<int> labelTmp1,labelTmp2;
3.71
3.72 MappingType _mapping_type;
3.73
3.74 - //indicates whether the mapping or the labels must be deleted in the ctor
3.75 + //indicates whether the mapping or the labels must be deleted in the destructor
3.76 bool _deallocMappingAfterUse,_deallocLabelsAfterUse;
3.77
3.78
3.79 @@ -286,8 +283,7 @@
3.80 return isIso&&cutByLabels<MT>(n1,n2);
3.81 }
3.82
3.83 -
3.84 - //matches n1 and n2
3.85 + //maps n1 to n2
3.86 void addPair(const typename G1::Node n1,const typename G2::Node n2) {
3.87 _conn[n2]=-1;
3.88 _mapping.set(n1,n2);
3.89 @@ -298,8 +294,7 @@
3.90 }
3.91 }
3.92
3.93 -
3.94 - //dematches n1 and n2
3.95 + //removes mapping of n1 to n2
3.96 void subPair(const typename G1::Node n1,const typename G2::Node n2) {
3.97 _conn[n2]=0;
3.98 _mapping.set(n1,INVALID);
3.99 @@ -312,7 +307,6 @@
3.100 }
3.101 }
3.102
3.103 -
3.104 void processBFSLevel(typename G1::Node source,unsigned int& orderIndex,
3.105 typename G1::template NodeMap<int>& dm1,
3.106 typename G1::template NodeMap<bool>& added) {
3.107 @@ -364,7 +358,6 @@
3.108 for(typename G2::NodeIt n2(_g2); n2!=INVALID; ++n2)
3.109 ++labelTmp1[_intLabels2[n2]];
3.110
3.111 - // OutDegMap<G1> dm1(_g1);
3.112 typename G1::template NodeMap<int> dm1(_g1,0);
3.113 for(typename G1::EdgeIt e(_g1); e!=INVALID; ++e) {
3.114 ++dm1[_g1.u(e)];
3.115 @@ -397,34 +390,34 @@
3.116 template<MappingType MT>
3.117 bool extMatch(){
3.118 while(_depth>=0) {
3.119 - //there is no node in g1, which has not pair in g2.
3.120 if(_depth==static_cast<int>(order.size())) {
3.121 + //all nodes of g1 are mapped to nodes of g2
3.122 --_depth;
3.123 return true;
3.124 }
3.125 typename G1::Node& nodeOfDepth = order[_depth];
3.126 const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth];
3.127 typename G2::IncEdgeIt &edgeItOfDepth = currEdgeIts[_depth];
3.128 - //the node of g2, which neighbours are the candidates for
3.129 + //the node of g2 whose neighbours are the candidates for
3.130 //the pair of order[_depth]
3.131 typename G2::Node currPNode;
3.132 if(edgeItOfDepth==INVALID){
3.133 typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth);
3.134 - //if _mapping[order[_depth]]!=INVALID, we dont need
3.135 - //fstMatchedE
3.136 - if(pairOfNodeOfDepth==INVALID)
3.137 + //if _mapping[order[_depth]]!=INVALID, we don't need fstMatchedE
3.138 + if(pairOfNodeOfDepth==INVALID) {
3.139 for(; fstMatchedE!=INVALID &&
3.140 _mapping[_g1.oppositeNode(nodeOfDepth,
3.141 fstMatchedE)]==INVALID;
3.142 ++fstMatchedE); //find fstMatchedE, it could be preprocessed
3.143 + }
3.144 if(fstMatchedE==INVALID||pairOfNodeOfDepth!=INVALID) {
3.145 - //We found no covered neighbours, this means
3.146 - //the graph is not connected(or _depth==0). Each
3.147 - //uncovered(and there are some other properties due
3.148 + //We found no covered neighbours, this means that
3.149 + //the graph is not connected (or _depth==0). Each
3.150 + //uncovered (and there are some other properties due
3.151 //to the spec. problem types) node of g2 is
3.152 - //candidate. We can read the iterator of the last
3.153 + //candidate. We can read the iterator of the last
3.154 //tried node from the match if it is not the first
3.155 - //try(match[nodeOfDepth]!=INVALID)
3.156 + //try (match[nodeOfDepth]!=INVALID)
3.157 typename G2::NodeIt n2(_g2);
3.158 //if it's not the first try
3.159 if(pairOfNodeOfDepth!=INVALID) {
3.160 @@ -447,13 +440,13 @@
3.161 --_depth;
3.162 continue;
3.163 }
3.164 - else{
3.165 + else {
3.166 currPNode=_mapping[_g1.oppositeNode(nodeOfDepth,
3.167 fstMatchedE)];
3.168 edgeItOfDepth=typename G2::IncEdgeIt(_g2,currPNode);
3.169 }
3.170 }
3.171 - else{
3.172 + else {
3.173 currPNode=_g2.oppositeNode(pairOfNodeOfDepth,
3.174 edgeItOfDepth);
3.175 subPair(nodeOfDepth,pairOfNodeOfDepth);
3.176 @@ -472,7 +465,7 @@
3.177 return false;
3.178 }
3.179
3.180 - //calc. the lookup table for cutting the searchtree
3.181 + //calculate the lookup table for cutting the search tree
3.182 void setRNew1tRInOut1t(){
3.183 typename G1::template NodeMap<int> tmp(_g1,0);
3.184 for(unsigned int i=0; i<order.size(); ++i) {
3.185 @@ -675,7 +668,7 @@
3.186
3.187 public:
3.188 ///Constructor
3.189 - Vf2ppWizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) { }
3.190 + Vf2ppWizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {}
3.191
3.192 ///Copy constructor
3.193 Vf2ppWizard(const Base &b) : Base(b) {}
3.194 @@ -684,7 +677,7 @@
3.195 template<typename T>
3.196 struct SetMappingBase : public Base {
3.197 typedef T Mapping;
3.198 - SetMappingBase(const Base &b) : Base(b) { }
3.199 + SetMappingBase(const Base &b) : Base(b) {}
3.200 };
3.201
3.202 ///\brief \ref named-templ-param "Named parameter" for setting
3.203 @@ -713,11 +706,11 @@
3.204 ///the node labels.
3.205 ///
3.206 ///\param nodeLabels1 A \ref concepts::ReadMap "readable node map"
3.207 - ///of g1 with integer value. In case of K different labels, the labels
3.208 - ///must be the {0,1,..,K-1} numbers.
3.209 + ///of g1 with integer values. In case of K different labels, the labels
3.210 + ///must be the numbers {0,1,..,K-1}.
3.211 ///\param nodeLabels2 A \ref concepts::ReadMap "readable node map"
3.212 - ///of g2 with integer value. In case of K different labels, the labels
3.213 - ///must be the {0,1,..,K-1} numbers.
3.214 + ///of g2 with integer values. In case of K different labels, the labels
3.215 + ///must be the numbers {0,1,..,K-1}.
3.216 template<typename NL1, typename NL2>
3.217 Vf2ppWizard< SetNodeLabelsBase<NL1,NL2> >
3.218 nodeLabels(const NL1 &nodeLabels1, const NL2 &nodeLabels2) {
3.219 @@ -877,7 +870,7 @@
3.220 /// int num_isos = vf2pp(g1,g2).iso().count();
3.221 ///
3.222 /// // Iterate through all the induced subgraph mappings
3.223 - /// //of graph g1 into g2 using the labels c1 and c2
3.224 + /// // of graph g1 into g2 using the labels c1 and c2
3.225 /// auto* myVf2pp = vf2pp(g1,g2).mapping(m).nodeLabels(c1,c2)
3.226 /// .induced().getPtrToVf2Object();
3.227 /// while(myVf2pp->find()){