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