Core Graph

Dependency Graph

This page describes a core part of Juliagebra, the Dependency graph. This graph is responsible for making sure that the Geometry the user creates updates correctly and efficiently, whilst managing CPU/GPU resources in an optimal way.

Graph construction

The graph is set-up from the code the user writes. The nodes in the graph are the Geometry/Juliagebra defined objects that the User can use. The connections between the nodes are formed by constructing geometry with a list that contains references to other nodes. What happens when a node is updated described in the dependency callback which is written in the do-end clause.

As we can see on the picture, the red underlined objects define the nodes, the parts with blue rectangles define the connections, and their do-end clause define their dependency callback.

A very powerful invariant which comes from the construction itself, is that the resulting graph will be a DAG, meaning no cycles will be present in the graph. This is so, because when constructing, you can only pass already created nodes and Nothing types are not allowed, so Cycles can't be constructed. You can only add nodes onto this graph, not even editing is allowed.

Graph evaluation

Now that we have a constructed graph, we would like to use it, evaluate it when the User interracts with the scene.

Let's imagine the following example:

• The User moves the Point named on the graph Center2.
• We update the coordinates of Center2 to the moved position.
• Then we would like to update the graph from Center2, which becomes the source node for evaluation.
• Then the nodes which are reachable from Center2 should update themselves based their dependency callback.
• Theese updates, evaluations should only happen once for efficiency and in a logical order, where nodes that should be updated are updated before other nodes, which rely on it are evaluated.

The picture above shows the correct nodes (green) that should be evaluated from the Center2 source node. The red connections are used, and also the purple one, but crv1 isn't updated in this evaluation.

Three Invariants are defined for the graph evaluatior algorithm, which will provide a safe and efficient update strategy:

1. Total call count was correct, so the number of evaluation equals the number of reachable nodes from the source node.
2. Correct nodes called only, so evaluation was called on only on the reachable nodes from the source node.
3. Order of calls are correct, so when it is time to evaluate a node, the other nodes it depends on are the most up-to-date, meaning if they were reachable from the source node, they have already been evaluated (if they weren't reachable, they still have to be accesible for this node).

Theese invariants have dedicated tests to them.

Graph Resource management

The graph itself has a built-in efficient Resource management mechanism for nodes which have shared resources. For example all Points have a shared resource manager, which can do instanced Point rendering.

This resource management will be discussed in more detail in later pages.

Graph implementation

Everything that's described above is implemented by a few classes:

• The global graph is implemented by the DependentGraph class.
• The nodes are implemented by the Dependent class. There's also a helper class, which helps with storing graph state's for evaluation, which is called DependentChain.
• Resource managers are implemented by the Observer class.
• Nodes which have resources are implemented by the Observed class.
• The Plan and ObservedPlan classes are there to help with automated construction.