[bgl] kamada_kawai_spring_layout
Just playing with the kamada_kawai_spring_layout , so far for any non trivial graph (more then 4 nodes) - it seems to just go into an infinite loop. The graph is undirected but would contain "circular" paths - thoughts? Gordon.
On Aug 17, 2004, at 9:33 AM, Gordon Smith wrote:
Just playing with the kamada_kawai_spring_layout , so far for any non trivial graph (more then 4 nodes) - it seems to just go into an infinite loop. The graph is undirected but would contain "circular" paths - thoughts?
I'm quite sure I botched the default termination condition. You could, if you are interested, try writing your own termination condition to see the behavior of the "delta" parameter and why my simple minimum-finding code doesn't work. Or you could send me one of those graphs and I can do the same. Doug
I am looking at it now, but if you want to reproduce, the following random
generated graph should cause it also:
typedef boost::minstd_rand base_generator_type;
base_generator_type generator;
generate_random_graph(m_graph, 60, 60, generator);
{
edge_iterator e, eend;
for (tie(e, eend) = edges(m_graph); e != eend; ++e)
{
edge_weight[*e] = 1;
}
}
circle_graph_layout(m_graph, vertex_pos, 10);
kamada_kawai_spring_layout(m_graph, vertex_pos, edge_weight,
boost::edge_length(65));
Gordon.
"Doug Gregor"
On Aug 17, 2004, at 9:33 AM, Gordon Smith wrote:
Just playing with the kamada_kawai_spring_layout , so far for any non trivial graph (more then 4 nodes) - it seems to just go into an infinite loop. The graph is undirected but would contain "circular" paths - thoughts?
I'm quite sure I botched the default termination condition. You could, if you are interested, try writing your own termination condition to see the behavior of the "delta" parameter and why my simple minimum-finding code doesn't work. Or you could send me one of those graphs and I can do the same.
Doug
NOTE: I also needed to change the following: vertex_descriptor old_p; To: vertex_descriptor old_p = 0;
On Aug 17, 2004, at 3:03 PM, Gordon Smith wrote:
NOTE: I also needed to change the following:
vertex_descriptor old_p;
To: vertex_descriptor old_p = 0;
I think it should be vertex_descriptor old_p = p; because "p" is the vertex that was just moved. It seems happier now, and I've checked in that fix. Maybe we'll be lucky after all :) Doug
Alas no, still looping on a reasonably normal graph, if I get a chance I
will send you the more info...
Gordon.
"Doug Gregor"
On Aug 17, 2004, at 3:03 PM, Gordon Smith wrote:
NOTE: I also needed to change the following:
vertex_descriptor old_p;
To: vertex_descriptor old_p = 0;
I think it should be
vertex_descriptor old_p = p;
because "p" is the vertex that was just moved. It seems happier now, and I've checked in that fix. Maybe we'll be lucky after all :)
Doug
On Aug 17, 2004, at 4:02 PM, Gordon Smith wrote:
Alas no, still looping on a reasonably normal graph, if I get a chance I will send you the more info...
I know what happened: the algorithm can only handle connected graphs, and the graph that's being generated is disconnected. I had to grep through the documentation page to find the (single!) place where it said that a connected graph is required. Anyway, I'm updating the documentation to be explicit about the connectedness requirement, which will be checked by the algorithm (it will return false for a disconnected graph or one with a negative weight cycle). The changes should be in shortly... Doug
I can reproduce the infinite loop with a connected graph - if I provide the
"dot" format for you will that be enough?
Gordon.
"Doug Gregor"
On Aug 17, 2004, at 4:02 PM, Gordon Smith wrote:
Alas no, still looping on a reasonably normal graph, if I get a chance I will send you the more info...
I know what happened: the algorithm can only handle connected graphs, and the graph that's being generated is disconnected. I had to grep through the documentation page to find the (single!) place where it said that a connected graph is required.
Anyway, I'm updating the documentation to be explicit about the connectedness requirement, which will be checked by the algorithm (it will return false for a disconnected graph or one with a negative weight cycle). The changes should be in shortly...
Doug
Thanks for all your timley responses btw...
Gordon.
begin 666 graph.zip
M4$L#!!0````(`"]<$C';23UD( L``. M```)````9W)A<&@N='ATG5K?;]PV
M$GZ^`OT?"#^K@3BD2 D'/\B[\JYLK933[MIU>_>0H&YB7"X)D@`]W.'^]_N&
M6DNDO$(C/11L[/DXY/SX9H;RNR]O/K\7__WQA[^\<__WZ^^?/G[[^O2?Q\LL
M$E_>?/SG;T]?+JLV$E\_?WCZ^/CU\O
On Aug 18, 2004, at 10:51 AM, Gordon Smith wrote:
Thanks for all your timley responses btw...
I've rewritten the termination check to be a whole heck of a lot smarter [*], and it seems to work nicely now for the graphs I've tried. The code is in CVS; I hope it works better for you, and thank you very much for the test cases. Doug
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.
2. If _all_ the vertices have the same location, then there is an infinite
loop (see 3).
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).
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.
Gordon.
"Doug Gregor"
On Aug 18, 2004, at 10:51 AM, Gordon Smith wrote:
Thanks for all your timley responses btw...
I've rewritten the termination check to be a whole heck of a lot smarter [*], and it seems to work nicely now for the graphs I've tried. The code is in CVS; I hope it works better for you, and thank you very much for the test cases.
Doug
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
participants (2)
-
Doug Gregor -
Gordon Smith