Wie sortiert man basierend auf Abhängigkeiten?

Ich habe eine Klasse, die eine Liste von "Abhängigkeiten" auf andere Klassen des gleichen Basistyps verweist.Wie sortiert man basierend auf Abhängigkeiten?

class Foo(Base): 
    dependencies = [] 

class Bar(Base): 
    dependencies = [Foo] 

class Baz(Base): 
    dependencies = [Bar]

Ich möchte die Instanzen, die diese Klassen basierend auf ihren Abhängigkeiten generieren, sortieren. In meinem Beispiel würde ich erwarten, dass Foo zuerst kommt, dann Bar, dann Baz.

Was ist der beste Weg, dies zu sortieren?

Quelle

2009-06-04 Soviut

Sind Sie über eine topologische Sortierung in Python zu fragen? http://en.wikipedia.org/wiki/Topological_sorting –

Ich möchte nach "sortierten gerichteten Graphen" suchen, weil das im Wesentlichen das ist, was Sie versuchen zu tun. –

Es wird eine topologische Sortierung genannt.

Quelle

2009-06-04 18:47:11

Obwohl Ihr Recht über die Lösung benötigt, ist dies nicht wirklich ein vollständiges/brauchbares Beispiel. – sleepycal

@sleepycal: Diese Website ist für die Beantwortung von Fragen, nicht für die Bereitstellung von Komplettlösungen für Ihre Probleme. –

Das ist ein schlechtes Argument, Sie haben ein Code-Snippet gepostet, das nicht funktioniert. Es ist nichts als Faulheit. – sleepycal

Ich hatte eine ähnliche Frage nur letzte Woche - ich wünschte, ich würde dann über Stack Overflow wissen! Ich jagte etwas herum, bis ich feststellte, dass ich einen DAG (Gerichteten Azyklischen Graph hatte, da meine Abhängigkeiten nicht rekursiv oder zirkulär sein konnten). Dann habe ich ein paar Referenzen für Algorithmen gefunden, um sie zu sortieren. Ich habe eine Tiefen-Traversierung verwendet, um zu den Blattknoten zu gelangen und sie zuerst der sortierten Liste hinzuzufügen.

Hier ist eine Seite, die ich nützlich gefunden:

Directed Acyclic Graphs

Quelle

2009-06-04 20:18:09

Interessant ... aber keine Links zu diesen anderen Ressourcen. Können Sie einige der Links angeben, um die Antwort auf diese Frage zu vervollständigen? –

Ich habe oben einen Link hinzugefügt. Da es neu ist, würde ich nur einen in meinem Post einfügen, also hier ist ein weiterer, der einen guten Hintergrund hat: http://www.codeproject.com/KB/java/BFSDFS.aspx –

Danke, der Link, den Sie in Ihrer Antwort angegeben haben ist ziemlich gut. Ich wünschte nur, diese Uniformen könnten tatsächlich eine echte Grafik einfügen, anstatt ansi Kunst. hehe – Soviut

Wie sortiert man basierend auf Abhängigkeiten?

Antwort

Verwandte Themen