Changeset 1188:76349d8212d3 in lemon-main

Timestamp:

10/07/17 03:18:49 (7 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

Improve and unify comments and API docs of VF2 algorithms (#597)

Location:

lemon

Files:

• bits/vf2_internals.h (modified) (2 diffs)
• vf2.h (modified) (10 diffs)
• vf2pp.h (modified) (18 diffs)

lemon/bits/vf2_internals.h

@@ -27 +27 @@
   ///\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.
@@ -36 +36 @@
     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
   };

lemon/vf2.h

@@ -54 +54 @@
       };
 
-
-
       template <class G>
       class DfsLeaveOrder : public DfsVisitor<G> {
@@ -94 +92 @@
   ///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.
@@ -103 +101 @@
   ///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()
@@ -117 +115 @@
     //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;
@@ -243 +249 @@
     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;
@@ -251 +257 @@
         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
@@ -318 +324 @@
     }
 
-    //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);
@@ -352 +358 @@
       _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();
@@ -441 +448 @@
 
   /// 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
@@ -466 +473 @@
   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

lemon/vf2pp.h

@@ -76 +76 @@
   ///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.
@@ -97 +97 @@
   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
@@ -115 +112 @@
     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;
 
@@ -138 +135 @@
     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;
 
@@ -150 +147 @@
 
     //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;
 
@@ -287 +284 @@
     }
 
-
-    //matches n1 and n2
+    //maps n1 to n2
     void addPair(const typename G1::Node n1,const typename G2::Node n2) {
       _conn[n2]=-1;
@@ -299 +295 @@
     }
 
-
-    //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;
@@ -312 +307 @@
       }
     }
-
 
     void processBFSLevel(typename G1::Node source,unsigned int& orderIndex,
@@ -365 +359 @@
         ++labelTmp1[_intLabels2[n2]];
 
-      //       OutDegMap<G1> dm1(_g1);
       typename G1::template NodeMap<int> dm1(_g1,0);
       for(typename G1::EdgeIt e(_g1); e!=INVALID; ++e) {
@@ -398 +391 @@
     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;
@@ -406 +399 @@
         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
@@ -448 +441 @@
             continue;
           }
-          else{
+          else {
             currPNode=_mapping[_g1.oppositeNode(nodeOfDepth,
                                                 fstMatchedE)];
@@ -454 +447 @@
           }
         }
-        else{
+        else {
           currPNode=_g2.oppositeNode(pairOfNodeOfDepth,
                                      edgeItOfDepth);
@@ -473 +466 @@
     }
 
-    //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);
@@ -676 +669 @@
   public:
     ///Constructor
-    Vf2ppWizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) { }
+    Vf2ppWizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {}
 
     ///Copy constructor
@@ -685 +678 @@
     struct SetMappingBase : public Base {
       typedef T Mapping;
-      SetMappingBase(const Base &b) : Base(b) { }
+      SetMappingBase(const Base &b) : Base(b) {}
     };
 
@@ -714 +707 @@
     ///
     ///\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> >
@@ -878 +871 @@
   ///
   ///  // 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();