Graph Interface

Several Beyond Brute Force problems use the same course-provided representation for a simple, undirected graph.

The class is defined in:

src/course/common/graph.py

Algorithms that use this representation may import it with:

from course.common.graph import Graph

The course-provided input routines construct the Graph object before calling your algorithm. In most cases, your code will therefore use a Graph rather than read or construct one itself.

This page defines the public interface that student code may rely on.

Graph Representation

A Graph contains vertices numbered consecutively from 0 through num_vertices - 1.

For example, if:

graph.num_vertices == 5

then the vertex set is:

V=\{0,1,2,3,4\}.

The graph is simple and undirected:

self-loops are not permitted;
parallel edges are not permitted; and
an edge $(u,v)$ is the same edge as $(v,u)$ .

The supplied Graph object should be treated as read-only. Algorithms should maintain their own state rather than modifying the graph.

Public Attributes

`graph.num_vertices`

graph.num_vertices

is an integer containing the number of vertices in the graph.

For example:

for v in range(graph.num_vertices):
    ...

iterates over every vertex.

Accessing num_vertices takes constant time.

`graph.edges`

graph.edges

is a tuple containing all edges in the graph.

Each edge is represented as a two-element tuple of integers:

(u, v)

The stored representation uses u < v.

For example:

for u, v in graph.edges:
    ...

iterates over every edge.

Iterating over the complete collection takes $O(|E|)$ time.

Student code should not depend on the order in which edges appear.

Public Methods

`graph.neighbors(vertex)`

graph.neighbors(vertex)

returns a frozenset containing the vertices adjacent to vertex.

For example:

for u in graph.neighbors(v):
    ...

iterates over all neighbors of v.

The returned collection is read-only.

Retrieving the neighbor collection takes constant time. Iterating over all neighbors takes $O(\deg(v))$ time.

Membership testing such as:

u in graph.neighbors(v)

uses Python’s hash-based set representation and therefore takes expected constant time.

`graph.degree(vertex)`

graph.degree(vertex)

returns the degree of vertex.

For example:

if graph.degree(v) == 0:
    ...

tests whether v is isolated.

This operation takes constant time.

`graph.has_edge(u, v)`

graph.has_edge(u, v)

returns True if the graph contains the edge between vertices u and v, and False otherwise.

For example:

if graph.has_edge(2, 4):
    ...

Because the graph is undirected:

graph.has_edge(2, 4)

and

graph.has_edge(4, 2)

produce the same result.

Edge lookup uses the graph’s hash-based adjacency representation and therefore takes expected constant time.

`len(graph)`

Python’s built-in len() function may also be used:

len(graph)

It returns the number of vertices and is equivalent to:

graph.num_vertices

This operation takes constant time.

Constructing Graphs for Tests

The course input routines normally construct graph objects for you. However, you may also construct small graphs directly when writing your own tests.

Use:

Graph.from_edges(num_vertices, edges)

For example:

graph = Graph.from_edges(
    5,
    [
        (0, 1),
        (0, 2),
        (1, 2),
        (2, 3),
        (2, 4),
        (3, 4),
    ],
)

This constructs the same graph used in the Minimum Vertex Cover example.

from_edges() rejects:

vertex numbers outside the valid range;
self-loops; and
duplicate edges.

The construction process takes $O(|V|+|E|)$ expected time.

Graph construction is support functionality and is not part of the running time of a solver once the parsed graph has been passed to solve().

Example

Suppose graph represents:

0 ----- 1
 \     /
   \ /
    2 ----- 3

The following expressions illustrate the public interface:

graph.num_vertices
# 4

len(graph)
# 4

graph.edges
# tuple containing the graph's edges

graph.neighbors(2)
# frozenset containing 0, 1, and 3

graph.degree(2)
# 3

graph.has_edge(0, 2)
# True

graph.has_edge(0, 3)
# False

The exact printed order of sets or edges should not be used as part of an algorithm.

Private Implementation Details

The Graph class may contain attributes whose names begin with an underscore, such as:

_adjacency

These are implementation details and are not part of the student-facing interface.

Do not access them directly.

For example, use:

graph.neighbors(v)

rather than:

graph._adjacency[v]

Only the attributes and methods documented on this page are guaranteed to remain available to student code.