from vorlesung.L08_graphen.graph import AdjacencyListGraph

DEPENDENCIES = {
    "main":      ["parser", "codegen"],
    "parser":    ["lexer", "ast"],
    "codegen":   ["ast", "optimizer"],
    "optimizer": ["utils"],
    "ast":       ["utils"],
    "lexer":     [],
    "utils":     [],
}

# --- a) Graph aufbauen -------------------------------------------------------
# Kantendefinition: A -> B bedeutet "A muss vor B gebaut werden" (B hängt von A ab).
# Kanten zeigen also von der Voraussetzung zum Abhängigen – nur so liefert
# die absteigende Sortierung nach leave_map die korrekte Baureihenfolge.
g = AdjacencyListGraph()
for module in DEPENDENCIES:
    g.insert_vertex(module)
for module, deps in DEPENDENCIES.items():
    for dep in deps:
        g.connect(dep, module)   # dep -> module: dep muss vor module gebaut werden

g.graph("BuildDependencies")

# --- b) DFS ausführen --------------------------------------------------------
enter_map, leave_map, pred_map = g.dfs()

print("Zeitmarken (DFS):")
for v in sorted(enter_map, key=lambda v: enter_map[v]):
    print(f"  {v.value:12s}  begin={enter_map[v]:2d}  end={leave_map[v]:2d}")
print()

# --- c) Topologische Sortierung ----------------------------------------------
sorted_vertices = sorted(leave_map, key=lambda v: leave_map[v], reverse=True)
reihenfolge = [v.value for v in sorted_vertices]
print("Topologische Reihenfolge (Build-Reihenfolge):")
print("  " + " -> ".join(reihenfolge))
print()

# Überprüfung: Für jede Abhängigkeit A->B muss A nach B in der Liste kommen.
pos = {name: i for i, name in enumerate(reihenfolge)}
ok = all(pos[dep] < pos[module]
         for module, deps in DEPENDENCIES.items()
         for dep in deps)
print(f"Alle Abhängigkeiten eingehalten: {ok}")
print()

# --- d) Komplexität ----------------------------------------------------------
v_count = len(list(g.all_vertices()))
e_count = sum(len(g.get_adjacent_vertices(v.value)) for v in g.all_vertices())
print(f"|V| = {v_count},  |E| = {e_count}")
# Jeder Knoten wird genau einmal grau (begin) und einmal schwarz (end) => O(|V|)
# Jede Kante wird beim ersten Besuch des Ausgangsknotens genau einmal betrachtet => O(|E|)
# Zusammen: O(|V| + |E|)