Package lepl :: Package support :: Module graph
[hide private]
[frames] | no frames]

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.

Classes [hide private]
  Reset
An exception that can be passed to dfs_edges to reset the traversal.
  ConstructorGraphNode
An interface that provides information on constructor arguments.
  ArgAsAttributeMixin
Constructor arguments are stored as attributes; their names are also stored in order so that the arguments can be constructed.
  Visitor
The interface required by the walkers.
  ConstructorWalker
Tree walker (it handles cyclic graphs by ignoring repeated nodes).
  SimpleWalker
This works like ConstructorWalker for generic classes.
  PostorderWalkerMixin
Add a 'postorder' method.
  _LineOverflow
Used internally in ConstructorStr.
  ConstructorStr
Reconstruct the constructors used to generate the graph as a string (useful for repr).
  GraphStr
Generate an ASCII graph of the nodes.
  Proxy
A simple proxy that allows us to re-construct cyclic graphs.
  Clone
Clone the graph, applying a particular clone function.
Functions [hide private]
 
dfs_edges(node, type_)
Iterative DFS, based on http://www.ics.uci.edu/~eppstein/PADS/DFS.py
source code
 
reset(generator)
Reset the traversal by raising Reset.
source code
 
order(node, include, type_, exclude=0)
An ordered sequence of nodes.
source code
 
preorder(node, type_, exclude=0)
The nodes in preorder.
source code
 
postorder(node, type_, exclude=0)
The nodes in postorder.
source code
 
leaves(node, type_=None)
The leaf nodes.
source code
 
loops(node, type_)
Return all loops from the given node.
source code
 
make_proxy()
Generate (setter, Proxy) pairs.
source code
 
clone(node, args, kargs)
The basic clone function that is supplied to Clone.
source code
 
post_clone(function)
Generate a clone function that applies the given function to the newly constructed node (so, when used with Clone, effectively performs a map on the graph).
source code
Variables [hide private]
  FORWARD = 1
  BACKWARD = 2
  NONTREE = 4
  ROOT = 8
  NODE = 16
  LEAF = 32
  POSTORDER = BACKWARD | NONTREE
  PREORDER = FORWARD | NONTREE
Function Details [hide private]

dfs_edges(node, type_)

source code 

Iterative DFS, based on http://www.ics.uci.edu/~eppstein/PADS/DFS.py

Returns forward and reverse edges. Also returns root node in correct order for pre- (FORWARD) and post- (BACKWARD) ordering.

type_ selects which values are iterated over. Children which are not of this type are flagged with LEAF.

order(node, include, type_, exclude=0)

source code 
An ordered sequence of nodes. The ordering is given by 'include' (see the constants PREORDER etc above).

loops(node, type_)

source code 

Return all loops from the given node.

Each loop is a list that starts and ends with the given node.

make_proxy()

source code 
Generate (setter, Proxy) pairs. The setter will supply the value to be proxied later; the proxy itself can be place in the graph immediately.

clone(node, args, kargs)

source code 
The basic clone function that is supplied to Clone. This recreates an instance based on its type and arguments.