Re: [Boost-users] BGL Fruchterman Reingold Layout

From: Doug Gregor (dgregor_at_[hidden])
Date: 2004-12-16 13:37:02

On Dec 16, 2004, at 11:05 AM, Gordon Smith wrote:

> I searched the net, but couldn't see any real world examples of what 
> the
> Fruchterman Reingold Layout should look like.  Having played with it, 
> it
> seems the vertices gravitate towards the bounding rectangle and a 
> horizontal
> / Vertical cross about one fifth into the rectangle.  Is this expected
> (which is not very impressive)?

It wasn't expected, but I believe I understand what's happening. The 
display area gets divided into a grid. There is an attractive force 
between all vertex pairs that have an edge between them and a repulsive 
force between all vertex pairs within a single grid cell. So, I think 
what's happening is that two vertices (u and v) have an edge between 
them (pulling them together) and are in the same grid cell, but they 
get pulled to one of these grid divisions where u ends up on one side 
of the grid boundary and v ends up on the other side of the boundary.

One simple question, though: how are you initializing the vertex 
positions? Randomly? Have you tried changing the random seed to see if 
this is an isolated instance?

If it isn't an isolated case, you may want to try changing the 
"force_pairs" argument to the Fruchterman-Reingold algorithm. It's 
currently using the "grid pairs" version, but there is an all-pairs 
version (bad for disconnected graphs) and you could probably write one 
that is distance-based, e.g., u and v repulse if they are within some 
distance threshold of each other. That variant will be as slow as 
all-pairs, but will work on disconnected graphs and should not have 
this behavior.

> I have attached two small images one of a regular spring layout and 
> one of
> the Fruchterman Reingold Layout (note the data is just random).

Cool!

        Doug