from typing import Any, Optional, List, Dict, Callable


class Vertex:
    def __init__(self, data, index):
        self.data = data  # wartosc
        self.index = index # index


# przechowuje krawedzie grafu
class Edge:
    source: Vertex  # od krawedzi
    destination: Vertex  # do krawedzi
    weight: Optional[float]  # opcjonalna waga krawedzi

    def __init__(self, source, destination, weight):
        self.source = source
        self.destination = destination
        self.weight = weight


class Graph:
    adjacencies: Dict[Vertex, List[Edge]]

    def __init__(self) -> None:
        self.adjacencies = {}

    def create_vertex(self, data: Any) -> Vertex:
        temp: Vertex = Vertex(data, len(self.adjacencies))
        self.adjacencies[temp] = []
        return temp

    def add_undirected_edge(self, source: Vertex, destination: Vertex, weight: Optional[float] = None) -> None:
        new_edge = Edge(source, destination, weight)
        new_edge_revers = Edge(destination, source, weight)
        self.adjacencies[source].append(new_edge)
        self.adjacencies[destination].append(new_edge_revers)

    def add_directed_edge(self, source, destination, weight=None):
        new_edge = Edge(source, destination, weight)
        self.adjacencies[source].append(new_edge)

    def print(self):
        for vertex_edges in self.adjacencies.values():
            source = list(self.adjacencies.keys())[list(self.adjacencies.values()).index(vertex_edges)]
            print(f"{source.data} -> ", end='')
            print("[", end='')
            for edge in vertex_edges:
                print(f"{edge.destination.data}, ", end='')
            print("]")
def dead_path(g: Graph, cross_id: Any, visit: Callable[[Any], None]) -> Optional[List[Vertex]]:
    vertex = None
    for elem in list(graph.adjacencies.keys()):
        if elem.data == cross_id:
            vertex = elem
    path: List[List[Vertex]] = [[]]
    road: List[Vertex] = []
    recursion(g, path, vertex, vertex, [], road, visit)
    return path


def recursion(g: Graph, path, begin, v: Vertex, visited: List[Vertex], road, visit: Callable[[Any], None]) -> None:
    visited.append(v)
    if g.adjacencies[v]:
        road.append(v)
    for elem in g.adjacencies[v]:
        if elem.destination == begin and not path[0]:
            path[0] = road.copy()
            path[0].append(begin)
        if elem.destination not in visited:
            recursion(g, path, begin, elem.destination, visited, road, visit)


def visit(node: Vertex):
    print(node.data)


if __name__ == '__main__':

    graph = Graph()
    a = graph.create_vertex("A")
    b = graph.create_vertex("B")
    c = graph.create_vertex("C")

    d = graph.create_vertex("D")
    e = graph.create_vertex("E")

    graph.add_directed_edge(a, b)
    graph.add_directed_edge(b, c)
    graph.add_directed_edge(c, d)
    graph.add_directed_edge(d, e)
    graph.add_directed_edge(e, a)
    graph.print()

    path = dead_path(graph, "A", visit)
    for elem in path[0]:
        print(elem.data)