[Boost-users] fruchterman_reingold doesn't like small graphs

From: Jamie Wilkinson (jaq_at_[hidden])
Date: 2005-01-13 08:08:14

I'm writing an app in which the user incrementally adds vertices to the
graph; of course it starts empty, and after each addition the graph is laid
out with the fruchterman-reingold function.

The algorithm copes well with empty graphs, but once I add a single vertex,
the program crashes: the crash is always in the same place, deep in
std::list but called from boost/graph/fruchterman_reingold.hpp:116 :

     buckets[row * columns + column].push_back(*v);

The push_back function calls end() to get the last element of the list, and
fails.  A bit of gdb turned up the following result: columns and rows were
both being set to 0 and so buckets was also of size 0.  Lines 111:112 also
end up setting column and row to 0, and then the next pair of lines were
setting them to, on my machine, 4G.

The element of buckets being accessed, then, was ridiculously out of bounds.

The value width/two_k, once cast to the integral size_t, was always zero.  I
don't think this is restricted to having a single vertex in the graph, but
that case seems to exacerbate the bug.

So as a workaround, I've added the following two lines to make sure that the
variables columns and rows are at least 1:

Index: boost/graph/fruchterman_reingold.hpp
===================================================================
RCS file: /cvsroot/boost/boost/boost/graph/fruchterman_reingold.hpp,v
retrieving revision 1.5
diff -u -r1.5 fruchterman_reingold.hpp
--- boost/graph/fruchterman_reingold.hpp        29 Dec 2004 16:53:05 -0000     1.5
+++ boost/graph/fruchterman_reingold.hpp        13 Jan 2005 13:09:00 -0000
@@ -105,6 +105,8 @@

     std::size_t columns = std::size_t(width / two_k);
     std::size_t rows = std::size_t(height / two_k);
+    if (columns == 0) columns = 1;
+    if (rows == 0) rows = 1;
     buckets_t buckets(rows * columns);
     vertex_iterator v, v_end;
     for (tie(v, v_end) = vertices(g); v != v_end; ++v) {

If you wish to reproduce this bug, you can do so with the example program
libs/graph/example/fr_layout.cpp :

  g++ -Iboost boost/libs/graph/example/fr_layout.cpp
  echo "A B" | ./a.out 100 100

My results without the patched function:

willow% echo "A B" | ./a.out 100 100 
0%   10   20   30   40   50   60   70   80   90   100%
|----|----|----|----|----|----|----|----|----|----|
*zsh: done                echo "A B" |
zsh: segmentation fault  ./a.out 100 100

and patched:

willow% echo "A B" | ./a.out 100 100

0%   10   20   30   40   50   60   70   80   90   100%
|----|----|----|----|----|----|----|----|----|----|
***************************************************
A       -41.0322        -29.471
B       1.16969 27.1354