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
27 #ifndef __defined_libdai_weightedgraph_h
28 #define __defined_libdai_weightedgraph_h
38 #include <boost/graph/adjacency_list.hpp>
39 #include <boost/graph/prim_minimum_spanning_tree.hpp>
45 /// Represents a directed edge pointing from n1 to n2
48 size_t n1
; ///< First node index
49 size_t n2
; ///< Second node index
51 /// Default constructor
55 DEdge( size_t m1
, size_t m2
) : n1(m1
), n2(m2
) {}
57 /// Tests for equality
58 bool operator==( const DEdge
&x
) const { return ((n1
== x
.n1
) && (n2
== x
.n2
)); }
60 /// Tests for inequality
61 bool operator!=( const DEdge
&x
) const { return !(*this == x
); }
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
)) );
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
<< ")";
76 /// Undirected edge between nodes n1 and n2
79 size_t n1
; ///< First node index
80 size_t n2
; ///< Second node index
82 /// Default constructor
86 UEdge( size_t m1
, size_t m2
) : n1(m1
), n2(m2
) {}
88 /// Construct from DEdge
89 UEdge( const DEdge
& e
) : n1(e
.n1
), n2(e
.n2
) {}
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
));
96 /// Smaller-than operator
97 bool operator<( const UEdge
&x
) const {
98 size_t s
= n1
, l
= n2
;
101 size_t xs
= x
.n1
, xl
= x
.n2
;
104 return( (s
< xs
) || ((s
== xs
) && (l
< xl
)) );
107 /// Writes a UEdge to an output stream
108 friend std::ostream
& operator << (std::ostream
& os
, const UEdge
& e
) {
110 os
<< "{" << e
.n1
<< "," << e
.n2
<< "}";
112 os
<< "{" << e
.n2
<< "," << e
.n1
<< "}";
119 typedef std::vector
<UEdge
> UEdgeVec
;
122 typedef std::vector
<DEdge
> DEdgeVec
;
124 /// Represents an undirected weighted graph, with weights of type T
125 template<class T
> class WeightedGraph
: public std::map
<UEdge
, T
> {};
127 /// Represents an undirected graph
128 typedef std::set
<UEdge
> Graph
;
131 /// Uses Prim's algorithm to construct a minimal spanning tree from the (positively) weighted graph G.
132 /** Uses implementation in Boost Graph Library.
134 template<typename T
> DEdgeVec
MinSpanningTreePrims( const WeightedGraph
<T
> &G
) {
137 using namespace boost
;
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
;
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
);
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]) );
158 // Store tree edges in result
159 result
.reserve( nodes
.size() - 1 );
161 for( size_t i
= 0; i
!= p
.size(); i
++ )
163 result
.push_back( DEdge( p
[i
], i
) );
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.
177 // Start with the root
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
);
186 nodes
.erase( result
[e
].n2
);
187 swap( result
[N
], result
[e
] );
199 /// Use Prim's algorithm to construct a minimal spanning tree from the (positively) weighted graph G.
200 /** Uses implementation in Boost Graph Library.
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
);
217 /// Constructs a rooted tree from a tree and a root
218 DEdgeVec
GrowRootedTree( const Graph
& T
, size_t Root
);
221 /// Constructs a random undirected graph of N nodes, where each node has connectivity d
222 UEdgeVec
RandomDRegularGraph( size_t N
, size_t d
);
225 } // end of namespace dai