|
Boost Users : |
Subject: [Boost-users] [Graph] Two issues: Incorrect behavior with Prim's MST algorithm and Fruchterman-Reingold layout
From: David Gleich (dgleich_at_[hidden])
Date: 2008-10-07 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 self-loops.
First issue:
I found an problem with Prim's minimum spanning tree algorithm and graphs with
self-loops. I looked through the documentation for the function and didn't
see any notes about self-loops (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 self-loop 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 self-loops. When
used with the combine function for Prim's algorithm, it'll always pick out
these self-loops.
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 self-loops 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 self-loops.
This issue has a rather simple fix.
--- lib/boost_trunk/boost/graph/fruchterman_reingold.hpp
+++ matlab-bgl/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; // self-loops 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 )
Boost-users 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