Re: Autolayout plug-in

[Hans Breuer <hans breuer org>]

At 26.08.2008 21:44, Fred Morcos wrote:
> I worked on a suggestion by Andrew Boktor where the force on each pair
> of nodes (repulsion and attraction) is calculated only once instead of
> twice. Adding the force to one node and subtracting it from the other.
Sorry, I'm not sure if I can follow. If I understood (and implemented) the 
algorithm correctly the position of the "current node" changes directly 
after it's calculation. So the only thing which is not position dependent - 
and can be cached - seems to be the nodes mass.

> The problem now is that there is no cur_node so I can't store the new
> netforce resulting from attraction due to the fact that I can't access
> the Node structs from the Edge struct and trying to add Nodes to Edges
> will result in duplicate structs being allocated and the position of
> the nodes not being updated correctly. 
One way would be to just store the references (pointers) to the original 
objects and deduce the rest during iteration. This is what I have done with 
my Python plug-in. There is no egde storing at all, they are just looked up 
while iterating over the nodes.

> Adding a double to DiaObject would do it 
I don't think this is feasible, the dia core should know nothing about the 
special algorithms needed for autolayout.
> and would have us get rid of the Graph struct
I don't have the graph struct in my implementation, just a plain list of 
objects (nodes) to process. If performance is really an issue one could 
extend this list with precalculated values. But the first thing should be 
to identify the bottlenecks.
If one of the bottleneck is the lookup of nodes edges it should be 
benefitial to have a list of node objects, where every node has it's own 
list of edges i.e. a pointer to its connected nodes (best pointing into the 
node list again.
To avoid multiple calculations of masses a node object could store them.
To avoid duplicate calculations of repulsion and attraction I think the 
objects movement needs to be moved out of the inner loop. For this every 
Node object would need to store it's original position as well as its 
target position.
This node list should be hold outside of layout_force(). After each 
iteration the target positions would be made the current positions. Things 
like edges (connected nodes) and masses would not be recalculated for every 
iteration.

> (but will increase the computational complexity of the algorithm, basically
> would be O((n + e)^2) instead of O(n^2) where n is the number of nodes
> and e the number of edges (connections)). 
Did you profile your current implementation to be sure you are optimizing 
the right thing?

> Any possibility for that to happen or any other solution? 
Regarding the storing of "user data" with the DiaObject my current answer 
is no. I'm pretty sure there will be an appropriate data structure on the 
client side. I'm still uncertain if it is needed at all; again only some 
profiling will show ;-)

> Sorry for the late replies I'm still writing my thesis report.
Have fun,
        Hans

-------- Hans "at" Breuer "dot" Org -----------
Tell me what you need, and I'll tell you how to
get along without it.                -- Dilbert