6.3.3 Geometric dependencies and topological sorting

As mentioned before, every graphic object has several anchors which serve as “geometric input” and hangers which are “geometric output” devices. Every anchor is connected to exactly one hanger, while a hanger can hold arbitrarily many anchors. This creates a dependency structure of geometric objects within a page (no anchor can hang on a hanger from a different page).

In the following image you can see a dependency diagram with two graphic objects. The half-circles represent anchors and hangers: the black half-circles pointing up are anchors, the ones pointing down are hangers and the white half-circles are mouse-clicks.

When any geometric property of a graphic object is changed or when an anchor of the object is rehung on some other hanger, the object must be recomputed. But all the dependent objects – objects whose anchors hang on the object's hangers – must be recomputed as well. The recomputation must be done in the right order; we use the topological order which assures that every object is dependent on the previous objects only.

We will not describe the topological sorting algorithm, as it is well known; we only describe how the algorithm is used in the VRR kernel.

Every page contains a special data structure for the topological sort: a list of graphic objects tsort_list and a bitmask for flags. The flags have the following meaning:

• OF_TSORT_ACTIVE means that the tsort_list is nonempty
• OF_TSORT_PRESORT means that the objects in the list are in topological order
• OF_TSORT_DIRTY means that the objects in the list have been modified, but not yet recomputed

The topological sorting algorithm is used for these activities as well:

• Rehang anchors with acyclicity checks. If the user tries to rehang an anchor, it must be checked that he resulting dependency graph is acyclic. For those purposes, the owner GO of the anchor is put in the sorted list with all its dependent objects and the anchor must not be rehung on any hanger whose GO is contained in the list.
• Manage transformation of given GOs. When performing many transformations with a certain fixed set of GOs, it is quite useful to use the same sorted list without having to rerun the sorting algorithm.

All the other editing actions must be done when the topological sorting is not active, because they could change the dependency structure (by adding new dependent GOs or removing some, for example) and make the sorted list invalid.