Graph

This module provides a graph structure that can be used to represent mazes, networks, or any other graph-like structure. It can be manipulated using the methods defined below. These methods allow to add and remove vertices and edges, check for the existence of edges, get neighbors of a vertex, etc.

class Graph.Graph

A graph is a mathematical structure that models pairwise relations between objects. It is implemented using an adjacency dictionary. We assume that all vertices are hashable. The keys of the dictionary are the vertices of the graph. The values of the dictionary are dictionaries themselves. The keys of these dictionaries are the neighbors of the corresponding vertex. The values of these dictionaries are the weights of the corresponding edges. This structure should be manipulated using the methods defined below and not directly.

This class provides generic methods to manipulate any graph. For more specific graphs, such as mazes, you should use the classes that inherit from this class.

__init__()

Initializes a new instance of the class. This constructor initializes the internal adjacency dictionary.

add_edge(vertex_1, vertex_2, weight=1, symmetric=False)

Adds an edge to the graph.

Parameters:

• vertex_1 (Hashable) – First vertex.

• vertex_2 (Hashable) – Second vertex.

• weight (float | int) – Weight of the edge. Defaults to 1.

• symmetric (bool) – Whether the edge is symmetric (undirected). Defaults to False.

Return type:

None

add_vertex(vertex)

Adds a vertex to the graph.

Parameters:

vertex (Hashable) – The vertex to add.

Return type:

None

as_dict()

Returns a dictionary representing the adjacency matrix.

Return type:

dict[Hashable, dict[Hashable, float | int]]

Returns:

Dictionary representing the adjacency matrix.

as_numpy_ndarray()

Returns a numpy.ndarray representing the graph. Entries are given in order in which vertices appear in the adjacency dictionary.

Return type:

object

Returns:

A numpy.ndarray representing the adjacency matrix (return type is object to allow numpy to be optional).

as_torch_tensor()

Returns a torch.tensor representing the graph. Entries are given in order in which vertices appear in the adjacency dictionary

Return type:

object

Returns:

A torch.tensor representing the adjacency matrix (return type is object to allow torch to be optional).

edge_is_symmetric(vertex_1, vertex_2)

Checks whether an edge is symmetric.

Parameters:

• vertex_1 (Hashable) – First vertex.

• vertex_2 (Hashable) – Second vertex.

Return type:

bool

Returns:

Whether the edge is symmetric.

get_edges()

Returns the list of edges in the graph. Symmetric edges are counted once.

Return type:

list[tuple[Hashable, Hashable]]

Returns:

List of edges in the graph, as tuples (vertex_1, vertex_2).

get_neighbors(vertex)

Returns the list of neighbors of a vertex.

Parameters:

vertex (Hashable) – Vertex of which to get neighbors.

Return type:

list[Hashable]

Returns:

List of neighbors of the vertex.

get_vertices()

Returns the list of vertices in the graph.

Return type:

list[Hashable]

Returns:

List of vertices in the graph.

get_weight(vertex_1, vertex_2)

Returns the weight of an edge.

Parameters:

• vertex_1 (Hashable) – First vertex.

• vertex_2 (Hashable) – Second vertex.

Return type:

float | int

Returns:

Weight of the edge.

has_edge(vertex_1, vertex_2)

Checks whether an edge exists between two vertices.

Parameters:

• vertex_1 (Hashable) – First vertex.

• vertex_2 (Hashable) – Second vertex.

Return type:

bool

Returns:

Whether an edge exists between the two vertices.

is_connected()

Checks whether the graph is connected using a depth-first search.

Return type:

bool

Returns:

True if the graph is connected, False otherwise.

minimum_spanning_tree(random_seed=None)

Returns the minimum spanning tree of the graph.

Parameters:

random_seed (int | None) – Seed for the random number generator.

Return type:

Graph

Returns:

Graph representing the minimum spanning tree.

nb_edges()

Returns the number of edges in the graph. Symmetric edges are counted once.

Return type:

int

Returns:

Number of edges in the graph.

nb_vertices()

Returns the number of vertices in the graph.

Return type:

int

Returns:

Number of vertices in the graph.

remove_edge(vertex_1, vertex_2, symmetric=False)

Removes an edge from the graph.

Parameters:

• vertex_1 (Hashable) – First vertex.

• vertex_2 (Hashable) – Second vertex.

• symmetric (bool) – Whether to also delete the symmetric edge. Defaults to False.

Return type:

None

remove_vertex(vertex)

Removes a vertex from the graph. Also removes all edges connected to this vertex.

Parameters:

vertex (Hashable) – Vertex to remove.

Return type:

None