Package tdi :: Module _graph :: Class DependencyGraph
[frames] | no frames]

Class DependencyGraph

source code

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.