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
5 This file is part of libDAI.
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.
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.
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
24 * \brief Defines some utility functions for weighted graphs
25 * \todo Improve documentation
26 * \todo Improve general support for graphs and trees.
30 #ifndef __defined_libdai_weightedgraph_h
31 #define __defined_libdai_weightedgraph_h
41 #include <boost/graph/adjacency_list.hpp>
42 #include <boost/graph/prim_minimum_spanning_tree.hpp>
48 /// Represents a directed edge pointing from n1 to n2
51 size_t n1
; ///< First node index
52 size_t n2
; ///< Second node index
54 /// Default constructor
58 DEdge( size_t m1
, size_t m2
) : n1(m1
), n2(m2
) {}
60 /// Tests for equality
61 bool operator==( const DEdge
&x
) const { return ((n1
== x
.n1
) && (n2
== x
.n2
)); }
63 /// Tests for inequality
64 bool operator!=( const DEdge
&x
) const { return !(*this == x
); }
66 /// Smaller-than operator (performs lexicographical comparison)
67 bool operator<( const DEdge
&x
) const {
68 return( (n1
< x
.n1
) || ((n1
== x
.n1
) && (n2
< x
.n2
)) );
71 /// Writes a DEdge to an output stream
72 friend std::ostream
& operator << (std::ostream
& os
, const DEdge
& e
) {
73 os
<< "(" << e
.n1
<< "," << e
.n2
<< ")";
79 /// Undirected edge between nodes n1 and n2
82 size_t n1
; ///< First node index
83 size_t n2
; ///< Second node index
85 /// Default constructor
89 UEdge( size_t m1
, size_t m2
) : n1(m1
), n2(m2
) {}
91 /// Construct from DEdge
92 UEdge( const DEdge
& e
) : n1(e
.n1
), n2(e
.n2
) {}
94 /// Tests for inequality (disregarding the ordering of n1 and n2)
95 bool operator==( const UEdge
&x
) {
96 return ((n1
== x
.n1
) && (n2
== x
.n2
)) || ((n1
== x
.n2
) && (n2
== x
.n1
));
99 /// Smaller-than operator
100 bool operator<( const UEdge
&x
) const {
101 size_t s
= n1
, l
= n2
;
104 size_t xs
= x
.n1
, xl
= x
.n2
;
107 return( (s
< xs
) || ((s
== xs
) && (l
< xl
)) );
110 /// Writes a UEdge to an output stream
111 friend std::ostream
& operator << (std::ostream
& os
, const UEdge
& e
) {
113 os
<< "{" << e
.n1
<< "," << e
.n2
<< "}";
115 os
<< "{" << e
.n2
<< "," << e
.n1
<< "}";
122 typedef std::vector
<UEdge
> UEdgeVec
;
125 typedef std::vector
<DEdge
> DEdgeVec
;
127 /// Represents an undirected weighted graph, with weights of type T
128 template<class T
> class WeightedGraph
: public std::map
<UEdge
, T
> {};
130 /// Represents an undirected graph
131 typedef std::set
<UEdge
> Graph
;
134 /// Uses Prim's algorithm to construct a minimal spanning tree from the (positively) weighted graph G.
135 /** Uses implementation in Boost Graph Library.
137 template<typename T
> DEdgeVec
MinSpanningTreePrims( const WeightedGraph
<T
> &G
) {
140 using namespace boost
;
142 typedef adjacency_list
< vecS
, vecS
, undirectedS
, property
<vertex_distance_t
, int>, property
<edge_weight_t
, double> > boostGraph
;
143 typedef pair
<size_t, size_t> E
;
147 vector
<double> weights
;
148 edges
.reserve( G
.size() );
149 weights
.reserve( G
.size() );
150 for( typename WeightedGraph
<T
>::const_iterator e
= G
.begin(); e
!= G
.end(); e
++ ) {
151 weights
.push_back( e
->second
);
152 edges
.push_back( E( e
->first
.n1
, e
->first
.n2
) );
153 nodes
.insert( e
->first
.n1
);
154 nodes
.insert( e
->first
.n2
);
157 boostGraph
g( edges
.begin(), edges
.end(), weights
.begin(), nodes
.size() );
158 vector
< graph_traits
< boostGraph
>::vertex_descriptor
> p( num_vertices(g
) );
159 prim_minimum_spanning_tree( g
, &(p
[0]) );
161 // Store tree edges in result
162 result
.reserve( nodes
.size() - 1 );
164 for( size_t i
= 0; i
!= p
.size(); i
++ )
166 result
.push_back( DEdge( p
[i
], i
) );
170 // We have to store the minimum spanning tree in the right
171 // order, such that for all (i1, j1), (i2, j2) in result,
172 // if j1 == i2 then (i1, j1) comes before (i2, j2) in result.
173 // We do this by reordering the contents of result, effectively
174 // growing the tree starting at the root. At each step,
175 // result[0..N-1] are the edges already added to the tree,
176 // whereas the other elements of result still have to be added.
177 // The elements of nodes are the vertices that still have to
178 // be added to the tree.
180 // Start with the root
184 // Iteratively add edges and nodes to the growing tree
185 while( N
!= result
.size() ) {
186 for( size_t e
= N
; e
!= result
.size(); e
++ ) {
187 bool e1_in_tree
= !nodes
.count( result
[e
].n1
);
189 nodes
.erase( result
[e
].n2
);
190 swap( result
[N
], result
[e
] );
202 /// Use Prim's algorithm to construct a minimal spanning tree from the (positively) weighted graph G.
203 /** Uses implementation in Boost Graph Library.
205 template<typename T
> DEdgeVec
MaxSpanningTreePrims( const WeightedGraph
<T
> & Graph
) {
206 T maxweight
= Graph
.begin()->second
;
207 for( typename WeightedGraph
<T
>::const_iterator it
= Graph
.begin(); it
!= Graph
.end(); it
++ )
208 if( it
->second
> maxweight
)
209 maxweight
= it
->second
;
210 // make a copy of the graph
211 WeightedGraph
<T
> gr( Graph
);
212 // invoke MinSpanningTreePrims with negative weights
213 // (which have to be shifted to satisfy positivity criterion)
214 for( typename WeightedGraph
<T
>::iterator it
= gr
.begin(); it
!= gr
.end(); it
++ )
215 it
->second
= maxweight
- it
->second
;
216 return MinSpanningTreePrims( gr
);
220 /// Constructs a rooted tree from a tree and a root
221 DEdgeVec
GrowRootedTree( const Graph
& T
, size_t Root
);
224 /// Constructs a random undirected graph of N nodes, where each node has connectivity d
225 UEdgeVec
RandomDRegularGraph( size_t N
, size_t d
);
228 } // end of namespace dai