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 <[EMAIL PROTECTED]> wrote:
> At 13.08.2008 19:21, Fred Morcos wrote:
>>
>> 2008/8/9 Hans Breuer <[EMAIL PROTECTED]>:
>
> [...]
>>>
>>> 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
> [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
>
>
--
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
