Package tdi :: Module _graph :: Class DependencyGraph

Class DependencyGraph

object --+
         |
        DependencyGraph

Dependency Graph Container

This is a simple directed acyclic graph. The graph starts empty, and new nodes (and edges) are added using the add method. If the newly added create a cycle, an exception is thrown.

Finally, the graph is resolved using the resolve method. The method will return topologically ordered nodes and destroy the graph. The topological order is stable, meaning, the same graph will always produce the same output.

Instance Methods

__init__(self)
Initialization

source code

add(self, start, end)
Add a new nodes with edge to the graph

source code

list

resolve(self)
Resolve graph and return nodes in topological order

source code

Inherited from object: __delattr__, __format__, __getattribute__, __hash__, __new__, __reduce__, __reduce_ex__, __repr__, __setattr__, __sizeof__, __str__, __subclasshook__

Properties
Inherited from `object`: `__class__`

Method Details

init(self)
(Constructor)

source code

Initialization

Overrides: object.__init__

add(self, start, end)

source code

Add a new nodes with edge to the graph

The edge is directed from start to end.

Parameters:

start (str) - Node
end (str) - Node

resolve(self)

source code

Resolve graph and return nodes in topological order

The graph is defined by outgoing and incoming dicts (mapping nodes to their outgoing or incoming neighbours). The graph is destroyed in the process.

Returns: list: Sorted node list. The output is stable, because nodes on the same level are sorted alphabetically. Furthermore all leaf nodes are put at the end.

Class DependencyGraph

__init__(self) (Constructor)

add(self, start, end)

resolve(self)

init(self)
(Constructor)