Removed obsolete/deprecated stuff
[libdai.git] / include / dai / weightedgraph.h
index 990d409..cc723bc 100644 (file)
@@ -1,22 +1,18 @@
-/*  Copyright (C) 2006-2008  Joris Mooij  [j dot mooij at science dot ru dot nl]
-    Radboud University Nijmegen, The Netherlands
-    
-    This file is part of libDAI.
+/*  This file is part of libDAI - http://www.libdai.org/
+ *
+ *  libDAI is licensed under the terms of the GNU General Public License version
+ *  2, or (at your option) any later version. libDAI is distributed without any
+ *  warranty. See the file COPYING for more details.
+ *
+ *  Copyright (C) 2006-2009  Joris Mooij  [joris dot mooij at libdai dot org]
+ *  Copyright (C) 2006-2007  Radboud University Nijmegen, The Netherlands
+ */
 
-    libDAI is free software; you can redistribute it and/or modify
-    it under the terms of the GNU General Public License as published by
-    the Free Software Foundation; either version 2 of the License, or
-    (at your option) any later version.
 
-    libDAI is distributed in the hope that it will be useful,
-    but WITHOUT ANY WARRANTY; without even the implied warranty of
-    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-    GNU General Public License for more details.
-
-    You should have received a copy of the GNU General Public License
-    along with libDAI; if not, write to the Free Software
-    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
-*/
+/** \file
+ *  \brief Defines some utility functions for (weighted) undirected graphs, trees and rooted trees.
+ *  \todo Improve general support for graphs and trees.
+ */
 
 
 #ifndef __defined_libdai_weightedgraph_h
 #include <map>
 #include <iostream>
 #include <set>
