API Reference for Enthought Tool Suite 2.7.1

Graph algorithms

A graph is represented by a dictionary which represents the adjacency relation,
where node a has an arc to node b iff `b in d[a]'.

Classes

• CyclicGraph - Exception for cyclic graphs.

Function summary

• closure(graph, sorted = True)
• eq(g1, g2)
• map(f, graph)
• reachable_graph(graph, nodes)
• reverse(graph)
• topological_sort(graph)

Functions

• closure(graph, sorted = True)

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

• eq(g1, g2)
• map(f, graph)

  Maps function f over the nodes in graph.

  >>> map(str, { 1:[2,3] })
  {'1': ['2', '3']}
  

• reachable_graph(graph, nodes)

  Return the subgraph of the given graph reachable from the given nodes.

  >>> reachable_graph({'a':'bc', 'b':'c' }, 'a')
  {'a': 'bc', 'b': 'c'}
  >>> reachable_graph({'a':'bc', 'b':'c' }, 'b')
  {'b': 'c'}
  >>> reachable_graph({'a':'bc', 'b':'c' }, 'c')
  {}
  

• reverse(graph)

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

• topological_sort(graph)

  Returns the nodes in the graph in topological order.

Imported Names

Copyright © 2002-2008 Enthought, Inc.