[Boost-users] [Graph] Two issues: Incorrect behavior with Prim's MST algorithm and Fruchterman-Reingold layout

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 #include #include #include #include <vector> #include using namespace boost; using namespace std; int main(int argc, char** argv) { typedef adjacency_list < vecS, vecS, undirectedS, property, property < edge_weight_t, double > > graph; graph g(3); property_map::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 )