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