The Graph

ng::Graph (graph.h, src/graph.cc) is the central structure. It is a plain value type: it can be copied, compared (ng::CmpGraph) and serialized. It doesn’t know the disk, except through add_proxy_node which asks the GraphManager (see Proxies: graphs inside graphs).

Storage

Graph
├── name_            std::string
├── qualifier_       std::optional<qualifier_t>     required to save the graph
├── nodes_           map<node_id_t, Node>           a Node only knows the IDs of its sockets
├── input_sockets_   map<socket_uuid_t, InputSocket>
├── output_sockets_  map<socket_uuid_t, OutputSocket>
├── links_           set<link_t>                    (to, from), sorted by destination
├── parameters_      map<socket_uuid_t, InterfaceProperties>   inputs exposed to the outside
└── results_         map<socket_uuid_t, InterfaceProperties>   outputs exposed to the outside

InterfaceProperties is {show_as, socket_id}: the name and ID the socket gets on a proxy node.

The sockets are copies of the sockets of the NodeDefinition taken when the node was added. After that, the graph never looks at the definition again (see Known limitations).

Nodes

add_node(qualifier)

Looks the type up in the NodesRegistry (returns null_node if unknown), generates an unused node ID, copies every socket of the definition into the graph under (node_id, socket_id), and creates the Node with the default name of the definition. add_node("a.b.c") parses the string first and throws if it’s not a valid qualifier.

remove_node(id)

Breaks all its links (reason NodeRemoved, callbacks triggered), removes its sockets from the parameters and results, erases its sockets (a single range thanks to the UUID ordering), then the node.

disconnect_node(id, reason = Manual)

Breaks all the links going to or coming from the node. The links are collected first, so the callbacks can safely modify the graph.

rename_node, get_node, has_node

get_node and rename_node throw std::out_of_range if the node doesn’t exist.

Links

add_link(from, to) checks, in this order, and stops at the first failure:

#	Check	Result
1	The link already exists	Ok, nothing happens (no callback)
2	from is an existing output socket	NoOutputSocket
3	to is an existing input socket	NoInputSocket
4	The type masks intersect	IncompatibleTypes
5	The input is linkable	NotLinkable
6	Adding the link doesn’t create a cycle (a self link is a cycle)	CausesCycle

Then it:

1. breaks the link currently targeting to, if any (reason Replaced, callbacks triggered);

2. removes to from the parameters, if it was exposed (a socket gets its value from a link or from the outside, never both);

3. inserts the link;

4. triggers the “link added” callbacks of the output socket, then of the input socket.

The cycle check is done before replacing the existing link, so a refused link leaves the graph exactly as it was. Keeping the old link in the check can’t produce a false positive: a simple cycle enters each socket only once, so it can’t use both links targeting to.

break_link(link) returns false if the link doesn’t exist. Otherwise it erases the link, then triggers the “link broken” callbacks of the output socket then of the input socket (reason Manual).

find_link_by_input_socket(input) and is_linked(input) are O(log n) thanks to the (to, from) order. get_input_links(node) and get_output_links(node) scan all the links (O(n)).

Socket values

set_socket_value(suuid, value) checks that the input exists (NoInputSocket), that the value is allowed (NotAllowedValue) and valid (InvalidValue), sets it and triggers the “value changed” callbacks with the old value. See Socket values, enumerations, validators for the rules. Setting the value of a linked socket is allowed: the value is kept but ignored at runtime, the link wins.

Interface: parameters and results

The interface is what a graph shows when it is used as a node of another graph (see Proxies: graphs inside graphs).

expose_parameter(input, alias, show_as = "")

• NoInputSocket if input isn’t an input socket;

• DuplicateAlias if another parameter already uses alias;

• show_as defaults to the name of the socket;

• any link targeting the input is broken (reason Replaced);

• exposing an already exposed socket again updates its alias and name.

expose_result(output, alias, show_as = "")

Same rules for outputs, except that no link is broken: an output can feed other nodes and be a result at the same time.

Parameters and results have separate alias spaces: a parameter and a result can share an alias.

Topology

get_depth_properties(links = links_) returns, for each node, its depth: the length of the longest path from a node without input links. It also gives max_depth and has_cycle.

The algorithm is Kahn’s topological sort:

1. count the incoming links of each node (in_degree);

2. push the nodes with in_degree == 0 with depth 0;

3. pop a node, and for each successor: depth = max(depth, current + 1), decrement its in-degree, push it when it reaches 0;

4. if fewer nodes were processed than there are nodes, there is a cycle. The nodes in (or downstream of) a cycle have no depth.

Using the longest path guarantees that a node is always deeper than all its predecessors, which is what the runtime needs to execute them in order. It costs O(nodes + links).

causes_cycle(link) copies the links, adds the new one and runs the algorithm: every add_link is O(nodes + links), fine for interactive graphs of a few hundreds of nodes.

get_source_nodes(links = links_) returns the nodes that are not the destination of any link.

The overloads taking a set of links analyse a hypothetical state without modifying the graph.

Callbacks

Event	Triggered by	Order
Link added	add_link	output socket, then input socket
Link broken	break_link (Manual), add_link replacing (Replaced), expose_parameter (Replaced), disconnect_node (given reason), remove_node (NodeRemoved)	output socket, then input socket, after the link is erased
Value changed	set_socket_value, only if the value is accepted	input socket

Callbacks receive the Graph& and may modify it. Callbacks attached to a socket but not registered are ignored.

Deep comparison

ng::CmpGraph().equal(a, b) compares everything by value: name, qualifier, links, every node, every socket (including values, allowed values and callbacks) and the interface. It is used by the tests and to check that a reloaded graph is identical to the saved one.