class Graph: def __init__(self): self.adjacent: dict[int, set] = {} self.vertex_attribute: dict[int, dict] = {} def add_vertex(self, vertex): if vertex not in self.adjacent: if not isinstance(vertex, int): raise TypeError(f"Argument {vertex} is not a valid vertex") self.adjacent[vertex] = set() pass def add_edge(self, u, v): self.add_vertex(u) self.add_vertex(v) v_neighbor = self.adjacent[v] if u not in v_neighbor: v_neighbor.add(u) u_neighbor = self.adjacent[u] if v not in u_neighbor: u_neighbor.add(v) pass def merge_attribute(self, vertex: int, properties: dict): """ merge a dict of attribute to a vertex. Usage example: ``` g = Graph(); g.add_vertex(1); g.mergeAttribute(1, {'color': 0}); ``` :param vertex: :param properties: :return: self """ if vertex not in self.adjacent: raise ValueError(f"Graph does not include vertex {vertex}") old_attributes = self.vertex_attribute[vertex] self.vertex_attribute[vertex] = old_attributes | properties return self pass def get_attribute(self, vertex): if vertex in self.adjacent: return self.vertex_attribute[vertex] else: raise ValueError(f"Graph does not include vertex {vertex}") pass def vertices(self): return self.adjacent.keys() def for_each_vertices(self, action): for v in self.vertices(): action(v) def adjacent_of(self, vertex): if vertex not in self.adjacent: raise ValueError(f"Graph does not include vertex {vertex}") return self.adjacent.get(vertex) def for_each_edges(self, action): visited_edges: dict[int, set] = {} for start in self.vertices(): for end in self.adjacent_of(start): (first, second) = (start, end) if (start > end) else (end, start) if first in visited_edges: visited_adjacent = visited_edges.get(first) if second not in visited_adjacent: visited_adjacent.add(second) action(start, end) else: adjacent = set() visited_edges[first] = adjacent adjacent.add(second) action(start, end) def __repr__(self): text = "" sorted_key = sorted(self.adjacent.keys()) last_key = sorted_key.pop() def adjacent_fn(vertex): return "[" + ", ".join( [str(v) for v in self.adjacent[vertex]] ) + "]" for key in sorted_key: text += f"{key} → {adjacent_fn(key)}\n" text += f"{last_key} → {adjacent_fn(last_key)}" return text