Re: Autolayout plug-in

[Hans Breuer <hans breuer org>]

At 13.08.2008 19:21, Fred Morcos wrote:
> 2008/8/9 Hans Breuer <hans breuer org>:
[...]
> > 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:
[...]
> >  * There is no state outside of the diagram (here: the modified object
> >   positions) shared between different iterations
>
> Could you come again please?
What I was trying to say was: the only information which must be stored 
between to iterations is the object position. It is stored in the diagram 
itself by modifiying the object directly. Evrything else can be 
recalculated from the objects in every iteration.

> > 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.
Here I have some problem with the current algorithms behaviour. A weakly 
connected bug object (say having only one connection to the other objects) 
gets pushed (too) far away from the rest of the more connected objects.
Would it be feasible to compensate for this behaviour by making the 
repulsion also dependent on the objects distance, i.e. reduce the repulsion 
the further away an object is?

> > 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).
The point I was trying to make is: there is no need to have the Graph 
allocated at all. It only may speed up the algorithm by caching. Of course 
- as you say - the caching effect could be improved by avoiding the 
construction of the Graph for every iteration.
But if one decides to concentrate on the algorithm and live with some 
recalculations (only object masses) the whole Graph object can be avoided.

> > 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...
You need to './configure --with-python' and run Dia with app/run_dia.sh. 
Than there should be the menu entry '<Diagram>/Test/Layout (force)'

> > 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...
Translating to Python is not necessary for inclusion. Plug-ins can be 
written in C as well. In fact I first build your code with only small 
modifications as a plug-in in C and afterwards translated it to Python 
because I wanted to test my assumptions, e.g. how much state needs to be 
cached.
The current implementation has the following changes to your implmentation:
 - there is no Graph to cache state, just the plain list of objects (nodes)
   is constructed before the iterations, see: layout_force_cb()
 - the object edges an their connections to other objects are queried
   in the every iterations inner loop. See layout_force() :

    for cpt in o.connections : # connection points
      for co in cpt.connected : # connected objects in this point
        edge = co
        oo = None
        for h in edge.handles : # the edge handles are connected to ...
          cto = h.connected_to # ... the other objects connection point
            if  cto and cto.object != o : # ... one of it being the current

[...]
> >  * every user-visble string needs to be marked for translation,
> >   e.g. _(""Spacing:"")
>
> You meant _("Spacing:") right?
Yep.

> >  * 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...
Thanks for all your work. An update patch would be nice, I could than do 
the suggested translation to a plug-in and commit it to SVN. In case the 
plug-in is not ready for prime time when the next release finally comes, it 
would be simple to just not install it for users.

> > The undo thing and other things I've forgotten is left for another mail. I
> > think this one is already long enough ;)
> >
BTW: here is my type agnostic reimplementation of your classification function:

/* check if an object can be an edge (connection) and return so */
GraphObjectType graph_type_from_object(DiaObject *object)
{
  guint i, nhc = 0;

  for (i = 0; i < object->num_handles; ++i) {
    if (object->handles[i]->connect_type == HANDLE_CONNECTABLE) {
      ++nhc;
      if (nhc > 1)
        return GRAPH_OBJECT_TYPE_EDGE;
    }
  }
  /* maybe we need a third type: not intersting for */
  return GRAPH_OBJECT_TYPE_NODE;
}

> 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)...
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