Re: [Boost-users] Re: Re: Re: Re: Re: [bgl] kamada_kawai_spring_layout

From: Doug Gregor (dgregor_at_[hidden])
Date: 2004-08-20 10:40:37

On Aug 20, 2004, at 9:22 AM, Gordon Smith wrote:

> Great thanks, this is working a lot better now...
>
> Comments (really just some boundary cases):
> 1.  If two vertices have the same location before the layout is 
> called, they
> will have the same location after the layout is finished.

Interesting. This case should probably be detected and the positions 
perturbed slightly.

> 2.  If _all_ the vertices have the same location, then there is an 
> infinite
> loop (see 3).

I'm not entirely surprised... the above change could fix this.

> 3.  I know you recommend calling circle_layout before calling the 
> spring
> layout, but since this layout algorithm is very dependant on starting
> positions I think you will find this won't produce great results...  
> In fact
> calling the spring algo several times in succession shows it gets 
> "better"
> (in my project I animate the movement after each iteration), I will be
> playing with the "Done" rules over the next couple of days and will 
> report
> back findings (if any are of interest).

The circular layout suggestion comes from Kamada & Kawai. If the 
layouts aren't all that great, it's probably the fault of the "Done" 
function object. Perhaps we need an absolute tolerance, or a tighter 
relative tolerance, or even an iteration count... it's hard to know 
what works well without a bit of testing.

> Again thanks for your work - I am comparing this spring layout against 
> my
> spring layout and also against "neato" (which I can't animate) from the
> graphviz project.

Cool. I'd be interested to hear about the results.

        Doug