Package pyxb :: Package utils :: Module utility :: Class Graph

Class Graph

Represent a directed graph with arbitrary objects as nodes.

This is used in the code generator to determine order dependencies among components within a namespace, and schema that comprise various namespaces. An edge from source to target indicates that some aspect of source requires that some aspect of target already be available.

Instance Methods

[hide private]

__init__(self, root=None)

source code

addEdge(self, source, target)
Add a directed edge from the source to the target. source code

addNode(self, node)
Add the given node to the graph.

source code

set

roots(self, reset=False)
Return the set of nodes calculated to be roots (i.e., those that have no incoming edges).

source code

addRoot(self, root)
Add the provided node as a root node, even if it has incoming edges.

source code

edgeMap(self)
Return the edges in the graph.

source code

edges(self)
Return the edges in the graph.

source code

nodes(self)
Return the set of nodes in the graph.

source code

tarjan(self, reset=False)
Execute Tarjan's algorithm on the graph.

source code

_tarjan(self, v)
Do the work of Tarjan's algorithm for a given root node.

source code

scc(self, reset=False)
Return the strongly-connected components of the graph.

source code

sccMap(self, reset=False)
Return a map from nodes to the strongly-connected component to which the node belongs.

source code

sccOrder(self, reset=False)
Return the strongly-connected components in order.

source code

sccForNode(self, node, **kw)
Return the strongly-connected component to which the given node belongs.

source code

cyclomaticComplexity(self)
Return the cyclomatic complexity of the graph.

source code

__dfsWalk(self, source)

source code

_generateDOT(self, title='UNKNOWN', labeller=None) source code

dfsOrder(self, reset=False)
Return the nodes of the graph in depth-first-search order.

source code

rootSetOrder(self)
Return the nodes of the graph as a sequence of root sets.

source code

Class Variables

[hide private]

__dfsOrder = None
hash(x)

__roots = None
hash(x)

__edgeMap = None
hash(x)

__scc = None
hash(x)

__sccMap = None
hash(x)

__sccOrder = None
hash(x)

Method Details

[hide private]

addEdge(self, source, target)

source code

Add a directed edge from the source to the target.

The nodes are added to the graph if necessary.

roots(self, reset=False)

source code

Return the set of nodes calculated to be roots (i.e., those that have no incoming edges).

This caches the roots calculated in a previous invocation unless the reset keyword is given the value True.

Parameters:

reset - If True, any cached value is discarded and recomputed. No effect if False (defalut).

Returns: set

Note: Upon reset, any notes that had been manually added using addNode will no longer be in the set.

addRoot(self, root)

source code

Add the provided node as a root node, even if it has incoming edges.

The node need not be present in the graph (if necessary, it is added).

Note that roots added in this way do not survive a reset using roots.

Returns:: self

edgeMap(self)

source code

Return the edges in the graph.

The edge data structure is a map from the source node to the set of nodes that can be reached in a single step from the source.

edges(self)

source code

Return the edges in the graph.

The edge data structure is a set of node pairs represented as ( source, target ).

nodes(self)

source code

Return the set of nodes in the graph.

The node collection data structure is a set containing node objects, whatever they may be.

tarjan(self, reset=False)

source code

Execute Tarjan's algorithm on the graph.

Tarjan's algorithm computes the strongly-connected components of the graph: i.e., the sets of nodes that form a minimal closed set under edge transition. In essence, the loops. We use this to detect groups of components that have a dependency cycle.

Parameters:

reset - If True, any cached component set is erased and recomputed. If True, an existing previous result is left unchanged.

scc(self, reset=False)

source code

Return the strongly-connected components of the graph.

The data structure is a set, each element of which is itself a set containing one or more nodes from the graph.

See Also: tarjan.

sccMap(self, reset=False)

source code

Return a map from nodes to the strongly-connected component to which the node belongs.

Parameters:

reset - If True, the tarjan method will be re-invoked, propagating the reset value. If False (default), a cached value will be returned if available.

See Also: tarjan.

sccOrder(self, reset=False)

source code

Return the strongly-connected components in order.

The data structure is a list, in dependency order, of strongly connected components (which can be single nodes). Appearance of a node in a set earlier in the list indicates that it has no dependencies on any node that appears in a subsequent set. This order is preferred over dfsOrder for code generation, since it detects loops.

See Also: tarjan.

sccForNode(self, node, **kw)

source code

Return the strongly-connected component to which the given node belongs.

Any keywords suppliend when invoking this method are passed to the sccMap method.

Returns:: The SCC set, or None if the node is not present in the results of Tarjan's algorithm.

dfsOrder(self, reset=False)

source code

Return the nodes of the graph in depth-first-search order.

The data structure is a list. Calculated lists are retained and returned on future invocations, subject to the reset keyword.

Parameters:

reset - If True, discard cached results and recompute the order.

rootSetOrder(self)

source code

Return the nodes of the graph as a sequence of root sets.

The first root set is the set of nodes that are roots: i.e., have no incoming edges. The second root set is the set of nodes that have incoming nodes in the first root set. This continues until all nodes have been reached. The sets impose a partial order on the nodes, without being as constraining as sccOrder.

Returns:: a list of the root sets.