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

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 )