Home | Trees | Indices | Help |
|
---|
|
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.
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
Inherited from |
|
|||
_UNDISCOVERED = 0
|
|||
_DISCOVERED = 1
|
|||
_EXPLORED = 2
|
|
|||
name Name of the graph. |
|||
Inherited from |
|
|
|
|
|
|
start
vertex to finish vertex.
|
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.
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). |
|
|
nameName of the graph.
|
Home | Trees | Indices | Help |
|
---|
Generated by Epydoc 3.0beta1 on Sat Nov 15 12:17:01 2008 | http://epydoc.sourceforge.net |