Graph algorithms

Algorithms that operate on a graph: traversal, paths, subgraphs and the like. See the graph algorithms guide.

nodeeditor.node_graph ¶

Graph algorithms over a NodeEditor :class:~nodeeditor.node_scene.Scene.

The data-flow graph of a Scene is directed: an :class:~nodeeditor.node_edge.Edge runs from the Node owning its start (output) :class:~nodeeditor.node_socket.Socket to the Node owning its end (input) Socket. An Edge whose endpoints do not form such a pair is ignored, as is an Edge that is not attached to a Socket at all.

Every algorithm here is implemented natively, so no third-party graph library is required. All traversals are iterative and keep a visited set, which means

a graph containing a cycle terminates instead of exhausting the interpreter's recursion limit, and
a node reachable through several distinct paths is visited once rather than once per path.

The graph is derived from the Scene on every call, so it always reflects the current connections. Nothing is cached and nothing has to be invalidated.

Edges internal to a collapsed :class:~nodeeditor.node_group.Group are hidden on screen but still carry data, so they still count here. Groups are visual containers and never change the shape of the graph.

GraphCycleError ¶

Bases: Exception

Raised when a graph that has to be acyclic contains a cycle.

:Instance Attributes:

- **cycles** - the cycles found, each a list of
  :class:`~nodeeditor.node_edge.Edge` in traversal order

descendants ¶

descendants(scene, node)

Every Node reachable downstream of node, excluding node itself.

The result is ordered breadth-first, so the nearest nodes come first. A node reachable through several paths appears once.

:param scene: the :class:~nodeeditor.node_scene.Scene to walk :param node: the Node to start from :return: the downstream Nodes :rtype: list of :class:~nodeeditor.node_node.Node

ancestors ¶

ancestors(scene, node)

Every Node feeding node, excluding node itself.

The result is ordered breadth-first, so the nearest nodes come first. A node feeding through several paths appears once.

:param scene: the :class:~nodeeditor.node_scene.Scene to walk :param node: the Node to start from :return: the upstream Nodes :rtype: list of :class:~nodeeditor.node_node.Node

components ¶

components(scene)

The disconnected subgraphs of scene, the "flocks" of nodes.

Two Nodes belong to the same component when a chain of Edges connects them, regardless of direction. A Node without any connection forms a component of its own.

The components come in scene order, and the Nodes inside a component come in scene order too, so the result is stable for a given graph.

:param scene: the :class:~nodeeditor.node_scene.Scene to inspect :return: one list of Nodes per component :rtype: list of list of :class:~nodeeditor.node_node.Node

topological_order ¶

topological_order(scene)

The Nodes of scene in dependency order.

Every Node comes after the Nodes feeding it, so a Node can be evaluated once every input it needs has been evaluated. Nodes that do not depend on each other keep their scene order, which makes the result reproducible for a given graph.

:param scene: the :class:~nodeeditor.node_scene.Scene to order :return: the Nodes in dependency order :rtype: list of :class:~nodeeditor.node_node.Node :raises :class:GraphCycleError if the graph contains a cycle

cycles ¶

cycles(scene)

The cycles of scene.

One representative cycle is returned per cyclic region, so a graph with two separate loops yields two cycles. Within a cycle, the Edges are listed in traversal order and the last one leads back to the node the first one started from.

:param scene: the :class:~nodeeditor.node_scene.Scene to inspect :return: the cycles, each a list of :class:~nodeeditor.node_edge.Edge :rtype: list of list of :class:~nodeeditor.node_edge.Edge

paths ¶

paths(scene, source, target)

Every simple path from source to target.

A path is a list of (node, edge) steps. The edge of a step is the Edge that led into its Node; the first step carries None because nothing leads into the first node. Two Edges between the same pair of Nodes yield two different paths, because each Edge is its own thing.

:param scene: the :class:~nodeeditor.node_scene.Scene to search :param source: the Node to start from :param target: the Node to reach :return: the paths found :rtype: list of list of (Node, Edge)

shortest_path ¶

shortest_path(scene, source, target)

The shortest path from source to target, counted in Edges.

The path is a list of (node, edge) steps, the same shape :func:paths returns. When several shortest paths exist, the one found first is returned, which makes the result reproducible.

:param scene: the :class:~nodeeditor.node_scene.Scene to search :param source: the Node to start from :param target: the Node to reach :return: the shortest path, or None when target is unreachable :rtype: list of (Node, Edge) or None