Rekursiver Sortieralgorithmus

[nkoehring]

Hallo...

ich wuerde gern einen Algorithmus bauen, der mir etwas nach Abhaengigkeiten sortiert.

Das ganze saehe Beispielsweise so aus:

Ich habe eine Reihe von Objekten:

Code: Alles auswählen

obj1, obj2, obj3, obj4 und obj5

.
Jedes dieser Objekte kann von einem oder mehreren anderen Abhaengig sein:

Code: Alles auswählen

obj1 - obj4
obj2 - obj2
obj3 - obj2
obj4 - -
obj5 - obj4, obj2

...wie kann ich nun die Abhaengigkeiten aufloesen... also eine Liste erstellen, in der die Objekte in der richtigen Reihenfolge aufgelistet sind, zB:
[obj4, obj1, obj2, obj3, obj5]

???

Danke schonmal

[BlackJack]

Dein Problem nennt sich Topologische Sortierung.

[Leonidas]

Zwar keine Lösung (sowas müsste man sich etwas länger überlegen, ist aber ein interessantes Problem), dafür ein paar Links:

Partial sort for dependancy graph, interessant schaut auch generating python module dependency graphs aus. Ich denke ein hifreiches Suchwort ist "Dependency Graph" und auch "Topological sorting".

HTH!

[nkoehring]

Ah, vielen Dank fuer die Antworten... ich werde die Pythonversion des Sortierers hier zur Verfuegung stellen, sobald er funktioniert.
Ich habe außerdem noch tsort gefunden. Ein Programm in den GNU Coreutils, dass genau das tut, was ich brauche

Bis spaeter dann...

[nkoehring]

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

[nkoehring]

achja... Meine "tolle" Zirkelsuche findet nicht alle Zirkelabhaengigkeiten

Folgende Eingabe zB fuehrt zu einem "maximum number of iterations exceeded":

Code: Alles auswählen

./tsort.py
> f1 f5 f6
> f2 f1
> f3 f4 f5
> f5 f6 f2

Das Original `tsort` sagt dazu:

Code: Alles auswählen

tsort
f6 f1
f5 f1
f1 f2
f5 f3
f4 f3
f2 f5
f6 f5
f4
f6
tsort: -: Eingabe enthält eine Schleife:
tsort: f1
tsort: f2
tsort: f5
f1
f2
f5
f3

... Wie kann ich denn solche komplizierten Abhaengigkeiten herausfiltern? Ich brauchte ja selbst eine ganze Weile um sie zu finden

[Leonidas]

Ich habe auch mal mein eigenes tsort.pyimplementiert, eine zirkuläre Abhängigkeit gibt es, wenn ``has_zero_dependents()`` ``False`` gibt und noch nicht alle Elemente durchlaufen sind. Eine explizite Zyklensuche gibt es nicht, die wäre noch zu implementieren.

Ich nutze aber das Eingabeformat von ``tsort`` (wobei man zugeben muss - es ist ziemlich blöd) und habe es mit einer Klasse implementiert. Man könnte es sicher noch etwas vereinfachen, indem man die Datenstrukturen etwas "intelligenter" macht.