codetools.util.graph

module documentation

(source)

Graph algorithms. A graph is represented by a dictionary which represents the adjacency relation, where node ``a`` has an arc to node ``b`` if and only if ``b in d[a]``.

Function	`closure`	Returns the transitive closure of the graph. If sorted is True then the successor nodes will be sorted into topological order.
Function	`eq`	Undocumented
Function	`map`	Maps function f over the nodes in graph.
Function	`reachable_graph`	Return the subgraph of the given graph reachable from the given nodes.
Function	`reverse`	Returns the reverse of a graph, that is the graph made when all of the edges are reversed.

def closure(graph, sorted=True): (source)

Returns the transitive closure of the graph. If sorted is True then the successor nodes will be sorted into topological order.

def eq(g1, g2): (source)

Undocumented

def map(f, graph): (source)

Maps function f over the nodes in graph. >>> map(str, { 1:[2,3] }) {'1': ['2', '3']}

def reachable_graph(graph, nodes): (source)

Return the subgraph of the given graph reachable from the given nodes. >>> sorted(reachable_graph({'a':'bc', 'b':'c' }, 'a').items()) [('a', 'bc'), ('b', 'c')] >>> reachable_graph({'a':'bc', 'b':'c' }, 'b') {'b': 'c'} >>> reachable_graph({'a':'bc', 'b':'c' }, 'c') {}

def reverse(graph): (source)

Returns the reverse of a graph, that is the graph made when all of the edges are reversed.