graphs.graph_adjacency_list

Author: Vikram Nithyanandam

Description: The following implementation is a robust unweighted Graph data structure implemented using an adjacency list. This vertices and edges of this graph can be effectively initialized and modified while storing your chosen generic value in each vertex.

Adjacency List: https://en.wikipedia.org/wiki/Adjacency_list

Potential Future Ideas: - Add a flag to set edge weights on and set edge weights - Make edge weights and vertex values customizable to store whatever the client wants - Support multigraph functionality if the client wants it

Attributes

T

Classes

GraphAdjacencyList
TestGraphAdjacencyList	A class whose instances are single test cases.

Module Contents

class graphs.graph_adjacency_list.GraphAdjacencyList(vertices: list[T], edges: list[list[T]], directed: bool = True)

Bases: Generic[T]

__repr__() → str

add_edge(source_vertex: T, destination_vertex: T) → None

Creates an edge from source vertex to destination vertex. If any given vertex doesn’t exist or the edge already exists, a ValueError will be thrown.

add_vertex(vertex: T) → None

Adds a vertex to the graph. If the given vertex already exists, a ValueError will be thrown.

clear_graph() → None

Clears all vertices and edges.

contains_edge(source_vertex: T, destination_vertex: T) → bool

Returns True if the graph contains the edge from the source_vertex to the destination_vertex, False otherwise. If any given vertex doesn’t exist, a ValueError will be thrown.

contains_vertex(vertex: T) → bool

Returns True if the graph contains the vertex, False otherwise.

remove_edge(source_vertex: T, destination_vertex: T) → None

Removes the edge between the two vertices. If any given vertex doesn’t exist or the edge does not exist, a ValueError will be thrown.

remove_vertex(vertex: T) → None

Removes the given vertex from the graph and deletes all incoming and outgoing edges from the given vertex as well. If the given vertex does not exist, a ValueError will be thrown.

adj_list: dict[T, list[T]]

directed

class graphs.graph_adjacency_list.TestGraphAdjacencyList(methodName='runTest')

Bases: unittest.TestCase

A class whose instances are single test cases.

By default, the test code itself should be placed in a method named ‘runTest’.

If the fixture may be used for many test cases, create as many test methods as are needed. When instantiating such a TestCase subclass, specify in the constructor arguments the name of the test method that the instance is to execute.

Test authors should subclass TestCase for their own tests. Construction and deconstruction of the test’s environment (‘fixture’) can be implemented by overriding the ‘setUp’ and ‘tearDown’ methods respectively.

If it is necessary to override the __init__ method, the base class __init__ method must always be called. It is important that subclasses should not change the signature of their __init__ method, since instances of the classes are instantiated automatically by parts of the framework in order to be run.

When subclassing TestCase, you can set these attributes: * failureException: determines which exception will be raised when

the instance’s assertion methods fail; test methods raising this exception will be deemed to have ‘failed’ rather than ‘errored’.

• longMessage: determines whether long messages (including repr of

  objects used in assert methods) will be printed on failure in addition to any explicit message passed.

• maxDiff: sets the maximum length of a diff in failure messages

  by assert methods using difflib. It is looked up as an instance attribute so can be configured by individual tests if required.

__assert_graph_edge_does_not_exist_check(undirected_graph: GraphAdjacencyList, directed_graph: GraphAdjacencyList, edge: list[int]) → None

__assert_graph_edge_exists_check(undirected_graph: GraphAdjacencyList, directed_graph: GraphAdjacencyList, edge: list[int]) → None

__assert_graph_vertex_does_not_exist_check(undirected_graph: GraphAdjacencyList, directed_graph: GraphAdjacencyList, vertex: int) → None

__assert_graph_vertex_exists_check(undirected_graph: GraphAdjacencyList, directed_graph: GraphAdjacencyList, vertex: int) → None

__generate_graphs(vertex_count: int, min_val: int, max_val: int, edge_pick_count: int) → tuple[GraphAdjacencyList, GraphAdjacencyList, list[int], list[list[int]]]

__generate_random_edges(vertices: list[int], edge_pick_count: int) → list[list[int]]

test_add_and_remove_edges_repeatedly() → None

test_add_and_remove_vertices_repeatedly() → None

test_add_edge() → None

test_add_edge_exception_check() → None

test_add_vertex_exception_check() → None

test_add_vertices() → None

test_contains_edge() → None

test_contains_edge_exception_check() → None

test_contains_vertex() → None

test_init_check() → None

test_remove_edge() → None

test_remove_edge_exception_check() → None

test_remove_vertex_exception_check() → None

test_remove_vertices() → None

graphs.graph_adjacency_list.T