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