Knoten Graph Sortierung nach Verbindungen

Ich habe einen Knoten Graph etwas wie im Bild untenKnoten Graph Sortierung nach Verbindungen

Ich mag würde die Knoten von Ebenen sortieren. So etwas wie

[8, 4, 5, 9, 3, 1, 2, 7 , 6, 10]

Wenn ich die Knoten und Verbindungen erstellen, können sie in beliebiger Reihenfolge sein. wie

class Element: 
    def __init__(self, name): 
     self.name = name 

class ElementConnection: 
    def __init__(self, element_source, element_dest): 
     self.element_source = element_source 
     self.element_dest = element_dest 



element5 = Element("Element5") 
element3 = Element("Element3") 
element1 = Element("Element1") 
element2 = Element("Element2") 
element8 = Element("Element8") 
element9 = Element("Element9") 
element7 = Element("Element7") 
element4 = Element("Element4") 
element10 = Element("Element10") 

elements = [element5, element3, element1, element2, element8, element10, element9, element7, element4] 

connections = [ 
       ElementConnection(element8, element5), 
       ElementConnection(element4, element3), 
       ElementConnection(element9, element2), 
       ElementConnection(element9, element7), 
       ElementConnection(element5, element7), 
       ElementConnection(element4, element9), 
       ElementConnection(element2, element6), 
       ElementConnection(element3, element1), 
       ElementConnection(element6, element10), 
       ElementConnection(element1, element10), 
       ]

Also würde ich gerne die Elementliste über die Verbindungsliste sortieren. Gibt es einen Standardweg, um dies zu erreichen?

Dank

Quelle

2017-06-14 Glenn Pierce

Was Sie beschreiben, ist [* topologische Bestellung *] (https://en.wikipedia.org/wiki/Topological_sorting#Kahn.27s_algorithm). –

Wenn dies keine Lernübung ist, würde ich vorschlagen, die NetworkX-Bibliothek zu untersuchen, anstatt das Rad neu zu erfinden. Weitere Informationen finden Sie in der Dokumentation für [topologische Sortierung] (https://networkx.github.io/documentation/networkx-1.9/reference/generated/networkx.algorithms.dag.topological_sort.html). –

Es ist keine Lernübung. Ich war mir der Namen des Algorithmus nicht bewusst. Mein Hauptcode ist in Rust, aber ich habe es vereinfacht, um in Python zu experimentieren. –

Ich glaube, Sie breadth first search Algorithmus für ein Diagramm betrachten kann. Es geht nicht um irgendeine Art von "Sortierung", aber Sie können die erforderlichen Schichten erhalten. Sie können eine Beschreibung dieses Algorithmus durch den obigen Link erhalten (es ist ein Beispiel für einen Baum).

Quelle

2017-06-14 08:44:33 Dmitry

Akzeptiert dies, wie es scheint gut zu funktionieren und war die erste Antwort nur für Breite erste Suche. –

Knoten Graph Sortierung nach Verbindungen

Antwort

Verwandte Themen