Jippie... es klappt. Ich hab endlich ein Prograemmchen geschaffen, dass Sachen korrekt nach ihren Abhaengigkeiten sortiert, aehnlich
tsort aus den Coreutils.
[...]
EDIT:Okay, jetzt hab ich auch eine Zirkelabhaengigkeiten-Erkennung (was fuer ein Wort
).
Hier die Sortierfunktion (das uebergebene `d` ist ein Dictionary mit dem Aufbau {Element, [Abhaengigkeiten]} und der Voraussetzung das alle Abhaengigkeiten auch Elemente sind):
Code: Alles auswählen
def sort(d):
out = list()
def look(key):
if key not in out:
if d[key]:
for sub in d[key]: look(sub)
out.append(key)
else: out.append(key)
for key in d.iterkeys(): look(key)
return out
Dazu kommt jetzt noch die Zirkelsuche (gibt die Cycles in einem Dictionary zurueck, oder ein leeres Dictionary, wenn keine aufgetreten sind):
Code: Alles auswählen
def find_cycles(d):
cycles = list()
for key, deps in d.iteritems():
for dep in deps:
if key in d[dep]:
if sorted([key, dep]) not in cycles: cycles.append(sorted([key, dep]))
if cycles:
print "Cycles found!"
for c1, c2 in cycles: print " ", c1, '<->', c2
return cycles
Zu guter Letzt noch die "main-Funktion". Sie nimmt Eingaben im Format "Element Abhaengigkeit Abhaengigkeit2 ..." an und fuettert damit ein Dictionary. Außerdem sorgt sie dafuer, dass alle Abhaengigkeiten auch Elemente (Keys des Dictionary) sind. Elemente (und somit auch Abhaengigkeiten) werden generell in Form einer Zeichenkette verwaltet.
Code: Alles auswählen
if __name__ == '__main__':
out = dict()
try:
while 1:
input = raw_input("> ").split()
if input:
for key in input[1:]:
if not out.has_key(key): out[key] = list()
if not out.has_key(input[0]): out[input[0]] = input[1:]
else: out[input[0]].extend(input[1:])
except EOFError:
print
for item, value in out.iteritems(): print item, value
print
if not find_cycles(out):
print "sorting...\n"
print sort(out)
Ich freu mich ueber jeden Optimierungs- und Verbesserungsvorschlag. Aber bitte habt Nachsicht, da der Code echt nur schnell hingehackt ist.
MfG und all das,
nkoehring
