15 #ifndef __defined_libdai_weightedgraph_h
16 #define __defined_libdai_weightedgraph_h
26 #include <boost/graph/adjacency_list.hpp>
27 #include <boost/graph/prim_minimum_spanning_tree.hpp>
28 #include <boost/graph/kruskal_min_spanning_tree.hpp>
98 return( (s < xs) || ((s == xs) && (l < xl)) );
119 template <
class InputIterator>
120 GraphEL( InputIterator begin, InputIterator end ) {
121 insert( begin, end );
126 for(
size_t n1 = 0; n1 < G.
nrNodes(); n1++ )
129 insert(
UEdge( n1, n2 ) );
164 using namespace boost;
166 typedef adjacency_list< vecS, vecS, undirectedS, no_property, property<edge_weight_t, double> > boostGraph;
170 vector<double> weights;
171 edges.reserve( G.size() );
172 weights.reserve( G.size() );
174 weights.push_back( e->second );
175 edges.push_back( e->first );
176 nodes.insert( e->first.first );
177 nodes.insert( e->first.second );
180 size_t N = nodes.size();
181 for( set<size_t>::const_iterator it = nodes.begin(); it != nodes.end(); it++ )
183 DAI_THROWE(RUNTIME_ERROR,
"Vertices must be in range [0..N) where N is the number of vertices.");
185 boostGraph g( edges.begin(), edges.end(), weights.begin(), nodes.size() );
186 size_t root = *(nodes.begin());
190 vector< graph_traits< boostGraph >::vertex_descriptor > p(N);
191 prim_minimum_spanning_tree( g, &(p[0]) );
194 for(
size_t i = 0; i != p.size(); i++ ) {
196 tree.insert(
UEdge( p[i], i ) );
200 vector< graph_traits< boostGraph >::edge_descriptor > t;
202 kruskal_minimum_spanning_tree( g, std::back_inserter(t) );
205 for(
size_t i = 0; i != t.size(); i++ ) {
206 size_t v1 = source( t[i], g );
207 size_t v2 = target( t[i], g );
209 tree.insert(
UEdge( v1, v2 ) );
230 T maxweight = G.begin()->second;
232 if( it->second > maxweight )
233 maxweight = it->second;
239 it->second = maxweight - it->second;