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 /// Represents an undirected weighted graph, with weights of type \a T, implemented as a std::map mapping undirected edges to weights
 135 template<class T> class WeightedGraph : public std::map<UEdge, T> {};
 136
 137
 138 /// Represents a rooted tree, implemented as a vector of directed edges
 139 /** By convention, the edges are stored such that they point away from
 140  *  the root and such that edges nearer to the root come before edges
 141  *  farther away from the root.
 142  */
 143 class RootedTree : public std::vector<DEdge> {
 144     public:
 145         /// Default constructor
 146         RootedTree() {}
 147
 148         /// Constructs a rooted tree from a tree and a root
 149         /** \pre T has no cycles and contains node \a Root
 150          */
 151         RootedTree( const GraphEL &T, size_t Root );
 152 };
 153
 154
 155 /// Uses Prim's algorithm to construct a minimal spanning tree from the (positively) weighted graph \a G.
 156 /** Uses implementation in Boost Graph Library.
 157  */
 158 template<typename T> RootedTree MinSpanningTreePrims( const WeightedGraph<T> &G ) {
 159     RootedTree result;
 160     if( G.size() > 0 ) {
 161         using namespace boost;
 162         using namespace std;
 163         typedef adjacency_list< vecS, vecS, undirectedS, property<vertex_distance_t, int>, property<edge_weight_t, double> > boostGraph;
 164         typedef pair<size_t, size_t> E;
 165
 166         set<size_t> nodes;
 167         vector<E> edges;
 168         vector<double> weights;
 169         edges.reserve( G.size() );
 170         weights.reserve( G.size() );
 171         for( typename WeightedGraph<T>::const_iterator e = G.begin(); e != G.end(); e++ ) {
 172             weights.push_back( e->second );
 173             edges.push_back( E( e->first.n1, e->first.n2 ) );
 174             nodes.insert( e->first.n1 );
 175             nodes.insert( e->first.n2 );
 176         }
 177
 178         boostGraph g( edges.begin(), edges.end(), weights.begin(), nodes.size() );
 179         vector< graph_traits< boostGraph >::vertex_descriptor > p( num_vertices(g) );
 180         prim_minimum_spanning_tree( g, &(p[0]) );
 181
 182         // Store tree edges in result
 183         GraphEL tree;
 184         size_t root = 0;
 185         for( size_t i = 0; i != p.size(); i++ )
 186             if( p[i] != i )
 187                 tree.insert( UEdge( p[i], i ) );
 188             else
 189                 root = i;
 190         // Order them to obtain a rooted tree
 191         result = RootedTree( tree, root );
 192     }
 193     return result;
 194 }
 195
 196
 197 /// Use Prim's algorithm to construct a maximal spanning tree from the (positively) weighted graph \a G.
 198 /** Uses implementation in Boost Graph Library.
 199  */
 200 template<typename T> RootedTree MaxSpanningTreePrims( const WeightedGraph<T> &G ) {
 201     if( G.size() == 0 )
 202         return RootedTree();
 203     else {
 204         T maxweight = G.begin()->second;
 205         for( typename WeightedGraph<T>::const_iterator it = G.begin(); it != G.end(); it++ )
 206             if( it->second > maxweight )
 207                 maxweight = it->second;
 208         // make a copy of the graph
 209         WeightedGraph<T> gr( G );
 210         // invoke MinSpanningTreePrims with negative weights
 211         // (which have to be shifted to satisfy positivity criterion)
 212         for( typename WeightedGraph<T>::iterator it = gr.begin(); it != gr.end(); it++ )
 213             it->second = maxweight - it->second;
 214         return MinSpanningTreePrims( gr );
 215     }
 216 }
 217
 218
 219 /// Constructs a random undirected graph of \a N nodes, where each node has connectivity \a d
 220 /** Algorithm 1 in [\ref StW99].
 221  *  Draws a random graph of size \a N and uniform degree \a d
 222  *  from an almost uniform probability distribution over these graphs
 223  *  (which becomes uniform in the limit that \a d is small and \a N goes
 224  *  to infinity).
 225  */
 226 GraphEL RandomDRegularGraph( size_t N, size_t d );
 227
 228
 229 } // end of namespace dai
 230
 231
 232 #endif