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

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

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.


 * Attraction is calculated only between the current and it's
  directly connected nodes.


 * 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

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

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)


 * the first file to include in every .c file is config.h


 * prototypes only used in a single file should be declared locally
  and static


 * a function name in the implementation should start at the beginning
  of a line, the return value is on it's own line


 * 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 ;)


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

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