from typing import Any, Callable
|
|
|
class Graph:
|
"""
|
represents an undirected and unweighted Graph
|
"""
|
def __init__(self):
|
self._adjacent: dict[int, set] = {}
|
self._vertex_attribute: dict[int, dict] = {}
|
|
def add_vertex(self, vertex:int):
|
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()
|
self._vertex_attribute[vertex] = {}
|
pass
|
|
def add_edge(self, u: int, v: int):
|
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 add_edges(self, u: int, adjacent: list[int]):
|
for v in adjacent:
|
self.add_edge(u, 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: int):
|
if vertex in self._adjacent:
|
return self._vertex_attribute[vertex]
|
else:
|
raise ValueError(f"Graph does not include vertex {vertex}")
|
pass
|
|
def vertices(self):
|
"""
|
returns the set of vertices in not defined order.
|
:return:
|
"""
|
return self._adjacent.keys()
|
|
def for_each_vertices(self, action: Callable[[int], Any]):
|
"""
|
iterates over all vertices in this graph in ascending order.
|
:param action:
|
:return:
|
"""
|
for v in sorted( self.vertices() ):
|
action(v)
|
|
def adjacent_of(self, vertex: int):
|
if vertex not in self._adjacent:
|
raise ValueError(f"Graph does not include vertex {vertex}")
|
return sorted( self._adjacent[vertex] )
|
|
def for_each_edges(self, action: Callable[[int, int], Any]):
|
"""
|
iterates over all edges of the graph, executes the action on each edge.
|
:param action: a binary function, its parameters are start and end vertices of the visited edges
|
"""
|
visited_edges: dict[int, set] = {}
|
for start in sorted( 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)
|
visited_adjacent = visited_edges[first]
|
if second not in visited_adjacent:
|
visited_adjacent.add(second)
|
action(start, end)
|
else:
|
adjacent: set[int] = 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
|
|
def to_dot(self) -> str:
|
pass
|
|
def greedy_color(self, vertex_order:[int]) -> dict[int,int]:
|
pass
|
|
|
def first_available(color_list:[]) -> int:
|
color_set = set(color_list)
|
count = 0
|
while True:
|
if count not in color_set:
|
return count
|
count += 1# count = count + 1
|
pass
|
|
def greedy_color(g:Graph, vertex_order:[int]) -> dict[int,int]:
|
color:dict[int,int] = {}
|
for vertex in vertex_order:
|
used_neighbor_colors = []
|
for nbr in g.adjacent_of(vertex):
|
if nbr in color:
|
used_neighbor_colors.append(color[nbr])
|
color[vertex] = first_available(used_neighbor_colors)
|
pass
|
return color
|
