Improved documentation of include/dai/weightedgraph.h
authorJoris Mooij <joris.mooij@tuebingen.mpg.de>
Wed, 21 Oct 2009 16:08:49 +0000 (18:08 +0200)
committerJoris Mooij <joris.mooij@tuebingen.mpg.de>
Wed, 21 Oct 2009 16:08:49 +0000 (18:08 +0200)
TODO
include/dai/doc.h
include/dai/weightedgraph.h
src/weightedgraph.cpp

diff --git a/TODO b/TODO
index 1af169e..0440459 100644 (file)
--- a/TODO
+++ b/TODO
@@ -2,7 +2,6 @@ To do for the next release (0.2.3):
 
 Improve documentation:
 
-       weightedgraph.h
        factorgraph.h
        clustergraph.h
        regiongraph.h
index 54c0659..7d2cd70 100644 (file)
  *  "Choosing a Variable to Clamp",
  *  <em>Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics (AISTATS 2009)</em> 5:145-152
  *  http://jmlr.csail.mit.edu/proceedings/papers/v5/eaton09a/eaton09a.pdf
+ *
+ *  \anchor StW99 \ref StW99
+ *  A. Steger and N. C. Wormald (1999):
+ *  "Generating Random Regular Graphs Quickly",
+ *  <em>Combinatorics, Probability and Computing</em> Vol 8, Issue 4, pp. 377-396
+ *  http://www.math.uwaterloo.ca/~nwormald/papers/randgen.pdf
  */
 
 
