GNOME.org
 

Re: Autolayout plug-in

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.
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. Adding a double to DiaObject
would do it and would have us get rid of the Graph struct (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)). Any possibility for that to
happen or any other solution? Sorry for the late replies I'm still
writing my thesis report.

Best Regards,

On Fri, Aug 15, 2008 at 12:54 PM, Hans Breuer <hans breuer org> wrote:

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
_______________________________________________
dia-list mailing list
dia-list gnome org
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/
[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]