+#include <limits>
+#include <climits>   // Work-around for bug in boost graph library
+
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/prim_minimum_spanning_tree.hpp>
 
 
 namespace dai {
 
 
-/// Directed edge
+/// Represents a directed edge
 class DEdge {
     public:
-        size_t  n1, n2;
-    
+        /// First node index (source of edge)
+        size_t n1;
+
+        /// Second node index (sink of edge)
+        size_t n2;
+
+        /// Default constructor
         DEdge() {}
+
+        /// Constructs a directed edge pointing from \a m1 to \a m2
         DEdge( size_t m1, size_t m2 ) : n1(m1), n2(m2) {}
-        bool operator==( const DEdge &x ) const {
-            return ((n1 == x.n1) && (n2 == x.n2));
-        }
-        bool operator!=( const DEdge &x ) const {
-            return !(*this == x);
-        }
+
+        /// Tests for equality
+        bool operator==( const DEdge &x ) const { return ((n1 == x.n1) && (n2 == x.n2)); }
+
+        /// Tests for inequality
+        bool operator!=( const DEdge &x ) const { return !(*this == x); }
+
+        /// Smaller-than operator (performs lexicographical comparison)
         bool operator<( const DEdge &x ) const {
             return( (n1 < x.n1) || ((n1 == x.n1) && (n2 < x.n2)) );
         }
+
+        /// 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;
@@ -55,17 +67,29 @@ class DEdge {
 };
 
 
-/// Undirected edge
+/// Represents an undirected edge
 class UEdge {
     public:
-        size_t  n1, n2;
-    
+        /// First node index
+        size_t  n1;
+        /// Second node index
+        size_t  n2;
+
+        /// Default constructor
         UEdge() {}
+
+        /// Constructs an undirected edge between \a m1 and \a m2
         UEdge( size_t m1, size_t m2 ) : n1(m1), n2(m2) {}
-        UEdge( const DEdge & e ) : n1(e.n1), n2(e.n2) {}
+
+        /// Construct from DEdge
+        UEdge( const DEdge &e ) : n1(e.n1), n2(e.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));
         }
+
+        /// Smaller-than operator
         bool operator<( const UEdge &x ) const {
             size_t s = n1, l = n2;
             if( s > l )
@@ -75,6 +99,8 @@ class UEdge {
                 std::swap( xs, xl );
             return( (s < xs) || ((s == xs) && (l < xl)) );
         }
+
+        /// 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 << "}";
@@ -85,86 +111,113 @@ class UEdge {
 };
 
 
-typedef std::vector<UEdge>  UEdgeVec;
-typedef std::vector<DEdge>  DEdgeVec;
-std::ostream & operator << (std::ostream & os, const DEdgeVec & rt);
+/// Represents an undirected graph, implemented as a std::set of undirected edges
+class Graph : public std::set<UEdge> {
+    public:
+        /// Default constructor
+        Graph() {}
+
+        /// Construct from range of objects that can be cast to DEdge
+        template <class InputIterator>
+        Graph( InputIterator begin, InputIterator end ) {
+            insert( begin, end );
+        }
+};
+
+
+/// Represents an undirected weighted graph, with weights of type \a T, implemented as a std::map mapping undirected edges to weights
 template<class T> class WeightedGraph : public std::map<UEdge, T> {};
-typedef std::set<UEdge>     Graph;
 
 
-/// Use Prim's algorithm to construct a maximal spanning tree from the weighted graph Graph
-template<typename T> DEdgeVec MaxSpanningTreePrim( const WeightedGraph<T> & Graph ) {
-    const long verbose = 0;
+/// Represents a rooted tree, implemented as a vector of directed edges
+/** By convention, the edges are stored such that they point away from 
+ *  the root and such that edges nearer to the root come before edges
+ *  farther away from the root.
+ */
+class RootedTree : public std::vector<DEdge> {
+    public:
+        /// Default constructor
+        RootedTree() {}
 
-    DEdgeVec result;
-    if( Graph.size() == 0 )
-        return result;
-    else {
-        // Make a copy
-        WeightedGraph<T> Gr = Graph;
-
-        // Nodes in the tree
-        std::set<size_t> treeV;
-
-        // Start with one node
-        treeV.insert( Gr.begin()->first.n1 );
-        
-        // Perform Prim's algorithm
-        while( Gr.size() ) {
-            typename WeightedGraph<T>::iterator largest = Gr.end();
-            
-            for( typename WeightedGraph<T>::iterator e = Gr.begin(); e != Gr.end(); ) {
-                if( verbose >= 1 )
-                    std::cout << "considering edge " << e->first << "...";
-                bool e1_in_treeV = treeV.count( e->first.n1 );
-                bool e2_in_treeV = treeV.count( e->first.n2 );
-                if( e1_in_treeV && e2_in_treeV ) {
-                    if( verbose >= 1 )
-                        std::cout << "red";
-                    Gr.erase( e++ );    // Nice trick! 
-                } else if( e1_in_treeV || e2_in_treeV ) {
-                    if( verbose >= 1 )
-                        std::cout << e->second;
-                    if( (largest == Gr.end()) || (e->second > largest->second) ) {
-                        largest = e;    // largest edge connected to the tree (until now)
-                        if( verbose >= 1 )
-                            std::cout << " and largest!";
-                    } 
-                    e++;
-                } else {
-                    if( verbose >= 1 )
-                        std::cout << "out of reach";
-                    e++;
-                }
-                if( verbose >= 1 )
-                    std::cout << std::endl;
-            }
-
-            if( largest != Gr.end() ) {
-                if( verbose >= 1 )
-                    std::cout << "largest = " << largest->first << std::endl;
-                // Add directed edge, pointing away from the root
-                if( treeV.count( largest->first.n1 ) ) {
-                    result.push_back( DEdge( largest->first.n1, largest->first.n2 ) );
-                    treeV.insert( largest->first.n2 );
-                } else {
-                    result.push_back( DEdge( largest->first.n2, largest->first.n1 ) );
-                    treeV.insert( largest->first.n1 );
-                }
-                Gr.erase( largest );
-            }
+        /// Constructs a rooted tree from a tree and a root
+        /** \pre T has no cycles and contains node \a Root
+         */
+        RootedTree( 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> RootedTree MinSpanningTreePrims( const WeightedGraph<T> &G ) {
+    RootedTree result;
+    if( G.size() > 0 ) {
+        using namespace boost;
+        using namespace std;
+        typedef adjacency_list< vecS, vecS, undirectedS, property<vertex_distance_t, int>, property<edge_weight_t, double> > boostGraph;
+        typedef pair<size_t, size_t> E;
+
+        set<size_t> nodes;
+        vector<E> edges;
+        vector<double> weights;
+        edges.reserve( G.size() );
+        weights.reserve( G.size() );
+        for( typename WeightedGraph<T>::const_iterator e = G.begin(); e != G.end(); e++ ) {
+            weights.push_back( e->second );
+            edges.push_back( E( e->first.n1, e->first.n2 ) );
+            nodes.insert( e->first.n1 );
+            nodes.insert( e->first.n2 );
         }
 
-        return result;
+        boostGraph g( edges.begin(), edges.end(), weights.begin(), nodes.size() );
+        vector< graph_traits< boostGraph >::vertex_descriptor > p( num_vertices(g) );
+        prim_minimum_spanning_tree( g, &(p[0]) );
+
+        // Store tree edges in result
+        Graph tree;
+        size_t root = 0;
+        for( size_t i = 0; i != p.size(); i++ )
+            if( p[i] != i )
+                tree.insert( UEdge( p[i], i ) );
+            else
+                root = i;
+        // Order them to obtain a rooted tree
+        result = RootedTree( tree, root );
     }
+    return result;
 }
 
 
-/// Calculate rooted tree from a tree T and a root
-DEdgeVec GrowRootedTree( const Graph & T, size_t Root );
+/// Use Prim's algorithm to construct a maximal spanning tree from the (positively) weighted graph \a G.
+/** Uses implementation in Boost Graph Library.
+ */
+template<typename T> RootedTree MaxSpanningTreePrims( const WeightedGraph<T> &G ) {
+    if( G.size() == 0 )
+        return RootedTree();
+    else {
+        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( 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++ )
+            it->second = maxweight - it->second;
+        return MinSpanningTreePrims( gr );
+    }
+}
 
 
-UEdgeVec RandomDRegularGraph( size_t N, size_t 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).
+ */
+Graph RandomDRegularGraph( size_t N, size_t d );
 
 
 } // end of namespace dai