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, trees and rooted trees.
  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 (source of edge)
  40         size_t n1;
  41
  42         /// Second node index (sink of edge)
  43         size_t n2;
  44
  45         /// Default constructor
  46         DEdge() {}
  47
  48         /// Constructs a directed edge pointing from \a m1 to \a m2
  49         DEdge( size_t m1, size_t m2 ) : n1(m1), n2(m2) {}
  50
  51         /// Tests for equality
  52         bool operator==( const DEdge &x ) const { return ((n1 == x.n1) && (n2 == x.n2)); }
  53
  54         /// Tests for inequality
  55         bool operator!=( const DEdge &x ) const { return !(*this == x); }
  56
  57         /// Smaller-than operator (performs lexicographical comparison)
  58         bool operator<( const DEdge &x ) const {
  59             return( (n1 < x.n1) || ((n1 == x.n1) && (n2 < x.n2)) );
  60         }
  61
  62         /// Writes a directed edge to an output stream
  63         friend std::ostream & operator << (std::ostream & os, const DEdge & e) {
  64             os << "(" << e.n1 << "," << e.n2 << ")";
  65             return os;
  66         }
  67 };
  68
  69
  70 /// Represents an undirected edge
  71 class UEdge {
  72     public:
  73         /// First node index
  74         union {
  75             size_t n1;
  76             size_t first;   /// alias
  77         };
  78         /// Second node index
  79         union {
  80             size_t n2;
  81             size_t second;  /// alias
  82         };
  83
  84         /// Default constructor
  85         UEdge() {}
  86
  87         /// Constructs an undirected edge between \a m1 and \a m2
  88         UEdge( size_t m1, size_t m2 ) : n1(m1), n2(m2) {}
  89
  90         /// Construct from DEdge
  91         UEdge( const DEdge &e ) : n1(e.n1), n2(e.n2) {}
  92
  93         /// Tests for inequality (disregarding the ordering of the nodes)
  94         bool operator==( const UEdge &x ) {
  95             return ((n1 == x.n1) && (n2 == x.n2)) || ((n1 == x.n2) && (n2 == x.n1));
  96         }
  97
  98         /// Smaller-than operator
  99         bool operator<( const UEdge &x ) const {
 100             size_t s = n1, l = n2;
 101             if( s > l )
 102                 std::swap( s, l );
 103             size_t xs = x.n1, xl = x.n2;
 104             if( xs > xl )
 105                 std::swap( xs, xl );
 106             return( (s < xs) || ((s == xs) && (l < xl)) );
 107         }
 108
 109         /// Writes an undirected edge to an output stream
 110         friend std::ostream & operator << (std::ostream & os, const UEdge & e) {
 111             if( e.n1 < e.n2 )
 112                 os << "{" << e.n1 << "," << e.n2 << "}";
 113             else
 114                 os << "{" << e.n2 << "," << e.n1 << "}";
 115             return os;
 116         }
 117 };
 118
 119
 120 /// Represents an undirected graph, implemented as a std::set of undirected edges
 121 class GraphEL : public std::set<UEdge> {
 122     public:
 123         /// Default constructor
 124         GraphEL() {}
 125
 126         /// Construct from range of objects that can be cast to DEdge
 127         template <class InputIterator>
 128         GraphEL( InputIterator begin, InputIterator end ) {
 129             insert( begin, end );
 130         }
 131 };
 132
 133
 134 /// \deprecated Please use dai::GraphEL instead.
 135 typedef GraphEL Graph;
 136
 137
 138 /// Represents an undirected weighted graph, with weights of type \a T, implemented as a std::map mapping undirected edges to weights
 139 template<class T> class WeightedGraph : public std::map<UEdge, T> {};
 140
 141
 142 /// Represents a rooted tree, implemented as a vector of directed edges
 143 /** By convention, the edges are stored such that they point away from
 144  *  the root and such that edges nearer to the root come before edges
 145  *  farther away from the root.
 146  */
 147 class RootedTree : public std::vector<DEdge> {
 148     public:
 149         /// Default constructor
 150         RootedTree() {}
 151
 152         /// Constructs a rooted tree from a tree and a root
 153         /** \pre T has no cycles and contains node \a Root
 154          */
 155         RootedTree( const GraphEL &T, size_t Root );
 156 };
 157
 158
 159 /// Uses Prim's algorithm to construct a minimal spanning tree from the (positively) weighted graph \a G.
 160 /** Uses implementation in Boost Graph Library.
 161  */
 162 template<typename T> RootedTree MinSpanningTreePrims( const WeightedGraph<T> &G ) {
 163     RootedTree result;
 164     if( G.size() > 0 ) {
 165         using namespace boost;
 166         using namespace std;
 167         typedef adjacency_list< vecS, vecS, undirectedS, property<vertex_distance_t, int>, property<edge_weight_t, double> > boostGraph;
 168         typedef pair<size_t, size_t> E;
 169
 170         set<size_t> nodes;
 171         vector<E> edges;
 172         vector<double> weights;
 173         edges.reserve( G.size() );
 174         weights.reserve( G.size() );
 175         for( typename WeightedGraph<T>::const_iterator e = G.begin(); e != G.end(); e++ ) {
 176             weights.push_back( e->second );
 177             edges.push_back( E( e->first.n1, e->first.n2 ) );
 178             nodes.insert( e->first.n1 );
 179             nodes.insert( e->first.n2 );
 180         }
 181
 182         boostGraph g( edges.begin(), edges.end(), weights.begin(), nodes.size() );
 183         vector< graph_traits< boostGraph >::vertex_descriptor > p( num_vertices(g) );
 184         prim_minimum_spanning_tree( g, &(p[0]) );
 185
 186         // Store tree edges in result
 187         GraphEL tree;
 188         size_t root = 0;
 189         for( size_t i = 0; i != p.size(); i++ )
 190             if( p[i] != i )
 191                 tree.insert( UEdge( p[i], i ) );
 192             else
 193                 root = i;
 194         // Order them to obtain a rooted tree
 195         result = RootedTree( tree, root );
 196     }
 197     return result;
 198 }
 199
 200
 201 /// Use Prim's algorithm to construct a maximal spanning tree from the (positively) weighted graph \a G.
 202 /** Uses implementation in Boost Graph Library.
 203  */
 204 template<typename T> RootedTree MaxSpanningTreePrims( const WeightedGraph<T> &G ) {
 205     if( G.size() == 0 )
 206         return RootedTree();
 207     else {
 208         T maxweight = G.begin()->second;
 209         for( typename WeightedGraph<T>::const_iterator it = G.begin(); it != G.end(); it++ )
 210             if( it->second > maxweight )
 211                 maxweight = it->second;
 212         // make a copy of the graph
 213         WeightedGraph<T> gr( G );
 214         // invoke MinSpanningTreePrims with negative weights
 215         // (which have to be shifted to satisfy positivity criterion)
 216         for( typename WeightedGraph<T>::iterator it = gr.begin(); it != gr.end(); it++ )
 217             it->second = maxweight - it->second;
 218         return MinSpanningTreePrims( gr );
 219     }
 220 }
 221
 222
 223 /// Constructs a random undirected graph of \a N nodes, where each node has connectivity \a d
 224 /** Algorithm 1 in [\ref StW99].
 225  *  Draws a random graph of size \a N and uniform degree \a d
 226  *  from an almost uniform probability distribution over these graphs
 227  *  (which becomes uniform in the limit that \a d is small and \a N goes
 228  *  to infinity).
 229  */
 230 GraphEL RandomDRegularGraph( size_t N, size_t d );
 231
 232
 233 } // end of namespace dai
 234
 235
 236 #endif