2008/8/9 Hans Breuer <[EMAIL PROTECTED]>:
> Am 05.08.2008 21:22, Fred Morcos schrieb:
>>
>> Patch attached. Taken off revision 4102 from Dia's root dir using svn
>> diff.
>>
> Thanks for the patch. I have played with it a bit but am still not able to
> completely wrap my head around it. Here is what I think I have understood:
>
> * Repulsion is calculated as a force between the current node and
> every other node - be it connected or not.
Yep.
> * Attraction is calculated only between the current and it's
> directly connected nodes.
Yep.
> * The calcualtion is done for every node in the graph and
> applied instantly. During one loop the only state accumulated is
> the overall graph energy.
Yep, I moved the netforce as a variable in the layout_force function
instead of being for every node.
> * The above is repeated until a maximum number of iterations is reached
> or the energy falls below a certain value.
Yep, at first I had only the energy part to terminate the algorithm
but while testing, with some combinations of graphs + distance/spacing
values the energy keeps oscillating between some values which turned
into an infinite loop. This should have improved by now (after some
changes) but I still kept the iterations limit just in case (put it
from 1000 to 10000).
> * There is no state outside of the diagram (here: the modified object
> positions) shared between different iterations
>
Could you come again please?
> The graph is constructed from the diagram('s selection) by translating (only
> connected) connection objects to edges and the other objects to nodes.
> The only additional parameters taken from the diagram are 'mass of node'
> (currently defined as Object::bounding_box area), their position and the
> distance between the nodes (currently defined as the distance between the
> Object::position).
Yep, so larger "objects" can push other objects around them further
and avoid overlapping.
>
> If the above summary is right the intermediate 'Graph' allocation is only
> needed for convenience and as a cache to avoid the recalculation of node
> masses.
Well not really. Everytime the function is called this 'Graph' is
reconstructed. We can have the Graph data structure static in the
function, and from app/autolayout-force.c we either pass an argument
(to have the function re-create the graph from the diagram or just use
the cached one).
> To verify my assumptions I have reimplemented the functionality as a PyDia
> plug-in, and indeed it gave the same result for everthing I have tested.
> I hope it is useful to illustrate the remaining open questions regarding
> Handle, ConnectionPoint an Object relation better than my previous attempts
> ;-)
>
I don't know Python and I couldn't really run the script...
>
> Your current patch adds the algorithm to lib/ and its dialog to app/. My gut
> feeling is both should be added together into a new plug-in/autolayout. The
> necessary glue code is attached. I only have integrated it with the
> win32/msvc build yet.
>
If you want it in Python you'll have to give me some time...
>
> There are also some formal aspects with your patch which need to be
> addressed before it is ready for inclusion with Dia.
>
> * please use tab-width 8 (apparently you used 4)
Done.
> * the first file to include in every .c file is config.h
Done.
> * prototypes only used in a single file should be declared locally
> and static
Done.
> * a function name in the implementation should start at the beginning
> of a line, the return value is on it's own line
Done.
> * every user-visble string needs to be marked for translation,
> e.g. _(""Spacing:"")
You meant _("Spacing:") right?
> * some variable naming looked strange to me, e.g. 'Graph diagram;'
> IMHO this make the code unnecessary harder to understand.
>
Did what I could here...
>
> The undo thing and other things I've forgotten is left for another mail. I
> think this one is already long enough ;)
>
> Regards,
> Hans
>
Well, I'll be really busy for the next 20 days with writing my thesis
report. I'm implementing another algorithm for force based layouting
(should be much faster and much more scalable)...
--
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
