
Boost Users : 
Subject: [Boostusers] [Graph] Two issues: Incorrect behavior with Prim's MST algorithm and FruchtermanReingold layout
From: David Gleich (dgleich_at_[hidden])
Date: 20081007 20:50:11
Hi,
There are two issues in this note. Sorry for bundling them, but they both
deal with incorrect behavior when the graph has selfloops.
First issue:
I found an problem with Prim's minimum spanning tree algorithm and graphs with
selfloops. I looked through the documentation for the function and didn't
see any notes about selfloops (which can cause the problem).
The program at the end of this message doesn't produce a complete spanning
tree on a connected graph, but it should.
This issue shows up with any graph where a vertex has a selfloop with a lower
weight than any of the other edges from that vertex.
The cause of the issue is the relax function used in Dijkstra's algorithm.
When computing a spanning tree, it shouldn't compare on selfloops. When
used with the combine function for Prim's algorithm, it'll always pick out
these selfloops.
I'd love to see this issue fixed so I don't have to special case calls to
Prim's algorithm to make sure all selfloops aren't there. The only way
I see to do it is to make a special version of the Dijkstra code for Prim's
algorithm. (It feels like the ramifications of changing relax.hpp could
be considerably greater.)
One possibility for a better fix is make a new version of Dijkstra's algorithm
where the relax function is a template parameter. Prim's algorithm can then
replace the entire relax behavior to get the behavior it needs.
Second issue:
The fruchterman_reingold_force_directed_layout function will always divide by
0 when computing the layout of a graph with selfloops.
This issue has a rather simple fix.
 lib/boost_trunk/boost/graph/fruchterman_reingold.hpp
+++ matlabbgl/work/libmbgl/yasmic/boost_mod/fruchterman_reingold.hpp
@@ 284,6 +284,9 @@
for (tie(e, e_end) = edges(g); e != e_end; ++e) {
vertex_descriptor v = source(*e, g);
vertex_descriptor u = target(*e, g);
+ if (v == u) {
+ continue; // selfloops should have no effect on the layout
+ }
Dim delta_x = position[v].x  position[u].x;
Dim delta_y = position[v].y  position[u].y;
Dim dist = sqrt(delta_x * delta_x + delta_y * delta_y);
Please let me know if there are any questions about these issues.
Thanks,
David Gleich
/* tested with g++ 4.2 and boost 1.36.0 */
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/property_map.hpp>
#include <vector>
#include <boost/graph/prim_minimum_spanning_tree.hpp>
using namespace boost;
using namespace std;
int main(int argc, char** argv) {
typedef adjacency_list
< vecS, vecS, undirectedS,
property<vertex_distance_t, int>, property < edge_weight_t, double >
> graph;
graph g(3);
property_map<graph, edge_weight_t>::type weightmap = get(edge_weight, g);
graph_traits<graph>::edge_descriptor e; bool inserted;
tie(e,inserted) = add_edge(0,1,g); weightmap[e]=1; cout << inserted << endl;
tie(e,inserted) = add_edge(0,2,g); weightmap[e]=1; cout << inserted << endl;
tie(e,inserted) = add_edge(1,2,g); weightmap[e]=1; cout << inserted << endl;
tie(e,inserted) = add_edge(2,2,g); weightmap[e]=0.1;
cout << inserted << endl;
std::vector < graph_traits < graph >::vertex_descriptor >
p(num_vertices(g));
prim_minimum_spanning_tree(g, &p[0]);
for (size_t i=0; i != p.size(); i++) {
std::cout << "mst parent[" << i << "] = " << p[i] << std::endl;
}
return 0;
}
Output:
1
1
1
1
mst parent[0] = 0
mst parent[1] = 0
mst parent[2] = 2
Desired output:
mst parent[2] = 0 ( or mst parent[2] = 1 )
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net