Da meine Freundin aber grad gestern Premiere gekriegt hat, hab ich irgendwann nicht mehr antworten können um nicht die neue Staffel von $lieblingsserie zu verpassen
Für die Newbies: Ihr braucht diesen Code nicht um Abhängigkeiten von normalen python-modulen o.Ä. aufzulösen, das macht python selbstverständlich alles selbst!
So jetzt aber der Code:
Code: Alles auswählen
#!/usr/bin/env python
# -*- coding: iso-8859-1 -*-
# Folgende Zeile ist nur für python <2.4 nötig
from sets import Set as set
# Das liest sich so:
# - Für A muss B bereits vorhanden sein
# - Für B müssen D und I vorhanden sein
# usw...
d = {
"A": ["B"],
"B": ["D", "I"],
"C": ["B"],
"D": ["I"],
"E": ["B"],
"F": ["I"],
"G": ["E"],
"H": ["E", "G"],
"I": [],
}
def calc_deps(d):
# fullfilled sind die Abhängigkeiten, die schon erfüllt sind
fullfilled = set()
while len(d):
for k, v in d.items():
# Sind die Abhängigkeiten für k schon erfüllt?
if set(v) <= fullfilled:
yield k
fullfilled.add(k)
del d[k]
break
else:
raise StandardError("Zirkuläre Abhängigkeit")
for x in calc_deps(d):
print x
Wenn ich das richtig sehe, braucht der Algo hier jetzt O(n^2) * O(subset-operation).
Wenn jemand was schnelleres findet, immer her damit!
edit:
Diese Funktion kann man z.B. auch benutzen, um herauszufinden, in welcher Reihenfolge man Klassen definieren muss, wenn diese untereinander eine unüberschaubare Vererbungsstruktur haben!