Home | Trees | Indices | Help |
---|
|
Unweighted graph algorithms of the pyGraphADT package.
Python version by Danver Braganza based on code originally authored by Michael J. Dinneen, with contributions by Sonny Datt.
2010 February
This module is part of the pyGraphADT package, and contains a number of basic graph algorithms which operate upon the graph abstract types included in this same package.
This module is designed to be used in the teaching of the Computer Science 220 course at the University of Auckland.
|
|||
Countpair |
|
|||
list of integers |
|
||
tuple |
|
||
tuple |
|
||
tuple |
|
||
boolean |
|
||
boolean |
|
||
|
|||
list |
|
||
boolean |
|
||
boolean |
|
||
integer or infinity |
|
||
boolean |
|
||
is of zero or more integers and zero or more None |
|
||
is of zero or more integers and zero or more None |
|
||
tuple -> integer or infinity, list |
|
||
list of lists |
|
||
integer or infinity |
|
||
integer or infinity |
|
|
|||
__package__ =
|
|
Returns a list containing the direct ancestors of every vertex as discovered during a breadth-first search starting from node v. This function performs a breadth-first search starting at the vertex labelled v. A list is returned such that the element at index i is the label of the direct parent of vertex i. If a vertex has not been discovered during the BFS traversal (due to being disconnected) its parent is set to None. Furthermore, the parent of v is set to itself. Note: The correct labels of the parents are used. This may conflict with some versions of the Java implementation, where indices are incremented by one.
|
Performs breadth-first search from vertex v and returns number of vertices discovered and a list showing the order vertices was discovered. This function performs a breadth-first search starting from vertex v, and returns a tuple containing two values. The first value is the number of vertices discovered during breadth-first search, and the second a list where element i is the order in which vertex i was discovered. If vertex i is not discovered by this search, then element i of this list is set to None. Note: Numberings in this list start from zero.
|
Iterates over the vertices in graph g in breadth-first order. This function iterates over the vertices in a graph is breadth-first order. It will repeat vertices if there are cycles in the graph, but will not expand them. This is so that code which makes use of this iterator can detect cycles, while trusting that this iterator will never loop infinitely. This function is not intended to be called by external code.
|
Performs depth-first search from vertex v, and returns number of vertices discovered as well as two lists showing the pre-order and post-order in which vertices were discovered. This function performs a depth-first search starting from vertex v, and returns a tuple containing three values. The first value is the number of vertices discovered during the search. The second value is a list of preorders, where element i is the order in which vertex i was first visited. The third value is a list of postorders, where element i is the order it which vertex i was lat visited. If a node is never visited, its preorder and postorder will both be None. Note: Numbering of order in both lists start from zero.
|
True if and only if the graph g is connected. This function checks for connectedness of graph g by converting it into an undirected graph, and then performing breadth-first search. G is considered connected if this breadth-first search is able to discover all nodes. Note: if g is a directed graph, then this function returns True if g is weakly connected.
|
Returns True if and only if the graph g is strongly connected. This function returns true if and only if g is strongly connected. A strongly connected graph is defined as one where for every pair of vertices u and v, there exists a path from u to v.
|
Finds the strong components of graph g. This function finds the strong components of graph g. For any pair of vertices v, u, if there is a path from v to u and a path from u to v, then u and v must belong to the same strongly-connected-component. This function returns a list where the element at index i is the label of the component to which vertex i belongs. If graph g is strongly connected, every element in this list will be 0, since every vertex is in component 0. Note: Numberings in this list start from zero. To find the number of components, use max(strongComponents(g)) + 1
|
Returns a list containing the direct ancestors of every vertex as discovered during a depth-first search starting from node v. This function performs a depth-first search starting at the vertex labelled v. A list is returned such that the element at index i is the label of the direct parent of vertex i. If a vertex has not been discovered during the DFS traversal (due to being disconnected) its parent is set to None. Furthermore, the parent of v is set to itself.
|
Returns True if and only if g is an Acyclic graph. This function checks g for cycles. If g is an undirected graph, cycles of length 2 will be ignored. If g is a directed graph, then any edges in g will count as a cycle of length 2. Any self-loops in g will also be counted as cycles.
|
True if, given that g is an undirected graph, it is also acyclic. Not meant to be called by external code
|
Returns the girth of g. This function only returns values for graphs with girth >= 3 or 1. Girth 1 is caused by self-loops. Girth >= 3 is the normal case of cycles Girth infinity indicates no cycles Girth 2 is never returned, because every undirected edge would otherwise create a cycle of girth 2. If the only cycle which exists is of girth 2, infinity is returned instead.
|
Returns True if and only if g is bipartite This function verifies whether g is bipartite by attempting a 2-colouring of the vertices. If the colouring succeeds, the function returns True, else False
|
Sorts the vertices in DirectedGraph g in a topological order This function performs a depth-first search of g, starting at v, to determine the dependencies and then returns a topological ordering of the vertices such that for every vertex v, its ancestors in g appear earlier in the ordering. The ordering is represented by a list with element i being the order of vertex i. If vertex i is not discoverable by a depth-first search from v, element i of this list will be None. g must be a directed acyclic graph, or an error is raised. If g is not a connected graph, it may be better to use topSort2 instead.
|
Sorts the vertices in DirectedGraph g in a topological order This function returns a topological ordering of the vertices such that for every vertex v, its ancestors in g appear earlier in the ordering. The ordering is represented by a list with element i being the order of vertex i. g must be a directed acyclic graph, or an error is raised.
|
Returns the length to the shortest path to the furthest vertex from v, as well as the distance to all the other vertices. This function computes the eccentricity of vertex v in graph g by performing breadth-first search and noting the distance of the last node to be discovered. This function also computes the distance of every vertex discovered in this way. Vertices that cannot be discovered are set to a distance of infinity. If all nodes are not discovered, the eccentricity of v is set to infinity. This function returns a tuple where the first element is the eccentricity of v. The second element is a list, where element i is the shortest distance from vertex v to vertex i.
|
Returns a matrix of all the distances between vertices in g. This function returns an n x n matrix, where n is the size of the vertex set of g. The value at element i,j of this matrix is the shortest distance from vertex i to vertex j. If j is not reachable from i, then the element at i,j is set to infinity.
|
Returns the diameter of g. The diameter of g is defined as the maximum eccentricity of its vertices. This function calculates the eccentricity of every vertex in g and then returns the maximum.
|
Returns the radius of g. The radius of g is defined as the minimum eccentricity of its vertices. This function calculates the eccentricity of every vertex in g and then returns the minimum.
|
Home | Trees | Indices | Help |
---|
Generated by Epydoc 3.0.1 on Thu Feb 25 13:23:34 2010 | http://epydoc.sourceforge.net |