Rekursiver Sortieralgorithmus

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Benutzeravatar
nkoehring
User
Beiträge: 543
Registriert: Mittwoch 7. Februar 2007, 17:37
Wohnort: naehe Halle/Saale
Kontaktdaten:

Rekursiver Sortieralgorithmus

Beitragvon nkoehring » Dienstag 22. Mai 2007, 18:51

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

Beitragvon BlackJack » Dienstag 22. Mai 2007, 19:24

Dein Problem nennt sich Topologische Sortierung.
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Dienstag 22. Mai 2007, 19:28

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!
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Benutzeravatar
nkoehring
User
Beiträge: 543
Registriert: Mittwoch 7. Februar 2007, 17:37
Wohnort: naehe Halle/Saale
Kontaktdaten:

Beitragvon nkoehring » Dienstag 22. Mai 2007, 20:27

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...
Benutzeravatar
nkoehring
User
Beiträge: 543
Registriert: Mittwoch 7. Februar 2007, 17:37
Wohnort: naehe Halle/Saale
Kontaktdaten:

Es funktioniert :D

Beitragvon nkoehring » Sonntag 27. Mai 2007, 20:50

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 :D ).

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
Benutzeravatar
nkoehring
User
Beiträge: 543
Registriert: Mittwoch 7. Februar 2007, 17:37
Wohnort: naehe Halle/Saale
Kontaktdaten:

Beitragvon nkoehring » Montag 28. Mai 2007, 18:50

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 :oops:
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Dienstag 29. Mai 2007, 09:53

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.
My god, it's full of CARs! | Leonidasvoice vs Modvoice

Wer ist online?

Mitglieder in diesem Forum: Whitie