Ich habe eine leichtgewichtige Grafik-Lib erstellt, die drei Objekte (Vertex, Edge, Graph) und eine Funktion (topo_sort) enthält, die wie folgt aussieht:
%Vor%Und das funktioniert gut, wenn ich eine flache DAG habe. Aber was ich erreichen möchte, ist das Hinzufügen von Untergraphen (oder verschachtelten Graphen) in mein Hauptdiagramm, wie Sie in dieser Illustration sehen können, die ich zeichne:
Dies ist immer noch eine DAG, also wenn ich meine Funktion darauf ausführe, wird die normale topo_sort -Ausgabe in etwa so aussehen:
Meine bevorzugte Ausgabe wäre jedoch, wenn alle Scheitelpunkte, von denen ein Untergraph abhängt, "verarbeitet" sind, bevor die Scheitelpunkte des Untergraphen verarbeitet werden - so sollte es etwa so aussehen:
%Vor%Aber ich konnte keine Ressourcen finden auf:
Ich hoffe, ich könnte mein Problem ausführlich genug erklären - obwohl, wenn etwas fehlt, lass es mich wissen, und ich werde meine Frage mit den fehlenden Teilen erweitern.
Vielen Dank im Voraus!
BEARBEITEN:
Ich fand diese (Boost-Graph-Bibliothek, BGL) und es sieht so aus, als ob es ein sehr ähnliches (oder genau das gleiche?) Problem löst, das ich habe, obwohl ich mit C ++ nicht vertraut bin, also verstehe ich nicht, wie es funktioniert und was genau es tut - aber ich lege das hier, vielleicht wird jemand es hilfreich finden, meine Fragen zu beantworten.
EDIT 2:
Ich akzeptiere auch Pseudocode, nicht nur Python! Natürlich, wenn eine existierende Python-Bibliothek das weiß, bin ich daran interessiert, aber ich möchte nicht eine so große Bibliothek wie graph-tools zum Beispiel benutzen - deshalb habe ich meine eigene erstellt, deshalb bevorzuge ich Implementierungen mehr als libs.
Vielleicht ist es ein bisschen spät für Sie, aber für andere Leute mit ähnlichen Problemen:
Wie man einen Eckpunkt in einem Graphen als Teil eines Untergraphen "markiert" oder "speichert"?
Warum geben Sie dem Vertex-Objekt nicht nur ein Attribut subgraph , das eine Ganzzahl oder eine String-Beschriftung enthält, zu welcher Untergrafik der Vertex gehört? (Wenn Sie NetworkX verwenden möchten, verwenden Sie das Knotenattribut-Wörterbuch ).
Auf diese Weise können Sie dieses Subgraph-Attribut in Ihrem Sortieralgorithmus überprüfen.
Wie sortiere ich die Scheitelpunkte basierend auf ihren Untergraphenabhängigkeiten (wie das obige Beispiel)?
Ich bin kein Experte für topologische Sortierung, aber wenn jeder Scheitelpunkt den Subgraphen "weiß", zu dem er gehört, bin ich dazu gekommen (mit NetworkX), aber Sie können die Teile, die ich in Ihrer eigenen Bibliothek verwendet habe, einfach implementieren ): Der folgende Code sammelt alle "Abhängigkeiten", die Sie beschrieben haben (alle Scheitelpunkte, die vor dem aktuellen stehen müssen). Sie können diese Information verwenden, um Ihre topol_sort () - Funktion so zu ändern, dass sie nur den aktuellen Vertex an die Liste anfügt, wenn nicht alle Vertices in ihren Abhängigkeiten bereits in der Liste sind.
%Vor%Wie bekomme oder verarbeite ich den Untergraphen als eigenständiges Diagramm?
Ich bin mir nicht sicher, was Sie genau hier wollen. Vielleicht hilft dies ( wieder, mit NetworkX), vor allem diesen Teil:
Um einen Untergraphen mit einer eigenen Kopie der Kanten- / Knotenattribute zu erstellen, verwenden Sie: nx.Graph (Ggraph (nbunch))
Wenn Kantenattribute Container sind, kann eine tiefe Kopie erhalten werden mit: Ggraph (nbunch) .copy ()
Ich hoffe, das hilft jedem ...:)
Lesen Sie Ihre Aussage über Graph-Tools, aber immer noch nicht sicher, ob Sie eine Bibliothek für einen bestimmten Job verwenden möchten oder wie Sie es selbst schreiben möchten.
Vielleicht sehen Sie sich
an %Vor%und sehen, ob es Ihnen hilft, Ihr Problem zu lösen?
Tags und Links python python-3.x graph topological-sort subgraph
