Spaces:
Runtime error
Runtime error
File size: 3,234 Bytes
4919e19 1294291 4919e19 1294291 4919e19 1294291 4919e19 1294291 4919e19 be83ac2 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 | class Graph:
def __init__(self, num_vertices, directed=True):
self.num_vertices = num_vertices
self.directed = directed
# Using float('inf') for no connection as requested
self.adj_matrix = [[float('inf')] * num_vertices for _ in range(num_vertices)]
self.adj_list = {i: [] for i in range(num_vertices)}
def add_edge(self, u, v, weight):
if 0 <= u < self.num_vertices and 0 <= v < self.num_vertices:
# Directed edge logic
self.adj_list[u].append((v, weight))
self.adj_matrix[u][v] = weight
if not self.directed:
self.adj_list[v].append((u, weight))
self.adj_matrix[v][u] = weight
else:
raise ValueError(f"Vertex index out of bounds: {u}, {v}")
def to_adjacency_matrix(self):
"""
Returns a 2D list (matrix) of size V x V.
matrix[u][v] = weight if edge exists.
matrix[u][v] = float('inf') if no edge exists.
matrix[u][u] = 0 (distance to self).
"""
# Create a deep copy to avoid modifying internal state if needed,
# or just return internal state if we maintain it strictly.
# But user requested "matrix[u][u] = 0". Our internal init uses float('inf').
# So we should probably update internal or return a modified copy.
# Let's return a generated one if we want to be safe, or update internal.
# Updating internal is better for consistency if we use it.
# But wait, internal initialized with inf.
# Let's just fix diagonals in internal if they are inf.
for i in range(self.num_vertices):
self.adj_matrix[i][i] = 0
return self.adj_matrix
def from_adjacency_matrix(self, matrix):
"""
Clears the current graph.
Populates the adjacency list based on the matrix values.
"""
self.num_vertices = len(matrix)
self.adj_matrix = matrix
self.adj_list = {i: [] for i in range(self.num_vertices)}
for i in range(self.num_vertices):
for j in range(self.num_vertices):
w = matrix[i][j]
if i != j and w != float('inf'):
self.adj_list[i].append((j, w))
def get_matrix(self):
return self.adj_matrix
def get_list(self):
return self.adj_list
def check_connectivity(self, start_node_id):
"""
Checks if all nodes are reachable from start_node_id using BFS.
Returns: (is_connected: bool, unreachable_nodes: list)
"""
if start_node_id < 0 or start_node_id >= self.num_vertices:
return False, []
visited = set()
queue = [start_node_id]
visited.add(start_node_id)
while queue:
u = queue.pop(0)
for v, weight in self.adj_list[u]:
if v not in visited:
visited.add(v)
queue.append(v)
all_nodes = set(range(self.num_vertices))
unreachable = list(all_nodes - visited)
unreachable.sort()
return (len(unreachable) == 0), unreachable
|