Re: Autolayout plug-in

["Fred Morcos" <fred morcos gmail com>]

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
> 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
> _______________________________________________
> dia-list mailing list
> dia-list gnome org
> http://mail.gnome.org/mailman/listinfo/dia-list
> FAQ at http://live.gnome.org/Dia/Faq
> Main page at http://live.gnome.org/Dia



-- 
Fred Morcos
http://fredmorcos.blogspot.com/
http://fredmorcos.googlecode.com/