Re: [Boost-users] BGL and maximum spanning trees

From: Doug Gregor (dgregor_at_[hidden])
Date: 2006-09-22 10:31:59

Hello,

On Sep 22, 2006, at 4:26 AM, aitor wrote:
> in my project i need to compute the maximum spanning tree of an
> undirected weighted graph. One possible solution is to could
> iteratively convert each weight wij to 1/wij and apply
> prim_minimum_spanning_tree algorithm over it.

Or create a property map adaptor that converts the property map for w  
into a property map for 1/w.

> However, i wonder if i could slightly change the
> prim_minimum_spanning_tree algorithm to a prim_maximum_spanning_tree
> function by changing only the compare predicate (in line 39 of
> prim_minimum_spanning_tree.hpp) from
>
> std::less<W> compare;
>
> to
>
> std::greater<W> compare;
>
> Wold then the function compute a maximum spanning tree ? Or am i
> missing something important ?

I believe you will also need to swap the infinity and zero values  
passed to dijkstra_shortest_paths.

        Doug