60 lines
1.6 KiB
Python
60 lines
1.6 KiB
Python
type Graph[T] = dict[T, list[T]]
|
|
|
|
|
|
def is_bidirected[T](graph: Graph[T]) -> bool:
|
|
for a, vertecies in graph.items():
|
|
for b in vertecies:
|
|
if a not in graph[b]:
|
|
return False
|
|
return True
|
|
|
|
|
|
def depth_first_search[T](graph: Graph[T], node: T,
|
|
_visited: set[T] = None) -> set[T]:
|
|
if _visited is None:
|
|
_visited = set()
|
|
if node in _visited:
|
|
return set()
|
|
_visited.add(node)
|
|
for neighbours in graph[node]:
|
|
depth_first_search(graph, neighbours, _visited)
|
|
return _visited
|
|
|
|
|
|
def all_edges[T](graph: Graph[T]) -> set[tuple[T, T]]:
|
|
all_vertecies = set()
|
|
for a, vertecies in graph.items():
|
|
for b in vertecies:
|
|
all_vertecies.add((a, b))
|
|
return all_vertecies
|
|
|
|
|
|
def alt_all_edges[T](graph: Graph[T]) -> set[tuple[T, T]]:
|
|
return {(a, b)
|
|
for a, vertecies in graph.items()
|
|
for b in vertecies}
|
|
|
|
|
|
if __name__ == '__main__':
|
|
my_graph: Graph[str] = {
|
|
'A': ['B', 'D'],
|
|
'B': ['A', 'C'],
|
|
'C': ['B', 'D'],
|
|
'D': ['C', 'A'],
|
|
}
|
|
assert all_edges(my_graph) == {('A', 'B'), ('A', 'D'), ('B', 'A'),
|
|
('B', 'C'), ('C', 'B'), ('C', 'D'),
|
|
('D', 'C'), ('D', 'A')}
|
|
assert all_edges(my_graph) == alt_all_edges(my_graph)
|
|
assert is_bidirected(my_graph)
|
|
assert not is_bidirected({'A': ['B', 'C'], 'B': [
|
|
'C'], 'C': ['A', 'B']})
|
|
my_graph = {
|
|
0: [1, 2, 3],
|
|
1: [0],
|
|
2: [3, 4, 0],
|
|
3: [0, 2],
|
|
4: [2],
|
|
5: [],
|
|
}
|
|
print(depth_first_search(my_graph, 5)) |