Re: Autolayout plug-in (was: Re: Dia Automatic Layouting)

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

2008/8/9 Hans Breuer <hans breuer org>:
> 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/