Re: Autolayout plug-in

Sorry for the very late reply, I have been finalizing my thesis and
moving back to my country. I would like to restart the discussion
about automatic layout, gearing things towards inclusion into Dia as
an offered feature.

You would prefer it as a plugin (I presume)?
If it is a plugin, where should the GUI code go (if any)?
Any requirements for the GUI (following a certain HIG)?
How can I generate the API docs for plugins? --with-hardbooks didn't work.
Any requirements about memory usage and processing? Or which one
should be prefered over the other?

Best Regards,

On Fri, Aug 29, 2008 at 1:59 PM, Hans Breuer <hans breuer org> wrote:
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
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

(but will increase the computational complexity of the algorithm,
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 "at" Breuer "dot" Org -----------
Tell me what you need, and I'll tell you how to
get along without it.                -- Dilbert
dia-list mailing list
dia-list gnome org
FAQ at
Main page at

Fred Morcos

[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]