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

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. Edge directions are ignored: the graph is connected if all vertices are linked when edges are followed in both directions (weak connectivity). This is the notion used by minimum_spanning_tree and random_spanning_tree, and it is the usual connectivity for undirected graphs such as mazes.

Return type:

bool

Returns:

True if the graph is connected, False otherwise.

minimum_spanning_tree(random_seed=None)

Returns a minimum spanning tree of the graph, i.e., a spanning tree whose total weight is minimal. It is computed with Prim’s algorithm: starting from a vertex, the tree grows by adding the lightest edge between a vertex of the tree and a vertex outside of it. Ties between edges of the same weight are broken randomly, so that different seeds may give different minimum spanning trees. The graph is considered undirected: an edge can link the tree to a new vertex whatever its direction. Each edge of the tree keeps the direction and weight of the edge of the graph it comes from, and is symmetric if the graph also has the reverse edge, with the same weight. To obtain a random spanning tree, without considering weights, see random_spanning_tree.

Parameters:

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

Return type:

Graph

Returns:

Graph representing the minimum spanning tree.

Raises:

PyRatException – If the graph is empty or not connected.

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.

random_spanning_tree(random_seed=None)

Returns a random spanning tree of the graph, without considering the weights of the edges. Vertices are taken in a random order, and each of them is attached to a random neighbor already in the tree. It is used by RandomMaze to generate mazes, in which all edges have the same weight when the walls are placed. In such a graph, any spanning tree is also a minimum spanning tree. To obtain a spanning tree of minimal weight in a weighted graph, see minimum_spanning_tree.

Parameters:

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

Return type:

Graph

Returns:

Graph representing the random spanning tree.

Raises:

PyRatException – If the graph is empty, not undirected (all edges symmetric), or not connected.

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