Changed Document Linking: Bidirectional Graph Structure

[ickby]

Hello,

Jriegel started around 2014 to make some changes in the document linking system in his assembly branch. I now ported those changes to master as I think they are really beneficial for the upcoming assembly document structure.

What is different
Currently FreeCAD links document objects together by properties only, hence this is a one-directional linking. This allows to traveres the resulting object graph only in one direction, from top to bottom. Often the other direction is needed (for example for recompute), there a boost::graph is created and used. The branch changes that, it introduces a datastructure, called backlinks, in each object where it stores all objects which link to it. This makes the one-directional linking a bidirectional one. Hence the graph can be traversed in both directions, top-down as well as bottom-up. All link properties ensure that the backlinks are keept up to date. This then allows to simplyfy quite many functions like recompute or getting the objects inList.

Why is this usefull
1. In the future it will often be needed to check to which group a object belongs: this becomes way easier, as one can go the graph upwards
2. To compute global position in a stack of local coordinate systems one need to traverse the graph upwards
3. To get all dependend objects ne need to traverse the graph upwards
Those operations, all of which will become heavily used with an assembly workbench, get way faster with the new structure. Hence it is very usefull IMHO.

What could go wrong
Recomputing is a core functionality of freecad, and lots of optimisation and error fixing was done. I'm not sure if I'm able to get the same amount of stability with the new implementation.

I currently leave the branch as is, without a pull request, as I think those changes should be discussed.
https://github.com/ickby/FreeCAD_sf_master/tree/DAG
(Note that I introduced the preprocessor-switch USE_OLD_DAG which should make it simple to compare old/new implementation.)

[yorik]

Document objects already have an InList and OutList, which if I remember correctly, get populated/recalculated everytime something changes, that seems to do pretty much what you are explaining... Is this implementation different?

[wmayer]

Document objects already have an InList and OutList, which if I remember correctly, get populated/recalculated everytime something changes, that seems to do pretty much what you are explaining... Is this implementation different?

No, that's not correct because the information is re-computed each time you call the functions.

The getOutList method goes through all property link types of an object and returns an array of all stored links. This method is quite fast, actually.
The getInList method however is quite inefficient because it goes through all objects of the document to get their out-lists and then checks if the given object object is part of it.

[ickby]

Document objects already have an InList and OutList, which if I remember correctly, get populated/recalculated everytime something changes, that seems to do pretty much what you are explaining... Is this implementation different?

As werner already pointed out, currently the inList is rebuild everytime one queries it. This gets highly uneficient for larger documents, especially as we are going to use this way more often in the future. Hence the proposed change does ensure the inList is rebuild everytime a link changes.

[wmayer]

I have looked through the source code and there are a few things that must be changed:
* in FCConfig.h there is the define "#define USE_OLD_DAG 0". The drawback of having this switch there is that whenever changing it you have to rebuild FreeCAD completely which increases compile time a lot. It would be much better to add this define to the App/CMakeLists.txt file.

* to reduce the compile further only use the define inside the .cpp files. For Document.h/DocumentObject.h just define the methods independent of USE_OLD_DAG.

* the check for USE_OLD_DAG is done inconsistently. Sometimes it's checked if the define is set, sometimes it's checked whether it's 0.

* the method _maintainBackLink is defined but used nowhere. It can be removed.

* inside PropertyLink::setValue(App::DocumentObject * lValue) it is checked if the current link value is the same as the passed value. If yes it returns straight away. This behaviour might be troublesome because it may block the notification chain and thus e.g. may affect the undo/redo mechanism. Btw, for no other property type it's checked if old and new value are the same. The assignment is just performed.

[yorik]

thanks for the explanations! Indeed the change makes perfect sense.

[ickby]

I introduced the changes proposed by werner and made a pull request:
https://github.com/FreeCAD/FreeCAD/pull/455

I think it is useful to have the possibility to switch to the old DAG for debuging purposes, we can remove the old code some time in the future, if the new code has been proven robust.

[realthunder]

I am not sure if this is the right place to bring up this issue. I just stumble upon this thread, which I think is kind of relevant.

In FC, a document object can be linked to many other objects, hence the InList. But in treeview, an object can only appear in one place. So, when adding or deleting new objects, their children will just magically disappear, re-appear, and out of order (e.g. Cut object with reversed Base and Tool). With this new graph structure, will it be easier to just show an object in all of its parents child branch?

[DeepSOIC]

I am not sure if this is the right place to bring up this issue. I just stumble upon this thread, which I think is kind of relevant. In FC, a document object can be linked to many other objects, hence the InList. But in treeview, an object can only appear in one place. So, when adding or deleting new objects, their children will just magically disappear, re-appear, and out of order (e.g. Cut object with reversed Base and Tool). With this new graph structure, will it be easier to just show an object in all of its parents child branch?

This post spawned a discussion that I moved to another thread, called it "Model Tree widget instability". https://forum.freecadweb.org/viewtopic.php?f=34&t=20197

[ickby]

Currently the new DAG structure is disabled. @werner Is there any reason for this, any instability or error? If so I could further improve it.

In my updates to the group structure i use the inlists rather extensively and having this optimisation would be nice.