1 /* This file is part of libDAI - http://www.libdai.org/
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.
7 * Copyright (C) 2006-2009 Joris Mooij [joris dot mooij at libdai dot org]
8 * Copyright (C) 2006-2007 Radboud University Nijmegen, The Netherlands
13 * \brief Defines some utility functions for (weighted) undirected graphs, trees and rooted trees.
14 * \todo Improve general support for graphs and trees.
18 #ifndef __defined_libdai_weightedgraph_h
19 #define __defined_libdai_weightedgraph_h
27 #include <climits> // Work-around for bug in boost graph library
29 #include <boost/graph/adjacency_list.hpp>
30 #include <boost/graph/prim_minimum_spanning_tree.hpp>
36 /// Represents a directed edge
39 /// First node index (source of edge)
42 /// Second node index (sink of edge)
45 /// Default constructor
48 /// Constructs a directed edge pointing from \a m1 to \a m2
49 DEdge( size_t m1
, size_t m2
) : n1(m1
), n2(m2
) {}
51 /// Tests for equality
52 bool operator==( const DEdge
&x
) const { return ((n1
== x
.n1
) && (n2
== x
.n2
)); }
54 /// Tests for inequality
55 bool operator!=( const DEdge
&x
) const { return !(*this == x
); }
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
)) );
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
<< ")";
70 /// Represents an undirected edge
76 size_t first
; /// alias
81 size_t second
; /// alias
84 /// Default constructor
87 /// Constructs an undirected edge between \a m1 and \a m2
88 UEdge( size_t m1
, size_t m2
) : n1(m1
), n2(m2
) {}
90 /// Construct from DEdge
91 UEdge( const DEdge
&e
) : n1(e
.n1
), n2(e
.n2
) {}
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
));
98 /// Smaller-than operator
99 bool operator<( const UEdge
&x
) const {
100 size_t s
= n1
, l
= n2
;
103 size_t xs
= x
.n1
, xl
= x
.n2
;
106 return( (s
< xs
) || ((s
== xs
) && (l
< xl
)) );
109 /// Writes an undirected edge to an output stream
110 friend std::ostream
& operator << (std::ostream
& os
, const UEdge
& e
) {
112 os
<< "{" << e
.n1
<< "," << e
.n2
<< "}";
114 os
<< "{" << e
.n2
<< "," << e
.n1
<< "}";
120 /// Represents an undirected graph, implemented as a std::set of undirected edges
121 class GraphEL
: public std::set
<UEdge
> {
123 /// Default constructor
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
);
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
> {};
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.
143 class RootedTree
: public std::vector
<DEdge
> {
145 /// Default constructor
148 /// Constructs a rooted tree from a tree and a root
149 /** \pre T has no cycles and contains node \a Root
151 RootedTree( const GraphEL
&T
, size_t Root
);
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.
158 template<typename T
> RootedTree
MinSpanningTreePrims( const WeightedGraph
<T
> &G
) {
161 using namespace boost
;
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
;
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
);
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]) );
182 // Store tree edges in result
185 for( size_t i
= 0; i
!= p
.size(); i
++ )
187 tree
.insert( UEdge( p
[i
], i
) );
190 // Order them to obtain a rooted tree
191 result
= RootedTree( tree
, root
);
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.
200 template<typename T
> RootedTree
MaxSpanningTreePrims( const WeightedGraph
<T
> &G
) {
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
);
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
226 GraphEL
RandomDRegularGraph( size_t N
, size_t d
);
229 } // end of namespace dai