Module graph

source code

Graph traversal - supports generic Python classes, but has extensions for classes that record their own constructor arguments (and so allow deep cloning of graphs).

The fundamental dfs_edges routine will traverse over (ie provides an iterator that returns (flag, node) pairs, where flag describes the type of node and ordering) a graph made of iterable Python objects. Only the __iter__ method (implemented by all containers) is required. However, in general this is too broad (for example, Strings are iterable, and single character strings contain themselves), so a type can be specified which identifies those nodes to be treated as "interior" nodes. Children of interior nodes are returned as "leaf" nodes, but are not iterated over themselves.

The order function provides a simpler interface to this traversal, allowing a particular order to be generated, and, for example, optionally excluding leaf nodes.

ConstructorGraphNode is motivated by data constructors and exposes its constructor arguments (this is important because if we are cloning a graph we want to replace constructor arguments that correspond to child nodes with their clones). This currently has a single implementation, ArgAsAttributeMixin (there used to be another, but it was equivalent to the generic case with SimpleWalker).

The 'Walker' (SimpleWalker and ConstructorWalker) and Visitor classes provide a different approach to traversing the graph (compared to the simple sequences of nodes provided by dfs_edges et al), that reflects the emphasis on constructors described above: the walker takes a visitor sub-class and calls it in a way that replicates the original calls to the node constructors.