Package CedarBackup3 :: Module util :: Class DirectedGraph
[hide private]
[frames] | no frames]

Class DirectedGraph

source code

object --+
         |
        DirectedGraph

Represents a directed graph.

A graph G=(V,E) consists of a set of vertices V together with a set E of vertex pairs or edges. In a directed graph, each edge also has an associated direction (from vertext v1 to vertex v2). A DirectedGraph object provides a way to construct a directed graph and execute a depth- first search.

This data structure was designed based on the graphing chapter in The Algorithm Design Manual, by Steven S. Skiena.

This class is intended to be used by Cedar Backup for dependency ordering. Because of this, it's not quite general-purpose. Unlike a "general" graph, every vertex in this graph has at least one edge pointing to it, from a special "start" vertex. This is so no vertices get "lost" either because they have no dependencies or because nothing depends on them.

Instance Methods [hide private]
 
__init__(self, name)
Directed graph constructor.
source code
 
__repr__(self)
Official string representation for class instance.
source code
 
__str__(self)
Informal string representation for class instance.
source code
 
__eq__(self, other)
Equals operator, implemented in terms of original Python 2 compare operator.
source code
 
__lt__(self, other)
Less-than operator, implemented in terms of original Python 2 compare operator.
source code
 
__gt__(self, other)
Greater-than operator, implemented in terms of original Python 2 compare operator.
source code
 
__cmp__(self, other)
Original Python 2 comparison operator.
source code
 
_getName(self)
Property target used to get the graph name.
source code
 
createVertex(self, name)
Creates a named vertex.
source code
 
createEdge(self, start, finish)
Adds an edge with an associated direction, from start vertex to finish vertex.
source code
 
topologicalSort(self)
Implements a topological sort of the graph.
source code
 
_topologicalSort(self, vertex, ordering)
Recursive depth first search function implementing topological sort.
source code
 
__ge__(x, y)
x>=y
 
__le__(x, y)
x<=y

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

Class Variables [hide private]
  _UNDISCOVERED = 0
  _DISCOVERED = 1
  _EXPLORED = 2
Properties [hide private]
  name
Name of the graph.

Inherited from object: __class__

Method Details [hide private]

__init__(self, name)
(Constructor)

source code 

Directed graph constructor.

Parameters:
  • name (String value.) - Name of this graph.
Overrides: object.__init__

__repr__(self)
(Representation operator)

source code 

Official string representation for class instance.

Overrides: object.__repr__

__str__(self)
(Informal representation operator)

source code 

Informal string representation for class instance.

Overrides: object.__str__

__cmp__(self, other)
(Comparison operator)

source code 

Original Python 2 comparison operator.

Parameters:
  • other - Other object to compare to.
Returns:
-1/0/1 depending on whether self is <, = or > other.

createVertex(self, name)

source code 

Creates a named vertex.

Parameters:
  • name - vertex name
Raises:
  • ValueError - If the vertex name is None or empty.

createEdge(self, start, finish)

source code 

Adds an edge with an associated direction, from start vertex to finish vertex.

Parameters:
  • start - Name of start vertex.
  • finish - Name of finish vertex.
Raises:
  • ValueError - If one of the named vertices is unknown.

topologicalSort(self)

source code 

Implements a topological sort of the graph.

This method also enforces that the graph is a directed acyclic graph, which is a requirement of a topological sort.

A directed acyclic graph (or "DAG") is a directed graph with no directed cycles. A topological sort of a DAG is an ordering on the vertices such that all edges go from left to right. Only an acyclic graph can have a topological sort, but any DAG has at least one topological sort.

Since a topological sort only makes sense for an acyclic graph, this method throws an exception if a cycle is found.

A depth-first search only makes sense if the graph is acyclic. If the graph contains any cycles, it is not possible to determine a consistent ordering for the vertices.

Returns:
Ordering on the vertices so that all edges go from left to right.
Raises:
  • ValueError - If a cycle is found in the graph.

Note: If a particular vertex has no edges, then its position in the final list depends on the order in which the vertices were created in the graph. If you're using this method to determine a dependency order, this makes sense: a vertex with no dependencies can go anywhere (and will).

_topologicalSort(self, vertex, ordering)

source code 

Recursive depth first search function implementing topological sort.

Parameters:
  • vertex - Vertex to search
  • ordering - List of vertices in proper order

Property Details [hide private]

name

Name of the graph.

Get Method:
_getName(self) - Property target used to get the graph name.