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