# HG changeset patch
# User Peter Kovacs <kpeter@inf.elte.hu>
# Date 1507339129 -7200
# Node ID 76349d8212d3953003885aabcef528a29de3d42d
# Parent  120b9031eadac340f6078b85d9bcb43c9342bc93
Improve and unify comments and API docs of VF2 algorithms (#597)

diff -r 120b9031eada -r 76349d8212d3 lemon/bits/vf2_internals.h
--- a/lemon/bits/vf2_internals.h	Sat Oct 07 00:14:05 2017 +0200
+++ b/lemon/bits/vf2_internals.h	Sat Oct 07 03:18:49 2017 +0200
@@ -26,7 +26,7 @@
 namespace lemon {
   ///\ingroup graph_isomorphism
   ///The \ref Vf2 "VF2" algorithm is capable of finding different kind of
-  ///embeddings, this enum specifies its type.
+  ///graph embeddings, this enum specifies their types.
   ///
   ///See \ref graph_isomorphism for a more detailed description.
   enum MappingType {
@@ -35,13 +35,12 @@
     /// Induced subgraph isomorphism
     INDUCED = 1,
     /// Graph isomorphism
-
-    /// If the two graph has the same number of nodes, than it is
+    ///
+    /// If the two graphs have the same number of nodes, than it is
     /// equivalent to \ref INDUCED, and if they also have the same
     /// number of edges, then it is also equivalent to \ref SUBGRAPH.
     ///
-    /// However, using this setting is faster than the other two
-    /// options.
+    /// However, using this setting is faster than the other two options.
     ISOMORPH = 2
   };
 }
diff -r 120b9031eada -r 76349d8212d3 lemon/vf2.h
--- a/lemon/vf2.h	Sat Oct 07 00:14:05 2017 +0200
+++ b/lemon/vf2.h	Sat Oct 07 03:18:49 2017 +0200
@@ -53,8 +53,6 @@
         }
       };
 
