This layout is actually a copy from the layout in D3. It uses a complexity n*log n.
And apparently, the force based layout performance follows the same curve.
-=-=-=-=-=-=-=-=-=-=-=-=
values := (1 to: 1000 by: 100) collect: [ :it |
[v := RTView new.
es := RTBox elementsOn: (1 to: it).
v addAll: es.
RTForceBasedLayout on: es. ] timeToRun
].
(values collect: #asMilliseconds) plot
-=-=-=-=-=-=-=-=-=-=-=-=
Making the number of edges varying:
-=-=-=-=-=-=-=-=-=-=-=-=
values := (1 to: 299 by: 10) collect: [ :it |
[v := RTView new.
es := RTBox elementsOn: (1 to: 300).
v addAll: es.
edges := RTEdgeBuilder new
view: v;
elements: es;
connectFrom: [ :aValue | aValue // 2 ].
(edges copyFrom: it to: edges size) do: #remove.
RTForceBasedLayout on: es.
v] timeToRun ].
(values collect: #asMilliseconds) plot
-=-=-=-=-=-=-=-=-=-=-=-=
All indicates that the algo we use is n log n.
Cheers,
Alexandre
--
_,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:
Alexandre Bergel http://www.bergel.eu
^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
Can you send a screenshot?
It's hard to judge the complexity of RTForceBasedLayout since the implementation is quite complex, but I see at least one what looks like O(V^2) (RTForceBasedLayout>>accumulate: method)... and that's just for a single step.
So for 500 nodes that's 0.25M operations per step?
Google tells me that this can be as fast as O(V log(V)) so maybe this is worth looking into sometime. (And Natalia was most certainly talking about this at ESUG).
Peter
_______________________________________________
Moose-dev mailing list
Moose-dev@iam.unibe.chhttps://www.iam.unibe.ch/mailman/listinfo/moose-dev