index 224fa6c..96a3830 100644 (file)
@@ -10,8 +10,7 @@
 
 
 /** \file
- *  \brief Defines some utility functions for weighted graphs
- *  \todo Improve documentation
+ *  \brief Defines some utility functions for (weighted) undirected graphs
  *  \todo Improve general support for graphs and trees.
  */
 
 namespace dai {
 
 
-/// Represents a directed edge pointing from n1 to n2
+/// Represents a directed edge
 class DEdge {
     public:
-        size_t n1;  ///< First node index
-        size_t n2;  ///< Second node index
+        /// First node index
+        size_t n1;
+        /// Second node index
+        size_t n2;
 
         /// Default constructor
         DEdge() {}
 
-        /// Constructor
+        /// Constructs a directed edge pointing from \a m1 to \a m2
         DEdge( size_t m1, size_t m2 ) : n1(m1), n2(m2) {}
 
         /// Tests for equality
@@ -57,7 +58,7 @@ class DEdge {
             return( (n1 < x.n1) || ((n1 == x.n1) && (n2 < x.n2)) );
         }
 
-        /// Writes a DEdge to an output stream
+        /// Writes a directed edge to an output stream
         friend std::ostream & operator << (std::ostream & os, const DEdge & e) {
             os << "(" << e.n1 << "," << e.n2 << ")";
             return os;
@@ -65,22 +66,24 @@ class DEdge {
 };
 
 
-/// Undirected edge between nodes n1 and n2
+/// Represents an undirected edge
 class UEdge {
     public:
-        size_t  n1;  ///< First node index
-        size_t  n2;  ///< Second node index
+        /// First node index
+        size_t  n1;
+        /// Second node index
+        size_t  n2;
 
         /// Default constructor
         UEdge() {}
 
-        /// Constructor
+        /// Constructs an undirected edge between \a m1 and \a m2
         UEdge( size_t m1, size_t m2 ) : n1(m1), n2(m2) {}
 
         /// Construct from DEdge
-        UEdge( const DEdge & e ) : n1(e.n1), n2(e.n2) {}
+        UEdge( const DEdge &e ) : n1(e.n1), n2(e.n2) {}
 
-        /// Tests for inequality (disregarding the ordering of n1 and n2)
+        /// Tests for inequality (disregarding the ordering of the nodes)
         bool operator==( const UEdge &x ) {
             return ((n1 == x.n1) && (n2 == x.n2)) || ((n1 == x.n2) && (n2 == x.n1));
         }
@@ -96,7 +99,7 @@ class UEdge {
             return( (s < xs) || ((s == xs) && (l < xl)) );
         }
 
-        /// Writes a UEdge to an output stream
+        /// Writes an undirected edge to an output stream
         friend std::ostream & operator << (std::ostream & os, const UEdge & e) {
             if( e.n1 < e.n2 )
                 os << "{" << e.n1 << "," << e.n2 << "}";
@@ -113,14 +116,20 @@ typedef std::vector<UEdge>  UEdgeVec;
 /// Vector of DEdge
 typedef std::vector<DEdge>  DEdgeVec;
 
-/// Represents an undirected weighted graph, with weights of type T
+/// Represents an undirected weighted graph, with weights of type \a T
 template<class T> class WeightedGraph : public std::map<UEdge, T> {};
 
 /// Represents an undirected graph
 typedef std::set<UEdge>     Graph;
 
 
-/// Uses Prim's algorithm to construct a minimal spanning tree from the (positively) weighted graph G.
+/// Constructs a rooted tree from a tree and a root
+/** \pre T has no cycles and contains node \a Root
+ */
+DEdgeVec GrowRootedTree( const Graph &T, size_t Root );
+
+
+/// Uses Prim's algorithm to construct a minimal spanning tree from the (positively) weighted graph \a G.
 /** Uses implementation in Boost Graph Library.
  */
 template<typename T> DEdgeVec MinSpanningTreePrims( const WeightedGraph<T> &G ) {
@@ -148,59 +157,34 @@ template<typename T> DEdgeVec MinSpanningTreePrims( const WeightedGraph<T> &G )
         prim_minimum_spanning_tree( g, &(p[0]) );
 
         // Store tree edges in result
-        result.reserve( nodes.size() - 1 );
+        Graph tree;
         size_t root = 0;
         for( size_t i = 0; i != p.size(); i++ )
             if( p[i] != i )
-                result.push_back( DEdge( p[i], i ) );
+                tree.insert( UEdge( p[i], i ) );
             else
                 root = i;
-
-        // We have to store the minimum spanning tree in the right
-        // order, such that for all (i1, j1), (i2, j2) in result,
-        // if j1 == i2 then (i1, j1) comes before (i2, j2) in result.
-        // We do this by reordering the contents of result, effectively
-        // growing the tree starting at the root. At each step,
-        // result[0..N-1] are the edges already added to the tree,
-        // whereas the other elements of result still have to be added.
-        // The elements of nodes are the vertices that still have to
-        // be added to the tree.
-
-        // Start with the root
-        nodes.erase( root );
-        size_t N = 0;
-
-        // Iteratively add edges and nodes to the growing tree
-        while( N != result.size() ) {
-            for( size_t e = N; e != result.size(); e++ ) {
-                bool e1_in_tree = !nodes.count( result[e].n1 );
-                if( e1_in_tree ) {
-                    nodes.erase( result[e].n2 );
-                    swap( result[N], result[e] );
-                    N++;
-                    break;
-                }
-            }
-        }
+        // Order them
+        result = GrowRootedTree( tree, root );
     }
 
     return result;
 }
 
 
-/// Use Prim's algorithm to construct a minimal spanning tree from the (positively) weighted graph G.
+/// Use Prim's algorithm to construct a minimal spanning tree from the (positively) weighted graph \a G.
 /** Uses implementation in Boost Graph Library.
  */
-template<typename T> DEdgeVec MaxSpanningTreePrims( const WeightedGraph<T> & Graph ) {
-    if( Graph.size() == 0 )
+template<typename T> DEdgeVec MaxSpanningTreePrims( const WeightedGraph<T> &G ) {
+    if( G.size() == 0 )
         return DEdgeVec();
     else {
-        T maxweight = Graph.begin()->second;
-        for( typename WeightedGraph<T>::const_iterator it = Graph.begin(); it != Graph.end(); it++ )
+        T maxweight = G.begin()->second;
+        for( typename WeightedGraph<T>::const_iterator it = G.begin(); it != G.end(); it++ )
             if( it->second > maxweight )
                 maxweight = it->second;
         // make a copy of the graph
-        WeightedGraph<T> gr( Graph );
+        WeightedGraph<T> gr( G );
         // invoke MinSpanningTreePrims with negative weights
         // (which have to be shifted to satisfy positivity criterion)
         for( typename WeightedGraph<T>::iterator it = gr.begin(); it != gr.end(); it++ )
@@ -210,11 +194,13 @@ template<typename T> DEdgeVec MaxSpanningTreePrims( const WeightedGraph<T> & Gra
 }
 
 
-/// Constructs a rooted tree from a tree and a root
-DEdgeVec GrowRootedTree( const Graph & T, size_t Root );
-
-
-/// Constructs a random undirected graph of N nodes, where each node has connectivity d
+/// Constructs a random undirected graph of \a N nodes, where each node has connectivity \a d
+/** Algorithm 1 in [\ref StW99].
+ *  Draws a random graph of size \a N and uniform degree \a d
+ *  from an almost uniform probability distribution over these graphs
+ *  (which becomes uniform in the limit that \a d is small and \a N goes
+ *  to infinity).
+ */
 UEdgeVec RandomDRegularGraph( size_t N, size_t d );
 
 
index c29b471..94bb8c1 100644 (file)
@@ -21,7 +21,7 @@ namespace dai {
 using namespace std;
 
 
-DEdgeVec GrowRootedTree( const Graph & T, size_t Root ) {
+DEdgeVec GrowRootedTree( const Graph &T, size_t Root ) {
     DEdgeVec result;
     if( T.size() == 0 )
         return result;
@@ -62,14 +62,6 @@ DEdgeVec GrowRootedTree( const Graph & T, size_t Root ) {
 
 
 UEdgeVec RandomDRegularGraph( size_t N, size_t d ) {
-    // Algorithm 1 in "Generating random regular graphs quickly"
-    // by A. Steger and N.C. Wormald
-    //
-    // Draws a random graph with size N and uniform degree d
-    // from an almost uniform probability distribution over these graphs
-    // (which becomes uniform in the limit that d is small and N goes
-    // to infinity).
-
     DAI_ASSERT( (N * d) % 2 == 0 );
 
     bool ready = false;