-
-
       template <class G>
       class DfsLeaveOrder : public DfsVisitor<G> {
         const G &_g;
@@ -93,7 +91,7 @@
   ///
   ///There is also a \ref vf2() "function-type interface" called \ref vf2()
   ///for the %VF2 algorithm, which is probably more convenient in most
-  ///use-cases.
+  ///use cases.
   ///
   ///\tparam G1 The type of the graph to be embedded.
   ///The default type is \ref ListDigraph.
@@ -102,7 +100,7 @@
   ///\tparam M The type of the NodeMap storing the mapping.
   ///By default, it is G1::NodeMap<G2::Node>
   ///\tparam NEQ A bool-valued binary functor determinining whether a node is
-  ///mappable to another. By default it is an always true operator.
+  ///mappable to another. By default, it is an always-true operator.
   ///
   ///\sa vf2()
 #ifdef DOXYGEN
@@ -116,23 +114,31 @@
   class Vf2 {
     //Current depth in the DFS tree.
     int _depth;
+
     //Functor with bool operator()(G1::Node,G2::Node), which returns 1
-    //ifff the two nodes are equivalent.
+    //if and only if the two nodes are equivalent
     NEQ _nEq;
 
+    //_conn[v2] = number of covered neighbours of v2
     typename G2::template NodeMap<int> _conn;
-    //Current mapping. We index it by the nodes of g1, and match[v] is
-    //a node of g2.
+
+    //The current mapping. _mapping[v1]=v2 iff v1 has been mapped to v2,
+    //where v1 is a node of G1 and v2 is a node of G2
     M &_mapping;
-    //order[i] is the node of g1, for which we search a pair if depth=i
+
+    //order[i] is the node of g1 for which a pair is searched if depth=i
     std::vector<typename G1::Node> order;
-    //currEdgeIts[i] is an edge iterator, witch is last used in the ith
-    //depth to find a pair for order[i].
+
+    //currEdgeIts[i] is the last used edge iterator in the i-th
+    //depth to find a pair for node order[i]
     std::vector<typename G2::IncEdgeIt> currEdgeIts;
-    //The small graph.
+ 
+    //The graph to be embedded
     const G1 &_g1;
-    //The large graph.
+
+    //The graph into which g1 is to be embedded
     const G2 &_g2;
+
     //lookup tables for cutting the searchtree
     typename G1::template NodeMap<int> rNew1t,rInOut1t;
 
@@ -242,34 +248,34 @@
     template<MappingType MT>
     bool extMatch() {
       while(_depth>=0) {
-        //there are not nodes in g1, which has not pair in g2.
         if(_depth==static_cast<int>(order.size())) {
+          //all nodes of g1 are mapped to nodes of g2
           --_depth;
           return true;
         }
         typename G1::Node& nodeOfDepth = order[_depth];
         const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth];
         typename G2::IncEdgeIt &edgeItOfDepth = currEdgeIts[_depth];
-        //the node of g2, which neighbours are the candidates for
+        //the node of g2 whose neighbours are the candidates for
         //the pair of nodeOfDepth
         typename G2::Node currPNode;
         if(edgeItOfDepth==INVALID) {
           typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth);
-          //if pairOfNodeOfDepth!=INVALID, we dont use
-          //fstMatchedE
-          if(pairOfNodeOfDepth==INVALID)
+          //if pairOfNodeOfDepth!=INVALID, we don't use fstMatchedE
+          if(pairOfNodeOfDepth==INVALID) {
             for(; fstMatchedE!=INVALID &&
                   _mapping[_g1.oppositeNode(nodeOfDepth,
                                             fstMatchedE)]==INVALID;
                 ++fstMatchedE) ; //find fstMatchedE
+          }
           if(fstMatchedE==INVALID||pairOfNodeOfDepth!=INVALID) {
-            //We found no covered neighbours, this means
-            //the graph is not connected(or _depth==0).  Each
-            //uncovered(and there are some other properties due
+            //We found no covered neighbours, this means that
+            //the graph is not connected (or _depth==0). Each
+            //uncovered (and there are some other properties due
             //to the spec. problem types) node of g2 is
-            //candidate.  We can read the iterator of the last
+            //candidate. We can read the iterator of the last
             //tried node from the match if it is not the first
-            //try(match[nodeOfDepth]!=INVALID)
+            //try (match[nodeOfDepth]!=INVALID)
             typename G2::NodeIt n2(_g2);
             //if it's not the first try
             if(pairOfNodeOfDepth!=INVALID) {
@@ -317,7 +323,7 @@
       return false;
     }
 
-    //calc. the lookup table for cut the searchtree
+    //calculate the lookup table for cutting the search tree
     void setRNew1tRInOut1t() {
       typename G1::template NodeMap<int> tmp(_g1,0);
       for(unsigned int i=0; i<order.size(); ++i) {
@@ -351,7 +357,8 @@
     Vf2(const G1 &g1, const G2 &g2, M &m, const NEQ &neq = NEQ() ) :
       _nEq(neq), _conn(g2,0), _mapping(m), order(countNodes(g1)),
       currEdgeIts(countNodes(g1),INVALID), _g1(g1), _g2(g2), rNew1t(g1,0),
-      rInOut1t(g1,0), _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0) {
+      rInOut1t(g1,0), _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0)
+    {
       _depth=0;
       setOrder();
       setRNew1tRInOut1t();
@@ -440,11 +447,11 @@
 
 
   /// Auxiliary class for the function-type interface of %VF2 algorithm.
-
+  ///
   /// This auxiliary class implements the named parameters of
   /// \ref vf2() "function-type interface" of \ref Vf2 algorithm.
   ///
-  /// \warning This class should only be used through the function \ref vf2().
+  /// \warning This class is not to be used directly.
   ///
   /// \tparam TR The traits class that defines various types used by the
   /// algorithm.
@@ -465,11 +472,10 @@
 
   public:
     ///Constructor
-    Vf2Wizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {
-    }
+    Vf2Wizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {}
 
     ///Copy constructor
-    Vf2Wizard(const Base &b) : Base(b) { }
+    Vf2Wizard(const Base &b) : Base(b) {}
 
     ///Copy constructor
     Vf2Wizard(const Vf2Wizard &b) : Base(b) {}
diff -r 120b9031eada -r 76349d8212d3 lemon/vf2pp.h
--- a/lemon/vf2pp.h	Sat Oct 07 00:14:05 2017 +0200
+++ b/lemon/vf2pp.h	Sat Oct 07 03:18:49 2017 +0200
@@ -75,7 +75,7 @@
   ///
   ///There is also a \ref vf2pp() "function-type interface" called
   ///\ref vf2pp() for the %VF2 Plus Plus algorithm, which is probably
-  ///more convenient in most use-cases.
+  ///more convenient in most use cases.
   ///
   ///\tparam G1 The type of the graph to be embedded.
   ///The default type is \ref ListDigraph.
@@ -96,11 +96,8 @@
 #else
   template<class G1=ListDigraph,
            class G2=ListDigraph,
-           class M = typename G1::template NodeMap<G2::Node>,//the mapping
-           //labels of G1,the labels are the numbers {0,1,2,..,K-1},
-           //where K is the number of different labels
+           class M = typename G1::template NodeMap<G2::Node>,
            class M1 = typename G1::template NodeMap<int>,
-           //labels of G2, ...
            class M2 = typename G2::template NodeMap<int> >
 #endif
   class Vf2pp {
@@ -114,17 +111,17 @@
     //where v1 is a node of G1 and v2 is a node of G2
     M &_mapping;
 
-    //order[i] is a node of g1, for which a pair is searched if depth=i
+    //order[i] is a node of g1 for which a pair is searched if depth=i
     std::vector<typename G1::Node> order;
 
-    //currEdgeIts[i] is the last used edge iterator in the ith
+    //currEdgeIts[i] is the last used edge iterator in the i-th
     //depth to find a pair for node order[i]
     std::vector<typename G2::IncEdgeIt> currEdgeIts;
-
-    //The small graph.
+ 
+    //The graph to be embedded
     const G1 &_g1;
 
-    //The large graph.
+    //The graph into which g1 is to be embedded
     const G2 &_g2;
 
     //rNewLabels1[v] is a pair of form
@@ -137,24 +134,24 @@
     typename G1::template NodeMap<std::vector<std::pair<int,int> > >
     rInOutLabels1;
 
-    //_intLabels1[v]==i means that vertex v has the i label in
-    //_g1 (i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
+    //_intLabels1[v]==i means that node v has label i in _g1
+    //(i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
     M1 &_intLabels1;
 
-    //_intLabels2[v]==i means that vertex v has the i label in
-    //_g2 (i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
+    //_intLabels2[v]==i means that node v has label i in _g2
+    //(i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
     M2 &_intLabels2;
 
     //largest label
     const int maxLabel;
 
     //lookup tables for manipulating with label class cardinalities
-    //after use they have to be reset to 0..0
+    //(after use they have to be reset to 0..0)
     std::vector<int> labelTmp1,labelTmp2;
 
     MappingType _mapping_type;
 
-    //indicates whether the mapping or the labels must be deleted in the ctor
+    //indicates whether the mapping or the labels must be deleted in the destructor
     bool _deallocMappingAfterUse,_deallocLabelsAfterUse;
 
 
@@ -286,8 +283,7 @@
       return isIso&&cutByLabels<MT>(n1,n2);
     }
 
-
-    //matches n1 and n2
+    //maps n1 to n2
     void addPair(const typename G1::Node n1,const typename G2::Node n2) {
       _conn[n2]=-1;
       _mapping.set(n1,n2);
@@ -298,8 +294,7 @@
       }
     }
 
-
-    //dematches n1 and n2
+    //removes mapping of n1 to n2
     void subPair(const typename G1::Node n1,const typename G2::Node n2) {
       _conn[n2]=0;
       _mapping.set(n1,INVALID);
@@ -312,7 +307,6 @@
       }
     }
 
-
     void processBFSLevel(typename G1::Node source,unsigned int& orderIndex,
                          typename G1::template NodeMap<int>& dm1,
                          typename G1::template NodeMap<bool>& added) {
@@ -364,7 +358,6 @@
       for(typename G2::NodeIt n2(_g2); n2!=INVALID; ++n2)
         ++labelTmp1[_intLabels2[n2]];
 
-      //       OutDegMap<G1> dm1(_g1);
       typename G1::template NodeMap<int> dm1(_g1,0);
       for(typename G1::EdgeIt e(_g1); e!=INVALID; ++e) {
         ++dm1[_g1.u(e)];
@@ -397,34 +390,34 @@
     template<MappingType MT>
     bool extMatch(){
       while(_depth>=0) {
-        //there is no node in g1, which has not pair in g2.
         if(_depth==static_cast<int>(order.size())) {
+          //all nodes of g1 are mapped to nodes of g2
           --_depth;
           return true;
         }
         typename G1::Node& nodeOfDepth = order[_depth];
         const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth];
         typename G2::IncEdgeIt &edgeItOfDepth = currEdgeIts[_depth];
-        //the node of g2, which neighbours are the candidates for
+        //the node of g2 whose neighbours are the candidates for
         //the pair of order[_depth]
         typename G2::Node currPNode;
         if(edgeItOfDepth==INVALID){
           typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth);
-          //if _mapping[order[_depth]]!=INVALID, we dont need
-          //fstMatchedE
-          if(pairOfNodeOfDepth==INVALID)
+          //if _mapping[order[_depth]]!=INVALID, we don't need fstMatchedE
+          if(pairOfNodeOfDepth==INVALID) {
             for(; fstMatchedE!=INVALID &&
                   _mapping[_g1.oppositeNode(nodeOfDepth,
                                             fstMatchedE)]==INVALID;
                 ++fstMatchedE); //find fstMatchedE, it could be preprocessed
+          }
           if(fstMatchedE==INVALID||pairOfNodeOfDepth!=INVALID) {
-            //We found no covered neighbours, this means
-            //the graph is not connected(or _depth==0).  Each
-            //uncovered(and there are some other properties due
+            //We found no covered neighbours, this means that
+            //the graph is not connected (or _depth==0). Each
+            //uncovered (and there are some other properties due
             //to the spec. problem types) node of g2 is
-            //candidate.  We can read the iterator of the last
+            //candidate. We can read the iterator of the last
             //tried node from the match if it is not the first
-            //try(match[nodeOfDepth]!=INVALID)
+            //try (match[nodeOfDepth]!=INVALID)
             typename G2::NodeIt n2(_g2);
             //if it's not the first try
             if(pairOfNodeOfDepth!=INVALID) {
@@ -447,13 +440,13 @@
               --_depth;
             continue;
           }
-          else{
+          else {
             currPNode=_mapping[_g1.oppositeNode(nodeOfDepth,
                                                 fstMatchedE)];
             edgeItOfDepth=typename G2::IncEdgeIt(_g2,currPNode);
           }
         }
-        else{
+        else {
           currPNode=_g2.oppositeNode(pairOfNodeOfDepth,
                                      edgeItOfDepth);
           subPair(nodeOfDepth,pairOfNodeOfDepth);
@@ -472,7 +465,7 @@
       return false;
     }
 
-    //calc. the lookup table for cutting the searchtree
+    //calculate the lookup table for cutting the search tree
     void setRNew1tRInOut1t(){
       typename G1::template NodeMap<int> tmp(_g1,0);
       for(unsigned int i=0; i<order.size(); ++i) {
@@ -675,7 +668,7 @@
 
   public:
     ///Constructor
-    Vf2ppWizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) { }
+    Vf2ppWizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {}
 
     ///Copy constructor
     Vf2ppWizard(const Base &b) : Base(b) {}
@@ -684,7 +677,7 @@
     template<typename T>
     struct SetMappingBase : public Base {
       typedef T Mapping;
-      SetMappingBase(const Base &b) : Base(b) { }
+      SetMappingBase(const Base &b) : Base(b) {}
     };
 
     ///\brief \ref named-templ-param "Named parameter" for setting
@@ -713,11 +706,11 @@
     ///the node labels.
     ///
     ///\param nodeLabels1 A \ref concepts::ReadMap "readable node map"
-    ///of g1 with integer value. In case of K different labels, the labels
-    ///must be the {0,1,..,K-1} numbers.
+    ///of g1 with integer values. In case of K different labels, the labels
+    ///must be the numbers {0,1,..,K-1}.
     ///\param nodeLabels2 A \ref concepts::ReadMap "readable node map"
-    ///of g2 with integer value. In case of K different labels, the labels
-    ///must be the {0,1,..,K-1} numbers.
+    ///of g2 with integer values. In case of K different labels, the labels
+    ///must be the numbers {0,1,..,K-1}.
     template<typename NL1, typename NL2>
     Vf2ppWizard< SetNodeLabelsBase<NL1,NL2> >
     nodeLabels(const NL1 &nodeLabels1, const NL2 &nodeLabels2) {
@@ -877,7 +870,7 @@
   ///  int num_isos = vf2pp(g1,g2).iso().count();
   ///
   ///  // Iterate through all the induced subgraph mappings
-  ///  //of graph g1 into g2 using the labels c1 and c2
+  ///  // of graph g1 into g2 using the labels c1 and c2
   ///  auto* myVf2pp = vf2pp(g1,g2).mapping(m).nodeLabels(c1,c2)
   ///  .induced().getPtrToVf2Object();
   ///  while(myVf2pp->find()){