Significant improvement of documentation
[libdai.git] / include / dai / weightedgraph.h
1 /* Copyright (C) 2006-2008 Joris Mooij [joris dot mooij at tuebingen dot mpg dot de]
2 Radboud University Nijmegen, The Netherlands /
3 Max Planck Institute for Biological Cybernetics, Germany
4
5 This file is part of libDAI.
6
7 libDAI is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
11
12 libDAI is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with libDAI; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20 */
21
22
23 /// \file
24 /// \brief Defines some utility functions for weighted graphs
25
26
27 #ifndef __defined_libdai_weightedgraph_h
28 #define __defined_libdai_weightedgraph_h
29
30
31 #include <vector>
32 #include <map>
33 #include <iostream>
34 #include <set>
35 #include <cassert>
36 #include <limits>
37
38 #include <boost/graph/adjacency_list.hpp>
39 #include <boost/graph/prim_minimum_spanning_tree.hpp>
40
41
42 namespace dai {
43
44
45 /// Represents a directed edge pointing from n1 to n2
46 class DEdge {
47 public:
48 size_t n1; ///< First node index
49 size_t n2; ///< Second node index
50
51 /// Default constructor
52 DEdge() {}
53
54 /// Constructor
55 DEdge( size_t m1, size_t m2 ) : n1(m1), n2(m2) {}
56
57 /// Tests for equality
58 bool operator==( const DEdge &x ) const { return ((n1 == x.n1) && (n2 == x.n2)); }
59
60 /// Tests for inequality
61 bool operator!=( const DEdge &x ) const { return !(*this == x); }
62
63 /// Smaller-than operator (performs lexicographical comparison)
64 bool operator<( const DEdge &x ) const {
65 return( (n1 < x.n1) || ((n1 == x.n1) && (n2 < x.n2)) );
66 }
67
68 /// Writes a DEdge to an output stream
69 friend std::ostream & operator << (std::ostream & os, const DEdge & e) {
70 os << "(" << e.n1 << "," << e.n2 << ")";
71 return os;
72 }
73 };
74
75
76 /// Undirected edge between nodes n1 and n2
77 class UEdge {
78 public:
79 size_t n1; ///< First node index
80 size_t n2; ///< Second node index
81
82 /// Default constructor
83 UEdge() {}
84
85 /// Constructor
86 UEdge( size_t m1, size_t m2 ) : n1(m1), n2(m2) {}
87
88 /// Construct from DEdge
89 UEdge( const DEdge & e ) : n1(e.n1), n2(e.n2) {}
90
91 /// Tests for inequality (disregarding the ordering of n1 and n2)
92 bool operator==( const UEdge &x ) {
93 return ((n1 == x.n1) && (n2 == x.n2)) || ((n1 == x.n2) && (n2 == x.n1));
94 }
95
96 /// Smaller-than operator
97 bool operator<( const UEdge &x ) const {
98 size_t s = n1, l = n2;
99 if( s > l )
100 std::swap( s, l );
101 size_t xs = x.n1, xl = x.n2;
102 if( xs > xl )
103 std::swap( xs, xl );
104 return( (s < xs) || ((s == xs) && (l < xl)) );
105 }
106
107 /// Writes a UEdge to an output stream
108 friend std::ostream & operator << (std::ostream & os, const UEdge & e) {
109 if( e.n1 < e.n2 )
110 os << "{" << e.n1 << "," << e.n2 << "}";
111 else
112 os << "{" << e.n2 << "," << e.n1 << "}";
113 return os;
114 }
115 };
116
117
118 /// Vector of UEdge
119 typedef std::vector<UEdge> UEdgeVec;
120
121 /// Vector of DEdge
122 typedef std::vector<DEdge> DEdgeVec;
123
124 /// Represents an undirected weighted graph, with weights of type T
125 template<class T> class WeightedGraph : public std::map<UEdge, T> {};
126
127 /// Represents an undirected graph
128 typedef std::set<UEdge> Graph;
129
130
131 /// Uses Prim's algorithm to construct a minimal spanning tree from the (positively) weighted graph G.
132 /** Uses implementation in Boost Graph Library.
133 */
134 template<typename T> DEdgeVec MinSpanningTreePrims( const WeightedGraph<T> &G ) {
135 DEdgeVec result;
136 if( G.size() > 0 ) {
137 using namespace boost;
138 using namespace std;
139 typedef adjacency_list< vecS, vecS, undirectedS, property<vertex_distance_t, int>, property<edge_weight_t, double> > boostGraph;
140 typedef pair<size_t, size_t> E;
141
142 set<size_t> nodes;
143 vector<E> edges;
144 vector<double> weights;
145 edges.reserve( G.size() );
146 weights.reserve( G.size() );
147 for( typename WeightedGraph<T>::const_iterator e = G.begin(); e != G.end(); e++ ) {
148 weights.push_back( e->second );
149 edges.push_back( E( e->first.n1, e->first.n2 ) );
150 nodes.insert( e->first.n1 );
151 nodes.insert( e->first.n2 );
152 }
153
154 boostGraph g( edges.begin(), edges.end(), weights.begin(), nodes.size() );
155 vector< graph_traits< boostGraph >::vertex_descriptor > p( num_vertices(g) );
156 prim_minimum_spanning_tree( g, &(p[0]) );
157
158 // Store tree edges in result
159 result.reserve( nodes.size() - 1 );
160 size_t root = 0;
161 for( size_t i = 0; i != p.size(); i++ )
162 if( p[i] != i )
163 result.push_back( DEdge( p[i], i ) );
164 else
165 root = i;
166
167 // We have to store the minimum spanning tree in the right
168 // order, such that for all (i1, j1), (i2, j2) in result,
169 // if j1 == i2 then (i1, j1) comes before (i2, j2) in result.
170 // We do this by reordering the contents of result, effectively
171 // growing the tree starting at the root. At each step,
172 // result[0..N-1] are the edges already added to the tree,
173 // whereas the other elements of result still have to be added.
174 // The elements of nodes are the vertices that still have to
175 // be added to the tree.
176
177 // Start with the root
178 nodes.erase( root );
179 size_t N = 0;
180
181 // Iteratively add edges and nodes to the growing tree
182 while( N != result.size() ) {
183 for( size_t e = N; e != result.size(); e++ ) {
184 bool e1_in_tree = !nodes.count( result[e].n1 );
185 if( e1_in_tree ) {
186 nodes.erase( result[e].n2 );
187 swap( result[N], result[e] );
188 N++;
189 break;
190 }
191 }
192 }
193 }
194
195 return result;
196 }
197
198
199 /// Use Prim's algorithm to construct a minimal spanning tree from the (positively) weighted graph G.
200 /** Uses implementation in Boost Graph Library.
201 */
202 template<typename T> DEdgeVec MaxSpanningTreePrims( const WeightedGraph<T> & Graph ) {
203 T maxweight = Graph.begin()->second;
204 for( typename WeightedGraph<T>::const_iterator it = Graph.begin(); it != Graph.end(); it++ )
205 if( it->second > maxweight )
206 maxweight = it->second;
207 // make a copy of the graph
208 WeightedGraph<T> gr( Graph );
209 // invoke MinSpanningTreePrims with negative weights
210 // (which have to be shifted to satisfy positivity criterion)
211 for( typename WeightedGraph<T>::iterator it = gr.begin(); it != gr.end(); it++ )
212 it->second = maxweight - it->second;
213 return MinSpanningTreePrims( gr );
214 }
215
216
217 /// Constructs a rooted tree from a tree and a root
218 DEdgeVec GrowRootedTree( const Graph & T, size_t Root );
219
220
221 /// Constructs a random undirected graph of N nodes, where each node has connectivity d
222 UEdgeVec RandomDRegularGraph( size_t N, size_t d );
223
224
225 } // end of namespace dai
226
227
228 #endif