56 lines
2.2 KiB
Python
56 lines
2.2 KiB
Python
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|)
|