##########################################################################################
########################################## INFO ##########################################
##########################################################################################
# This file is part of the PyRat library.
# It is meant to be used as a library, and not to be executed directly.
# Please import necessary elements using the following syntax:
# from pyrat import <element_name>
"""
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.
"""
##########################################################################################
######################################### IMPORTS ########################################
##########################################################################################
# External imports
from collections.abc import Hashable
import heapq
import math
import random
import sys
# Numpy is an optional dependency
try:
import numpy
except ImportError:
pass
# Torch is an optional dependency
try:
import torch
except ImportError:
pass
# PyRat imports
from pyrat.src.game.exceptions import PyRatException
##########################################################################################
######################################### CLASSES ########################################
##########################################################################################
[docs]
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.
"""
##################################################################################
# CONSTRUCTOR #
##################################################################################
[docs]
def __init__ (self) -> None:
"""
Initializes a new instance of the class.
This constructor initializes the internal adjacency dictionary.
"""
# Private attributes
self.__adjacency = {}
##################################################################################
# DUNDER METHODS #
##################################################################################
def __str__ (self) -> str:
"""
Returns a string representation of the object.
Returns:
String representation of the object.
"""
# Create the string
string = "Graph object:\n"
string += "| Vertices: {}\n".format(self.get_vertices())
string += "| Adjacency matrix:\n"
for vertex_1, vertex_2 in self.get_edges():
weight = self.get_weight(vertex_1, vertex_2)
symmetric = self.edge_is_symmetric(vertex_1, vertex_2)
string += "| | {} {} ({}) --> {}\n".format(vertex_1, "<--" if symmetric else "---", weight, vertex_2)
return string.strip()
##################################################################################
# PUBLIC METHODS #
##################################################################################
[docs]
def add_edge ( self,
vertex_1: Hashable,
vertex_2: Hashable,
weight: float | int = 1,
symmetric: bool = False
) -> None:
"""
Adds an edge to the graph.
Args:
vertex_1: First vertex.
vertex_2: Second vertex.
weight: Weight of the edge. Defaults to 1.
symmetric: Whether the edge is symmetric (undirected). Defaults to False.
"""
# Check validity
if not isinstance(vertex_1, Hashable):
raise PyRatException(f"Argument 'vertex_1' must be hashable, got a value of type {type(vertex_1).__name__}")
if (isinstance(vertex_1, tuple) and not _is_hashable(vertex_1)):
raise PyRatException(f"Argument 'vertex_1' must be hashable, got {vertex_1!r}, a tuple containing an unhashable element")
if not isinstance(vertex_2, Hashable):
raise PyRatException(f"Argument 'vertex_2' must be hashable, got a value of type {type(vertex_2).__name__}")
if (isinstance(vertex_2, tuple) and not _is_hashable(vertex_2)):
raise PyRatException(f"Argument 'vertex_2' must be hashable, got {vertex_2!r}, a tuple containing an unhashable element")
if not (isinstance(weight, (float, int)) and not isinstance(weight, bool)):
raise PyRatException(f"Argument 'weight' must be a real number, got {weight!r} of type {type(weight).__name__}")
if (isinstance(weight, float) and math.isnan(weight)):
raise PyRatException(f"Argument 'weight' must be a real number, got {weight!r}")
if not isinstance(symmetric, bool):
raise PyRatException(f"Argument 'symmetric' must be a boolean, got {symmetric!r} of type {type(symmetric).__name__}")
if vertex_1 not in self.__adjacency:
raise PyRatException(f"Cannot add an edge between {vertex_1!r} and {vertex_2!r}: vertex {vertex_1!r} is not in the graph (add it first with add_vertex)")
if vertex_2 not in self.__adjacency:
raise PyRatException(f"Cannot add an edge between {vertex_1!r} and {vertex_2!r}: vertex {vertex_2!r} is not in the graph (add it first with add_vertex)")
if self.has_edge(vertex_1, vertex_2):
raise PyRatException(f"Cannot add an edge from {vertex_1!r} to {vertex_2!r}: this edge already exists (remove it first with remove_edge to change its weight)")
if (symmetric and self.has_edge(vertex_2, vertex_1)):
raise PyRatException(f"Cannot add a symmetric edge between {vertex_1!r} and {vertex_2!r}: the reverse edge from {vertex_2!r} to {vertex_1!r} already exists")
# Add edge to the adjacency dictionary
self.__adjacency[vertex_1][vertex_2] = weight
if symmetric:
self.__adjacency[vertex_2][vertex_1] = weight
##################################################################################
[docs]
def add_vertex ( self,
vertex: Hashable
) -> None:
"""
Adds a vertex to the graph.
Args:
vertex: The vertex to add.
"""
# Check validity
if not isinstance(vertex, Hashable):
raise PyRatException(f"Argument 'vertex' must be hashable, got a value of type {type(vertex).__name__}")
if (isinstance(vertex, tuple) and not _is_hashable(vertex)):
raise PyRatException(f"Argument 'vertex' must be hashable, got {vertex!r}, a tuple containing an unhashable element")
if vertex in self.__adjacency:
raise PyRatException(f"Cannot add vertex {vertex!r}: it is already in the graph")
# Add vertex to the adjacency matrix
self.__adjacency[vertex] = {}
##################################################################################
[docs]
def as_dict (self) -> dict[Hashable, dict[Hashable, float | int]]:
"""
Returns a dictionary representing the adjacency matrix.
Returns:
Dictionary representing the adjacency matrix.
"""
# Make a copy of the adjacency matrix
adjacency_dict = self.__adjacency.copy()
return adjacency_dict
##################################################################################
[docs]
def as_numpy_ndarray (self) -> object:
"""
Returns a ``numpy.ndarray`` representing the graph.
Entries are given in order in which vertices appear in the adjacency dictionary.
Returns:
A ``numpy.ndarray`` representing the adjacency matrix (return type is ``object`` to allow ``numpy`` to be optional).
"""
# Check validity
if "numpy" not in globals():
raise PyRatException("Cannot convert the graph to a numpy.ndarray: numpy is not installed (install it with 'pip install numpy')")
if not all(not isinstance(weight, float) or weight.is_integer() for neighbors in self.__adjacency.values() for weight in neighbors.values()):
raise PyRatException(f"Cannot convert the graph to a numpy.ndarray: the weight of the edge {next(f'from {vertex_1!r} to {vertex_2!r} is {weight!r}' for vertex_1, neighbors in self.__adjacency.items() for vertex_2, weight in neighbors.items() if isinstance(weight, float) and not weight.is_integer())}, which cannot be stored in a matrix of integers")
# Create the adjacency matrix
adjacency_matrix = numpy.zeros((self.nb_vertices(), self.nb_vertices()), dtype=int)
for i, vertex_1 in enumerate(self.__adjacency):
for j, vertex_2 in enumerate(self.__adjacency):
if self.has_edge(vertex_1, vertex_2):
adjacency_matrix[i, j] = self.get_weight(vertex_1, vertex_2)
return adjacency_matrix
##################################################################################
[docs]
def as_torch_tensor (self) -> object:
"""
Returns a ``torch.tensor`` representing the graph.
Entries are given in order in which vertices appear in the adjacency dictionary
Returns:
A ``torch.tensor`` representing the adjacency matrix (return type is ``object`` to allow ``torch`` to be optional).
"""
# Check validity
if "torch" not in globals():
raise PyRatException("Cannot convert the graph to a torch.Tensor: torch is not installed (install it with 'pip install torch')")
if not all(not isinstance(weight, float) or weight.is_integer() for neighbors in self.__adjacency.values() for weight in neighbors.values()):
raise PyRatException(f"Cannot convert the graph to a torch.Tensor: the weight of the edge {next(f'from {vertex_1!r} to {vertex_2!r} is {weight!r}' for vertex_1, neighbors in self.__adjacency.items() for vertex_2, weight in neighbors.items() if isinstance(weight, float) and not weight.is_integer())}, which cannot be stored in a matrix of integers")
# Create the adjacency matrix
adjacency_matrix = torch.zeros((self.nb_vertices(), self.nb_vertices()), dtype=int)
for i, vertex_1 in enumerate(self.__adjacency):
for j, vertex_2 in enumerate(self.__adjacency):
if self.has_edge(vertex_1, vertex_2):
adjacency_matrix[i, j] = self.get_weight(vertex_1, vertex_2)
return adjacency_matrix
##################################################################################
[docs]
def edge_is_symmetric ( self,
vertex_1: Hashable,
vertex_2: Hashable,
) -> bool:
"""
Checks whether an edge is symmetric.
Args:
vertex_1: First vertex.
vertex_2: Second vertex.
Returns:
Whether the edge is symmetric.
"""
# Check validity
if not isinstance(vertex_1, Hashable):
raise PyRatException(f"Argument 'vertex_1' must be hashable, got a value of type {type(vertex_1).__name__}")
if (isinstance(vertex_1, tuple) and not _is_hashable(vertex_1)):
raise PyRatException(f"Argument 'vertex_1' must be hashable, got {vertex_1!r}, a tuple containing an unhashable element")
if not isinstance(vertex_2, Hashable):
raise PyRatException(f"Argument 'vertex_2' must be hashable, got a value of type {type(vertex_2).__name__}")
if (isinstance(vertex_2, tuple) and not _is_hashable(vertex_2)):
raise PyRatException(f"Argument 'vertex_2' must be hashable, got {vertex_2!r}, a tuple containing an unhashable element")
if vertex_1 not in self.__adjacency:
raise PyRatException(f"Cannot check whether the edge from {vertex_1!r} to {vertex_2!r} is symmetric: vertex {vertex_1!r} is not in the graph")
if vertex_2 not in self.__adjacency:
raise PyRatException(f"Cannot check whether the edge from {vertex_1!r} to {vertex_2!r} is symmetric: vertex {vertex_2!r} is not in the graph")
if not self.has_edge(vertex_1, vertex_2):
raise PyRatException(f"Cannot check whether the edge from {vertex_1!r} to {vertex_2!r} is symmetric: this edge does not exist")
# Check whether the edge is symmetric
symmetric = self.has_edge(vertex_2, vertex_1)
return symmetric
##################################################################################
[docs]
def get_edges (self) -> list[tuple[Hashable, Hashable]]:
"""
Returns the list of edges in the graph.
Symmetric edges are counted once.
Returns:
List of edges in the graph, as tuples ``(vertex_1, vertex_2)``.
"""
# Get the list of edges
edge_list = []
for vertex_1 in self.get_vertices():
for vertex_2 in self.get_neighbors(vertex_1):
if (vertex_2, vertex_1) not in edge_list:
edge_list.append((vertex_1, vertex_2))
return edge_list
##################################################################################
[docs]
def get_neighbors ( self,
vertex: Hashable
) -> list[Hashable]:
"""
Returns the list of neighbors of a vertex.
Args:
vertex: Vertex of which to get neighbors.
Returns:
List of neighbors of the vertex.
"""
# Check validity
if not isinstance(vertex, Hashable):
raise PyRatException(f"Argument 'vertex' must be hashable, got a value of type {type(vertex).__name__}")
if (isinstance(vertex, tuple) and not _is_hashable(vertex)):
raise PyRatException(f"Argument 'vertex' must be hashable, got {vertex!r}, a tuple containing an unhashable element")
if vertex not in self.__adjacency:
raise PyRatException(f"Cannot get the neighbors of vertex {vertex!r}: it is not in the graph")
# Get neighbors
neighbors = list(self.__adjacency[vertex].keys())
return neighbors
##################################################################################
[docs]
def get_vertices (self) -> list[Hashable]:
"""
Returns the list of vertices in the graph.
Returns:
List of vertices in the graph.
"""
# Get the list of vertices
vertices = list(self.__adjacency.keys())
return vertices
##################################################################################
[docs]
def get_weight ( self,
vertex_1: Hashable,
vertex_2: Hashable
) -> float | int:
"""
Returns the weight of an edge.
Args:
vertex_1: First vertex.
vertex_2: Second vertex.
Returns:
Weight of the edge.
"""
# Check validity
if not isinstance(vertex_1, Hashable):
raise PyRatException(f"Argument 'vertex_1' must be hashable, got a value of type {type(vertex_1).__name__}")
if (isinstance(vertex_1, tuple) and not _is_hashable(vertex_1)):
raise PyRatException(f"Argument 'vertex_1' must be hashable, got {vertex_1!r}, a tuple containing an unhashable element")
if not isinstance(vertex_2, Hashable):
raise PyRatException(f"Argument 'vertex_2' must be hashable, got a value of type {type(vertex_2).__name__}")
if (isinstance(vertex_2, tuple) and not _is_hashable(vertex_2)):
raise PyRatException(f"Argument 'vertex_2' must be hashable, got {vertex_2!r}, a tuple containing an unhashable element")
if vertex_1 not in self.__adjacency:
raise PyRatException(f"Cannot get the weight of the edge from {vertex_1!r} to {vertex_2!r}: vertex {vertex_1!r} is not in the graph")
if vertex_2 not in self.__adjacency:
raise PyRatException(f"Cannot get the weight of the edge from {vertex_1!r} to {vertex_2!r}: vertex {vertex_2!r} is not in the graph")
if not self.has_edge(vertex_1, vertex_2):
raise PyRatException(f"Cannot get the weight of the edge from {vertex_1!r} to {vertex_2!r}: this edge does not exist (check it first with has_edge)")
# Get weight
weight = self.__adjacency[vertex_1][vertex_2]
return weight
##################################################################################
[docs]
def has_edge ( self,
vertex_1: Hashable,
vertex_2: Hashable,
) -> bool:
"""
Checks whether an edge exists between two vertices.
Args:
vertex_1: First vertex.
vertex_2: Second vertex.
Returns:
Whether an edge exists between the two vertices.
"""
# Check validity
if not isinstance(vertex_1, Hashable):
raise PyRatException(f"Argument 'vertex_1' must be hashable, got a value of type {type(vertex_1).__name__}")
if (isinstance(vertex_1, tuple) and not _is_hashable(vertex_1)):
raise PyRatException(f"Argument 'vertex_1' must be hashable, got {vertex_1!r}, a tuple containing an unhashable element")
if not isinstance(vertex_2, Hashable):
raise PyRatException(f"Argument 'vertex_2' must be hashable, got a value of type {type(vertex_2).__name__}")
if (isinstance(vertex_2, tuple) and not _is_hashable(vertex_2)):
raise PyRatException(f"Argument 'vertex_2' must be hashable, got {vertex_2!r}, a tuple containing an unhashable element")
if vertex_1 not in self.__adjacency:
raise PyRatException(f"Cannot check for an edge from {vertex_1!r} to {vertex_2!r}: vertex {vertex_1!r} is not in the graph")
if vertex_2 not in self.__adjacency:
raise PyRatException(f"Cannot check for an edge from {vertex_1!r} to {vertex_2!r}: vertex {vertex_2!r} is not in the graph")
# Check whether the edge exists
edge_exists = vertex_2 in self.get_neighbors(vertex_1)
return edge_exists
##################################################################################
[docs]
def is_connected (self) -> bool:
"""
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.
Returns:
``True`` if the graph is connected, ``False`` otherwise.
"""
# Check validity
if not (self.nb_vertices() > 0):
raise PyRatException("Cannot check whether the graph is connected: the graph has no vertex")
# Neighbors of each vertex when edge directions are ignored
vertices = list(self.get_vertices())
undirected_neighbors = {vertex: set() for vertex in vertices}
for vertex in vertices:
for neighbor in self.get_neighbors(vertex):
undirected_neighbors[vertex].add(neighbor)
undirected_neighbors[neighbor].add(vertex)
# Create a list of visited vertices
visited = {vertex: False for vertex in vertices}
visited[vertices[0]] = True
stack = [vertices[0]]
# Depth-first search
while stack:
vertex = stack.pop()
for neighbor in undirected_neighbors[vertex]:
if not visited[neighbor]:
visited[neighbor] = True
stack.append(neighbor)
# Check if all vertices have been visited
connected = all(visited.values())
return connected
##################################################################################
[docs]
def minimum_spanning_tree ( self,
random_seed: int | None = None
) -> "Graph":
"""
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``.
Args:
random_seed: Seed for the random number generator.
Returns:
Graph representing the minimum spanning tree.
Raises:
PyRatException: If the graph is empty or not connected.
"""
# Check validity
if not (random_seed is None or isinstance(random_seed, int)):
raise PyRatException(f"Argument 'random_seed' must be an integer or None, got {random_seed!r} of type {type(random_seed).__name__}")
if not (random_seed is None or 0 <= random_seed < sys.maxsize):
raise PyRatException(f"Argument 'random_seed' must be non-negative and lower than sys.maxsize, got {random_seed!r}")
if self.nb_vertices() == 0:
raise PyRatException("Cannot compute a minimum spanning tree: the graph has no vertex")
# Initialize a random number generator
rng = random.Random(random_seed)
# List the edges incident to each vertex, whatever their direction, as pairs (other end, edge in its original direction)
incident = {vertex: [] for vertex in self.get_vertices()}
for vertex_1 in self.get_vertices():
for vertex_2 in self.get_neighbors(vertex_1):
incident[vertex_1].append((vertex_2, (vertex_1, vertex_2)))
incident[vertex_2].append((vertex_1, (vertex_1, vertex_2)))
# Create the minimum spanning tree, initialized with a random vertex
mst = Graph()
vertex = rng.choice(self.get_vertices())
mst.add_vertex(vertex)
# Edges leaving the tree, sorted by weight, then by a random number to break ties (and a counter, as vertices may not be comparable)
candidates = []
counter = 0
for other_end, edge in incident[vertex]:
heapq.heappush(candidates, (self.get_weight(*edge), rng.random(), counter, other_end, edge))
counter += 1
# Add the lightest edge leaving the tree until all vertices are included
while mst.nb_vertices() < self.nb_vertices():
# If no edge leaves the tree, some vertices cannot be reached
if not candidates:
raise PyRatException(f"Cannot compute a minimum spanning tree: the graph is not connected (only {mst.nb_vertices()} of its {self.nb_vertices()} vertices could be linked to the tree, even ignoring edge directions)")
# Add the new vertex and the edge leading to it
weight, _, _, vertex, edge = heapq.heappop(candidates)
if vertex in mst.get_vertices():
continue
mst.add_vertex(vertex)
symmetric = self.edge_is_symmetric(*edge) and self.get_weight(edge[1], edge[0]) == weight
mst.add_edge(edge[0], edge[1], weight, symmetric)
# The edges of the new vertex can now leave the tree
for other_end, next_edge in incident[vertex]:
if other_end not in mst.get_vertices():
heapq.heappush(candidates, (self.get_weight(*next_edge), rng.random(), counter, other_end, next_edge))
counter += 1
# Return the minimum spanning tree
return mst
##################################################################################
[docs]
def nb_edges (self) -> int:
"""
Returns the number of edges in the graph.
Symmetric edges are counted once.
Returns:
Number of edges in the graph.
"""
# Get the number of edges
nb = len(self.get_edges())
return nb
##################################################################################
[docs]
def nb_vertices (self) -> int:
"""
Returns the number of vertices in the graph.
Returns:
Number of vertices in the graph.
"""
# Get the number of vertices
nb = len(self.__adjacency)
return nb
##################################################################################
[docs]
def random_spanning_tree ( self,
random_seed: int | None = None
) -> "Graph":
"""
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``.
Args:
random_seed: Seed for the random number generator.
Returns:
Graph representing the random spanning tree.
Raises:
PyRatException: If the graph is empty, not undirected (all edges symmetric), or not connected.
"""
# Check validity
if not (random_seed is None or isinstance(random_seed, int)):
raise PyRatException(f"Argument 'random_seed' must be an integer or None, got {random_seed!r} of type {type(random_seed).__name__}")
if not (random_seed is None or 0 <= random_seed < sys.maxsize):
raise PyRatException(f"Argument 'random_seed' must be non-negative and lower than sys.maxsize, got {random_seed!r}")
if self.nb_vertices() == 0:
raise PyRatException("Cannot compute a random spanning tree: the graph has no vertex")
directed_edge = next(((vertex, neighbor) for vertex in self.get_vertices() for neighbor in self.get_neighbors(vertex) if not self.edge_is_symmetric(vertex, neighbor)), None)
if directed_edge is not None:
raise PyRatException(f"Cannot compute a random spanning tree: the graph must be undirected, got edge {directed_edge[0]!r} -> {directed_edge[1]!r} without the reverse edge (use minimum_spanning_tree for directed graphs)")
if not self.is_connected():
raise PyRatException("Cannot compute a random spanning tree: the graph is not connected (see is_connected)")
# Initialize a random number generator
rng = random.Random(random_seed)
# Shuffle vertices
vertices_to_add = self.get_vertices()
rng.shuffle(vertices_to_add)
# Create the spanning tree, initialized with a random vertex
tree = Graph()
vertex = vertices_to_add.pop(0)
tree.add_vertex(vertex)
# Add vertices until all are included
while vertices_to_add:
vertex = vertices_to_add.pop(0)
neighbors = self.get_neighbors(vertex)
rng.shuffle(neighbors)
neighbors_in_tree = [neighbor for neighbor in neighbors if neighbor in tree.get_vertices()]
if neighbors_in_tree:
neighbor = neighbors_in_tree[0]
symmetric = self.edge_is_symmetric(vertex, neighbor)
weight = self.get_weight(neighbor, vertex)
tree.add_vertex(vertex)
tree.add_edge(vertex, neighbor, weight, symmetric)
else:
vertices_to_add.append(vertex)
# Return the random spanning tree
return tree
##################################################################################
[docs]
def remove_edge ( self,
vertex_1: Hashable,
vertex_2: Hashable,
symmetric: bool = False
) -> None:
"""
Removes an edge from the graph.
Args:
vertex_1: First vertex.
vertex_2: Second vertex.
symmetric: Whether to also delete the symmetric edge. Defaults to False.
"""
# Check validity
if not isinstance(vertex_1, Hashable):
raise PyRatException(f"Argument 'vertex_1' must be hashable, got a value of type {type(vertex_1).__name__}")
if (isinstance(vertex_1, tuple) and not _is_hashable(vertex_1)):
raise PyRatException(f"Argument 'vertex_1' must be hashable, got {vertex_1!r}, a tuple containing an unhashable element")
if not isinstance(vertex_2, Hashable):
raise PyRatException(f"Argument 'vertex_2' must be hashable, got a value of type {type(vertex_2).__name__}")
if (isinstance(vertex_2, tuple) and not _is_hashable(vertex_2)):
raise PyRatException(f"Argument 'vertex_2' must be hashable, got {vertex_2!r}, a tuple containing an unhashable element")
if not isinstance(symmetric, bool):
raise PyRatException(f"Argument 'symmetric' must be a boolean, got {symmetric!r} of type {type(symmetric).__name__}")
if vertex_1 not in self.__adjacency:
raise PyRatException(f"Cannot remove the edge from {vertex_1!r} to {vertex_2!r}: vertex {vertex_1!r} is not in the graph")
if vertex_2 not in self.__adjacency:
raise PyRatException(f"Cannot remove the edge from {vertex_1!r} to {vertex_2!r}: vertex {vertex_2!r} is not in the graph")
if not self.has_edge(vertex_1, vertex_2):
raise PyRatException(f"Cannot remove the edge from {vertex_1!r} to {vertex_2!r}: this edge does not exist")
if not ((not symmetric) or (symmetric and self.edge_is_symmetric(vertex_1, vertex_2))):
raise PyRatException(f"Cannot remove the edge between {vertex_1!r} and {vertex_2!r} with symmetric=True: the reverse edge from {vertex_2!r} to {vertex_1!r} does not exist (use symmetric=False)")
# Remove edge and symmetric
del self.__adjacency[vertex_1][vertex_2]
if symmetric:
del self.__adjacency[vertex_2][vertex_1]
##################################################################################
[docs]
def remove_vertex ( self,
vertex: Hashable
) -> None:
"""
Removes a vertex from the graph.
Also removes all edges connected to this vertex.
Args:
vertex: Vertex to remove.
"""
# Check validity
if not isinstance(vertex, Hashable):
raise PyRatException(f"Argument 'vertex' must be hashable, got a value of type {type(vertex).__name__}")
if (isinstance(vertex, tuple) and not _is_hashable(vertex)):
raise PyRatException(f"Argument 'vertex' must be hashable, got {vertex!r}, a tuple containing an unhashable element")
if vertex not in self.__adjacency:
raise PyRatException(f"Cannot remove vertex {vertex!r}: it is not in the graph")
# Remove the vertex and connections to it
for neighbor in self.__adjacency:
if vertex in self.__adjacency[neighbor]:
del self.__adjacency[neighbor][vertex]
del self.__adjacency[vertex]
##########################################################################################
#################################### PRIVATE FUNCTIONS ###################################
##########################################################################################
def _is_hashable ( value: object
) -> bool:
"""
Checks whether a value can be hashed, i.e., used as a key of a dictionary.
This is more precise than ``isinstance(value, Hashable)``, which accepts tuples containing unhashable elements, such as ``([1],)``.
Args:
value: The value to check.
Returns:
``True`` if the value can be hashed, ``False`` otherwise.
"""
# Try to hash the value
try:
hash(value)
except TypeError:
return False
return True
##########################################################################################
##########################################################################################