include/dai/weightedgraph.h

   1 /*  This file is part of libDAI - http://www.libdai.org/
   2  *
   3  *  libDAI is licensed under the terms of the GNU General Public License version
   4  *  2, or (at your option) any later version. libDAI is distributed without any
   5  *  warranty. See the file COPYING for more details.
   6  *
   7  *  Copyright (C) 2006-2009  Joris Mooij  [joris dot mooij at libdai dot org]
   8  *  Copyright (C) 2006-2007  Radboud University Nijmegen, The Netherlands
   9  */
  10
  11
  12 /** \file
  13  *  \brief Defines some utility functions for (weighted) undirected graphs
  14  *  \todo Improve general support for graphs and trees.
  15  */
  16
  17
  18 #ifndef __defined_libdai_weightedgraph_h
  19 #define __defined_libdai_weightedgraph_h
  20
  21
  22 #include <vector>
  23 #include <map>
  24 #include <iostream>
  25 #include <set>
  26 #include <limits>
  27 #include <climits>   // Work-around for bug in boost graph library
  28
  29 #include <boost/graph/adjacency_list.hpp>
  30 #include <boost/graph/prim_minimum_spanning_tree.hpp>
  31
  32
  33 namespace dai {
  34
  35
  36 /// Represents a directed edge
  37 class DEdge {
  38     public:
  39         /// First node index
  40         size_t n1;
  41         /// Second node index
  42         size_t n2;
  43
  44         /// Default constructor
  45         DEdge() {}
  46
  47         /// Constructs a directed edge pointing from \a m1 to \a m2
  48         DEdge( size_t m1, size_t m2 ) : n1(m1), n2(m2) {}
  49
  50         /// Tests for equality
  51         bool operator==( const DEdge &x ) const { return ((n1 == x.n1) && (n2 == x.n2)); }
  52
  53         /// Tests for inequality
  54         bool operator!=( const DEdge &x ) const { return !(*this == x); }
  55
  56         /// Smaller-than operator (performs lexicographical comparison)
  57         bool operator<( const DEdge &x ) const {
  58             return( (n1 < x.n1) || ((n1 == x.n1) && (n2 < x.n2)) );
  59         }
  60
  61         /// Writes a directed edge to an output stream
  62         friend std::ostream & operator << (std::ostream & os, const DEdge & e) {
  63             os << "(" << e.n1 << "," << e.n2 << ")";
  64             return os;
  65         }
  66 };
  67
  68
  69 /// Represents an undirected edge
  70 class UEdge {
  71     public:
  72         /// First node index
  73         size_t  n1;
  74         /// Second node index
  75         size_t  n2;
  76
  77         /// Default constructor
  78         UEdge() {}
  79
  80         /// Constructs an undirected edge between \a m1 and \a m2
  81         UEdge( size_t m1, size_t m2 ) : n1(m1), n2(m2) {}
  82
  83         /// Construct from DEdge
  84         UEdge( const DEdge &e ) : n1(e.n1), n2(e.n2) {}
  85
  86         /// Tests for inequality (disregarding the ordering of the nodes)
  87         bool operator==( const UEdge &x ) {
  88             return ((n1 == x.n1) && (n2 == x.n2)) || ((n1 == x.n2) && (n2 == x.n1));
  89         }
  90
  91         /// Smaller-than operator
  92         bool operator<( const UEdge &x ) const {
  93             size_t s = n1, l = n2;
  94             if( s > l )
  95                 std::swap( s, l );
  96             size_t xs = x.n1, xl = x.n2;
  97             if( xs > xl )
  98                 std::swap( xs, xl );
  99             return( (s < xs) || ((s == xs) && (l < xl)) );
 100         }
 101
 102         /// Writes an undirected edge to an output stream
 103         friend std::ostream & operator << (std::ostream & os, const UEdge & e) {
 104             if( e.n1 < e.n2 )
 105                 os << "{" << e.n1 << "," << e.n2 << "}";
 106             else
 107                 os << "{" << e.n2 << "," << e.n1 << "}";
 108             return os;
 109         }
 110 };
 111
 112
 113 /// Vector of UEdge
 114 typedef std::vector<UEdge>  UEdgeVec;
 115
 116 /// Vector of DEdge
 117 typedef std::vector<DEdge>  DEdgeVec;
 118
 119 /// Represents an undirected weighted graph, with weights of type \a T
 120 template<class T> class WeightedGraph : public std::map<UEdge, T> {};
 121
 122 /// Represents an undirected graph
 123 typedef std::set<UEdge>     Graph;
 124
 125
 126 /// Constructs a rooted tree from a tree and a root
 127 /** \pre T has no cycles and contains node \a Root
 128  */
 129 DEdgeVec GrowRootedTree( const Graph &T, size_t Root );
 130
 131
 132 /// Uses Prim's algorithm to construct a minimal spanning tree from the (positively) weighted graph \a G.
 133 /** Uses implementation in Boost Graph Library.
 134  */
 135 template<typename T> DEdgeVec MinSpanningTreePrims( const WeightedGraph<T> &G ) {
 136     DEdgeVec result;
 137     if( G.size() > 0 ) {
 138         using namespace boost;
 139         using namespace std;
 140         typedef adjacency_list< vecS, vecS, undirectedS, property<vertex_distance_t, int>, property<edge_weight_t, double> > boostGraph;
 141         typedef pair<size_t, size_t> E;
 142
 143         set<size_t> nodes;
 144         vector<E> edges;
 145         vector<double> weights;
 146         edges.reserve( G.size() );
 147         weights.reserve( G.size() );
 148         for( typename WeightedGraph<T>::const_iterator e = G.begin(); e != G.end(); e++ ) {
 149             weights.push_back( e->second );
 150             edges.push_back( E( e->first.n1, e->first.n2 ) );
 151             nodes.insert( e->first.n1 );
 152             nodes.insert( e->first.n2 );
 153         }
 154
 155         boostGraph g( edges.begin(), edges.end(), weights.begin(), nodes.size() );
 156         vector< graph_traits< boostGraph >::vertex_descriptor > p( num_vertices(g) );
 157         prim_minimum_spanning_tree( g, &(p[0]) );
 158
 159         // Store tree edges in result
 160         Graph tree;
 161         size_t root = 0;
 162         for( size_t i = 0; i != p.size(); i++ )
 163             if( p[i] != i )
 164                 tree.insert( UEdge( p[i], i ) );
 165             else
 166                 root = i;
 167         // Order them
 168         result = GrowRootedTree( tree, root );
 169     }
 170
 171     return result;
 172 }
 173
 174
 175 /// Use Prim's algorithm to construct a minimal spanning tree from the (positively) weighted graph \a G.
 176 /** Uses implementation in Boost Graph Library.
 177  */
 178 template<typename T> DEdgeVec MaxSpanningTreePrims( const WeightedGraph<T> &G ) {
 179     if( G.size() == 0 )
 180         return DEdgeVec();
 181     else {
 182         T maxweight = G.begin()->second;
 183         for( typename WeightedGraph<T>::const_iterator it = G.begin(); it != G.end(); it++ )
 184             if( it->second > maxweight )
 185                 maxweight = it->second;
 186         // make a copy of the graph
 187         WeightedGraph<T> gr( G );
 188         // invoke MinSpanningTreePrims with negative weights
 189         // (which have to be shifted to satisfy positivity criterion)
 190         for( typename WeightedGraph<T>::iterator it = gr.begin(); it != gr.end(); it++ )
 191             it->second = maxweight - it->second;
 192         return MinSpanningTreePrims( gr );
 193     }
 194 }
 195
 196
 197 /// Constructs a random undirected graph of \a N nodes, where each node has connectivity \a d
 198 /** Algorithm 1 in [\ref StW99].
 199  *  Draws a random graph of size \a N and uniform degree \a d
 200  *  from an almost uniform probability distribution over these graphs
 201  *  (which becomes uniform in the limit that \a d is small and \a N goes
 202  *  to infinity).
 203  */
 204 UEdgeVec RandomDRegularGraph( size_t N, size_t d );
 205
 206
 207 } // end of namespace dai
 208
 209
 210 #endif