Package graphadt :: Module algorithms
[hide private]
[frames] | no frames]

Module algorithms

source code

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.

Classes [hide private]
  Countpair
Functions [hide private]
list of integers
getBFSParents(g, v)
Returns a list containing the direct ancestors of every vertex as discovered during a breadth-first search starting from node v.
source code
tuple
BFS(g, v)
Performs breadth-first search from vertex v and returns number of vertices discovered and a list showing the order vertices was discovered.
source code
tuple
BFSIt(g, v)
Iterates over the vertices in graph g in breadth-first order.
source code
tuple
DFS(g, v)
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.
source code
boolean
isConnected(g)
True if and only if the graph g is connected.
source code
boolean
isStronglyConnected(g)
Returns True if and only if the graph g is strongly connected.
source code
 
strongComponents(g)
Finds the strong components of graph g.
source code
list
getDFSParents(g, v, parents=None)
Returns a list containing the direct ancestors of every vertex as discovered during a depth-first search starting from node v.
source code
boolean
isAcyclic(g)
Returns True if and only if g is an Acyclic graph.
source code
boolean
isAcyclicUndirected(g)
True if, given that g is an undirected graph, it is also acyclic.
source code
integer or infinity
girth(g)
Returns the girth of g.
source code
boolean
isBipartite(g)
Returns True if and only if g is bipartite
source code
is of zero or more integers and zero or more None
topSort1(g, v)
Sorts the vertices in DirectedGraph g in a topological order
source code
is of zero or more integers and zero or more None
topSort2(g)
Sorts the vertices in DirectedGraph g in a topological order
source code
tuple -> integer or infinity, list
maxDistance(g, v)
Returns the length to the shortest path to the furthest vertex from v, as well as the distance to all the other vertices.
source code
list of lists
distanceMatrix(g)
Returns a matrix of all the distances between vertices in g.
source code
integer or infinity
diameter(g)
Returns the diameter of g.
source code
integer or infinity
radius(g)
Returns the radius of g.
source code
Variables [hide private]
  __package__ = 'graphadt'
Function Details [hide private]

getBFSParents(g, v)

source code 

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.

Parameters:
Returns: list of integers
index of parent or None
Raises:
  • ValueError - if v is not the label of a vertex in g

BFS(g, v)

source code 

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.

Parameters:
Returns: tuple
an integer containing the number of vertices dicovered, a list comprised of integers and one or more None.
Raises:
  • ValueError - if v is not the label of a vertex in g

BFSIt(g, v)

source code 

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.

Parameters:
Returns: tuple
yields (vfrom, vto), where vfrom is the current parent vertex, and vto is the vertex being discovered.
Raises:
  • ValueError - if v is not the label of a vertex in g
  • StopIteration - if all vertices have been discovered.

DFS(g, v)

source 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.

Parameters:
Returns: tuple
a tuple of: integer representing total vertices discovered preorder : a list containing the preorders of every vertex postorder: a list containing the postorders of every vertex
Raises:
  • ValueError - if v is not the label of a vertex in g

isConnected(g)

source code 

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.

Parameters:
Returns: boolean
True if and only if graph g is connected False otherwise

isStronglyConnected(g)

source code 

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.

Parameters:
Returns: boolean
True if and only if graph g is strongly connected False otherwise

strongComponents(g)

source code 

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

Parameters:
Returns:
a list comprised of integers.
Raises:
  • ValueError - if v is not the label of a vertex in g

getDFSParents(g, v, parents=None)

source code 

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.

Parameters:
Returns: list
a list comprised of integers and one or more None.
Raises:
  • ValueError - if v is not the label of a vertex in g

    Note: The correct labels of the parents are used. This may conflict with some versions of the Java implementation, where indices returned are incremented by one.

isAcyclic(g)

source code 

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.

Parameters:
  • g (graphadt.graphtypes.Graph) - the graph
Returns: boolean
True if and only if g is acyclic

isAcyclicUndirected(g)

source code 

True if, given that g is an undirected graph, it is also acyclic.

Not meant to be called by external code

Parameters:
  • g (graphadt.graphtypes.Graph) - the graph
Returns: boolean
True if and only if g is acyclic

girth(g)

source 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.

Parameters:
  • g (graphadt.graphtypes.Graph) - the graph
Returns: integer or infinity
length of smallest cycle in g

isBipartite(g)

source code 

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

Parameters:
  • g (graphadt.graphtypes.Graph) - the graph
Returns: boolean
True if and only if g is bipartite

topSort1(g, v)

source code 

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.

Parameters:
  • g (graphadt.graphtypes.Graph) - the graph to sort
  • v (integer) - the label of a vertex
Returns: is of zero or more integers and zero or more None
zero or more integers and zero or more None
Raises:
  • ValueError - if g is not a directed acyclic graph
  • ValueError - if v is not a vertex in g

topSort2(g)

source code 

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.

Parameters:
  • g (graphadt.graphtypes.Graph) - the graph to sort
Returns: is of zero or more integers and zero or more None
zero or more integers and zero or more None
Raises:
  • ValueError - if g is not a directed acyclic graph

maxDistance(g, v)

source code 

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.

Parameters:
  • g (graphadt.graphtypes.Graph) - the graph
  • v (integer) - the label of a vertex
Returns: tuple -> integer or infinity, list
eccentricity of v, distance of other vertices from v
Raises:
  • ValueError - if v is not the label of a vertex in g

distanceMatrix(g)

source code 

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.

Parameters:
  • g (graphadt.graphtypes.Graph) - the graph
Returns: list of lists
distance matrix of g

diameter(g)

source code 

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.

Parameters:
  • g (graphadt.graphtypes.Graph) - the graph
Returns: integer or infinity
the diameter of g

radius(g)

source code 

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.

Parameters:
  • g (graphadt.graphtypes.Graph) - the graph
Returns: integer or infinity
the radius of g