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