Module `dalpy.graphs`

This module holds classes related to graphs.

This module contains the Vertex, VertexAttributeError, Graph, and GraphVertexError classes. Vertex represents a graph vertex. VertexAttributeError is an error raised by Vertex. Graph represents a directed graph. GraphVertexError is an error raised by Graph.

Examples

Initializing a Graph as well as adding colored vertices and edges:

g = Graph()
a = Vertex('a', color='red')
b = Vertex('b', color='blue')
g.add_vertex(a)
g.add_vertex(b)
g.add_edge(a, b)

The following code will raise a VertexAttributeError because 'colour' is not an attribute of the Vertex a:

x = a['colour']

Classes

class Graph

Represents a directed graph.

A Graph represents a directed graph object whose edges can be assigned weights. The Vertex objects in the Graph should have unique names. For more information on this, see the class docstring of Vertex.

Examples

To initialize a Graph:

g = Graph()

In order to add edges to a Graph, one must first add the Vertex objects that will make up that edge.

a = Vertex('a')
b = Vertex('b')
g.add_vertex(a)
g.add_vertex(b)

Now that a and b have been added to g, one can add an edge between them. Note that there is no edge object.

g.add_edge(a, b)

When adding an edge, one can specify a weight (by default it is None):

g.add_edge(a, b, 1)

One can get a Set of the adjacent edges of a Vertex:

s = g.adj(a)

Initializes an empty Graph in O(1) time.

Methods

def add_edge(self, source, dest, weight=None)

Adds an edge between 2 Vertex objects in this Graph.

This creates an edge from the source Vertex to the destination Vertex. Graph is directed so the edge is in only one direction. That is, an edge from the destination Vertex to the source Vertex will not exist. One can additionally provide a weight for this edge. One may assume that this operation runs in O(1) time with respect to the number of vertices and edges in this Graph.

Args

source: The source Vertex.
dest: The destination Vertex.
weight: The weight for this edge (floating point, integer). By default this is None.

Raises

GraphVertexError: If source or dest is not in this Graph.

def add_vertex(self, vertex)

Adds a Vertex to this Graph.

This runs in O(1) time with respect to the number of vertices and edges in this Graph.

Args

vertex: The Vertex to be added to this Graph.

def adj(self, vertex)

Gets the Vertex objects that are adjacent to a Vertex.

This gets a Set of the Vertex objects that are adjacent to the vertex. Since Set objects preserve insertion order (see Set documentation), the Set will be ordered according to the order in which edges starting from the input Vertex were created. This method runs in O(n) time where n is the number of edges going out of the input Vertex.

Args

vertex: A Vertex.

Returns

A Set containing the vertices adjacent to vertex.

Raises

GraphVertexError: If vertex is not in this Graph.

Examples

To illustrate the nature of the Set returned by this method, first set up a Graph and add some vertices and edges:

g = Graph()
a = Vertex('a')
b = Vertex('b')
c = Vertex('c')
g.add_vertex(a)
g.add_vertex(b)
g.add_vertex(c)
g.add_edge(a, b)
g.add_edge(a, c)

The Set returned by g.adj(a) will always have b preceding c since the edge from a to b was created before the edge from a to c.

def vertices(self)

Gets the vertices in this Graph.

This method runs in O(V) time where V is the number of vertices added to this Graph.

Returns

A Set containing the Vertex objects in this Graph. The order of the vertices in this Set will always be the order in which the vertices were added to this Graph via add_vertex.

def weight(self, source, dest)

Gets the weight of an edge defined by two vertices.

This method runs in O(1) time with respect to the number of vertices and edges in this Graph.

Args

source: The source Vertex of the edge in question.
dest: The destination Vertex of the edge in question.

Returns

The integer or floating point weight associated with the edge from source to dest. This will be None if no weight was specified when the edge was created.

Raises

GraphVertexError: If source or dest is not in this Graph.
GraphEdgeError: If an edge from source to dest does not exist.

class GraphEdgeError (source, dest)

This class is used by Graph to raise errors regarding invalid edges.

Initializes a GraphEdgeError that will be raised associated with a particular Vertex.

Args

source: The source Vertex of the edge this GraphVertexError is being raised in association with.
dest: The destination Vertex of the edge this GraphVertexError is being raised in association with.

Ancestors

builtins.Exception
builtins.BaseException

class GraphVertexError (vertex_name)

This class is used by Graph to raise errors regarding invalid vertices.

Initializes a GraphVertexError that will be raised associated with a particular Vertex.

Args

vertex_name: The string name of the Vertex this GraphVertexError is being raised in association with.

Ancestors

builtins.Exception
builtins.BaseException

class Vertex (name, **attributes)

Represents a graph vertex.

A Vertex has a name and a collection of customizable attributes. The name should be used to identify it in a Graph. Vertex objects are compared with == and via hash code based on their name. The attributes you can use in graph algorithms. For example, you could set colors or time steps as in DFS. One should assume all operations that can be performed on a Vertex are done in O(1) time.

Examples

To initialize a Vertex with a name:

v = Vertex('a')

To initialize a Vertex with some starting attributes, use keyword arguments following the name:

v = Vertex('a', color='red', time=1)

To add additional attributes to an existing Vertex using [] with =:

v['seen'] = False

To update or view existing attributes, use the same idea:

x = v['color']
v['time'] = 3

If you try to get the value of an attribute that does not exist, a VertexAttributeError will be raised (e.g. calling print(v['colour']). If you try to add a new attribute to an existing Vertex where the attribute's type is not str, a TypeError will be raised (e.g. calling v[1] = 'blue').

Initializes a Vertex.

Args

name: The name of the Vertex. Make sure to read the class docstring above regarding naming of Vertex objects.
**attributes: Optional keyword arguments specifying attributes you want the Vertex to start with. See the class docstring above for some possible attributes you could add.

Methods

def get_name(self): Returns the name of this Vertex.

class VertexAttributeError (name, wrong_attribute, attributes)

This class is used by Vertex to raise errors regarding invalid attributes.

Initializes a VertexAttributeError.

Args

name: String name of Vertex that erroneous attribute is associated with.
wrong_attribute: String attribute that does not exist in the Vertex referred to by name.
attributes: The valid attributes in the Vertex referred to by name as a list of str.

Ancestors

builtins.Exception
builtins.BaseException