Improved documentation of include/dai/weightedgraph.h
[libdai.git] / 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