Graphen in Python

[asdfasdf]

Hey liebes PythonDe-Forum,
Kurz mal zu mir: Ich bin ein Programmier-Anfänger und versuche mich gerade an dem Thema Graphen. Momentan ist mein Problem, dass ich nicht weiter weiß, wie ich alle Pfade ab einem gewissen Knoten berechne... Es handelt sich um einen gerichteten Graph dargestellt durch ein dictionary. Jetzt sind mir schon mehrere Bergriffe, wie zum Beispiel (iterative) Tiefensuche, Breitensuche oder Backtracking während meiner Onlinesuche begegnet, aber ich weiß nicht wirklich was damit anzufangen. Mit der rekursiven Programmierung hab ich auch nur wenig Erfahrung... Was sagt ihr wie ich vorgehen sollte ? Sollte ich mir Tiefen - oder Breitensuche näher anschauen? Was sind eigentlich die deren jeweiligen Vorteile?
Ich hoffe die Frage passt hier ins Forum!

LG

[BlackJack]

@asdfasdf: Man sollte Breiten- und Tiefensuche näher anschauen um zu verstehen wie die funktionieren und was die Unterschiede sind um zu verstehen wann man welches benutzt.

Gutes Buch über Algorithmen und Datenstrukturen inklusive Graphen ist Introduction to Algorithms. Allerdings nicht ganz billig. Und man sollte die englische Ausgabe nehmen und nicht die deutsche. Die fand ich deutlich anstrengender und komplizierter. IIRC haben die Übersetzer nicht nur übersetzt sondern das ganze auch nach „deutschem Geschmack” etwas umgestrickt, also nicht verständlich beschrieben sondern an einigen Stellen deutlich ”mathematischer” mit Formeln schön kryptisch. War zumindest bei der ersten und/oder zweiten Auflage so.

Eine gute Python-Bibliothek für Graphenalgoritmen ist NetworkX.

[pyHoax]

Versuch doch mal ein Beispiel zu liefern.
Ich habe das verstanden:

Du hast folgenden Beispiel Graph (dargestellt als dict)

Code: Alles auswählen

{ 
    'a': {  
        'a': { 
            'a': 111, 
            'b': 112, 
            'c': 113
         },
        'b':{ 
            'a': 121,
            'b': 122
        }
    },
    'b': 2  
}

Alle Pfade ab a wären dann:
a/a
a/b
a/c
b/a
b/b

Alle Pfade ab a/b wären dann:
a
b

oder Pfade ab a/a wären:
a
b
c

Passt das ?

Ansonsten schau mal hier:
https://de.wikipedia.org/wiki/Iterative_Tiefensuche
https://de.wikipedia.org/wiki/Breitensuche
https://de.wikipedia.org/wiki/Backtracking

[asdfasdf]

zu PyHoax:
Hier mal ein vereinfachtes Beispiel, wie ich es ähnlich habe:

Code: Alles auswählen

graph = { 0 : [4],
          1 : [4],
          2 : [5],
          3 : [],
          4 : [6,7],
          5 : [],
          6 : [8,9],
          7 : [],
          8 : [],
          9 : []}

Und jetzt versuche ich von einem Knoten alle Pfade zu berechnen. Hab mir jetzt mal die Tiefensuche etwas genauer angeschaut und die Theorie etwas verstanden, aber ich hab keine wirkliche Ahnung wie ich das implementieren soll...

zu BlackJack:
Ein Buch werde ich mir momentan wahrscheinlich noch nicht kaufen. Von NetworkX hab ich auch schon gehört... Gibt es da inbuilt-functions die mir bei meinem Problem weiterhelfen?

LG

[BlackJack]

@asdfasdf: Was heisst jetzt *alle* Pfade? Wirklich *alle* oder die kürzesten Pfade vom Ausgangsknoten zu jedem anderen?

NetworkX hat eine Menge Algorithmen für Graphen bereits fertig implementiert. Und kommt mit verschiedenen Darstellungen von Graphen klar. Unter anderem mit Deinem Wörterbuch. Alle Pfade vom Knoten 0 zu allen anderen (erreichbaren) Knoten:

Code: Alles auswählen

In [44]: graph
Out[44]: 
{0: [4],
 1: [4],
 2: [5],
 3: [],
 4: [6, 7],
 5: [],
 6: [8, 9],
 7: [],
 8: [],
 9: []}

In [45]: g = nx.DiGraph(graph)

In [46]: nx.single_source_shortest_path(g, 0)
Out[46]: 
{0: [0],
 4: [0, 4],
 6: [0, 4, 6],
 7: [0, 4, 7],
 8: [0, 4, 6, 8],
 9: [0, 4, 6, 9]}

[asdfasdf]

Ich suche nicht den kürzesten Pfad, sondern alle Pfade von dem jeweiligen Knoten.

LG

[nezzcarth]

@pyhoax:
Wozu ist denn die mittlere Verschachtelungsebene gedacht? Die Elemente des inneren Dictionarys könnte man für einen gewichteten Graphen doch auch direkt in das mittlere schreiben und so eine einfachere Struktur erzeugen -- oder übersehe ich etwas?

Also:

Code: Alles auswählen

graph = { 
        'a': { 
            'a': 111, 
            'b': 112, 
            'c': 113
         },
        'b':{ 
            'a': 121,
            'b': 122
        },
}

Edit:
Und wofür ist das einzelne 'b' im mittleren Dictionary da?

[BlackJack]

@asdfasdf: Also alle einfachen Pfade oder es gibt die Garantie das der Graph azyklisch ist‽ Das Ergebnis macht bei dem Beispielgraph allerdings keinen Unterschied.

Code: Alles auswählen

In [55]: list(chain.from_iterable(nx.all_simple_paths(g, 0, t) for t in g.nodes_iter()))
Out[55]: [[0, 4], [0, 4, 6], [0, 4, 7], [0, 4, 6, 8], [0, 4, 6, 9]]

[asdfasdf]

Nein es gibt keine Garantie, dass der Graph azyklisch ist, doch das ignorier ich erstmals um die Sache nicht noch komplizierter zu machen. Ich werde mir jetzt NetworkX anschauen, aber eigentlich ist es mein Ziel ohne zusätzliche Module zu lösen.

LG

[nezzcarth]

Nein es gibt keine Garantie, dass der Graph azyklisch ist. Ich werde mir jetzt NetworkX anschauen, aber eigentlich ist es mein Ziel ohne zusätzliche Module zu lösen.

LG

Wenn du einen einfachen, ungewichteten Graphen hast, kannst du ihn meiner Ansicht nach eigentlich schon so modellieren, wie in deinem zweiten Beispiel gezeigt. Du legst dir dann eine Liste mit allen zu besuchenden Knoten an und initalisierst sie mit deinem Startelement. Du übernimmst die dort gespeicherten Nachbarknoten in deine Knotenliste und fährst mit dem nächsten Element fort. Je nachdem, wie du das nächste Element bestimmst und wie die Nachbarn in die Knotenliste übernommen werden, kannst du verschiedene Suchstrategien umsetzen.

Hier mal ein Vorschlag, wie man so nach meinem Verständnis zum Beispiel eine simple "Breitensuche" für den kürzesten Pfad zwischen zwei Pfaden realisieren könnte: (Die Suche nach allen Pfaden wolltest du ja machen... )

Code: Alles auswählen

from collections import deque

def search(graph, start, goal):
    nodes = deque(((start, 0),))
    while nodes:
        node, level = nodes.popleft()
        if node == goal:
            break
        level += 1
        neighbors = graph.get(node)
        if neighbors:
            nodes.extend([(neighbor, level) for neighbor in neighbors])
    else:
        level = None
    return level

def main():    
    graph = { 0 : [4],
              1 : [4],
              2 : [5],
              3 : [],
              4 : [6,7],
              5 : [],
              6 : [8,9],
              7 : [],
              8 : [],
              9 : []}
          
    print(search(graph, 0, 7))

if __name__ == '__main__':
    main()

Vielleicht geht es an einigen Stellen auch noch etwas eleganter?

[pyHoax]

@pyhoax:
Wozu ist denn die mittlere Verschachtelungsebene gedacht? Die Elemente des inneren Dictionarys könnte man für einen gewichteten Graphen doch auch direkt in das mittlere schreiben und so eine einfachere Struktur erzeugen -- oder übersehe ich etwas?

Ich habe die Angaben aus dem ersten Posting versucht zu einen Bild zusammen zufügen, knapp daneben ist halt auch vorbei.

Meine Wahl war die Notation für einen gerichteten Baum in Form von mehreren geschachtelten Dictionaries. (Der gerichtete Baum ist auch ein gerichteter Graph)

Was heisst jetzt *alle* Pfade?

Genau...daher die Aufgabenstellung will Pfade ausgehend von einen Knoten berechnen , das impliziert das der Graph nicht zyklisch ist.

Wenn du jetzt meine Datenstruktur liest, dann mach dir klar das nur die Keys 'a', 'b' des root Dicts auch die Namen der 'root' Knoten sind.
Der Name der Knoten eines Baumes werden Idalerweise als Pfad der Knotenkeys durch den Baum beschrieben (man denke an eine Rest-API oder eine Verzeichnisstruktur). Daher ist eine Wiederholung des keys 'a' in der Darstellung nicht die Referenzierung des selben Knotens.

Schlecht geraten.. weil ich ein guten Informatiker bin und Optimist, denn die Aufgabe hat es in sich:
Die von asdfasdf präsentierte Datenstruktur ist nur zufällig nicht zyklisch konfiguriert, sie könnte es aber.
Wenn ich nun algorithmisch auf der Struktur arbeite, muss ich der Datenstruktur vertrauen das sie den dummen Computer nicht in eine Endlosschleife zwingt.. sprich die Anzahl der Pfad nicht berechenbar ist oder ich muss wie der GC es hat eine Detecion für Zyklische Pfade einbauen.

Nein es gibt keine Garantie, dass der Graph azyklisch ist, doch das ignorier ich erstmals um die Sache nicht noch komplizierter zu machen.

Dem kann ich daher auch nicht folgen, denn es macht die Sache schon etwas kompliziert.

[BlackJack]

@pyHoax: Naja, so viel komplizierter wird es auch nicht wenn man von allen *einfachen* Pfaden ausgeht, also alle in denen jeder Knoten nur einmal vorkommt.

[pyHoax]

@pyHoax: Naja, so viel komplizierter wird es auch nicht wenn man von allen *einfachen* Pfaden ausgeht, also alle in denen jeder Knoten nur einmal vorkommt.

Aye. hab ich mir auch gedacht...

ist zwar noch nicht das Ende aller Weisheit und rekursiv aber funktionert:

Code: Alles auswählen

def walk_rekursiv(graph, start):
    result = []
    def _rekursiv(n, path):
        if graph[n]:
            for next_node in graph[n]:
                if next_node in path:
                    raise Exception('Cycle in Graph Error')
                _rekursiv(next_node, path + [n])
        else:
           result.append(path + [n])

    _rekursiv(start,  [])
    return result

Habs gerade nicht als Generator mit Rekursion hinbekommen

[asdfasdf]

Schon Mal vielen Dank für die schnellen und umfangreichen Antworten von euch! Ich werde mich damit wahrscheinlich heute Abend, wenn ich wieder Zeit habe, beschäftigen.
Jetzt hab ich noch eine andere Frage :
Wie kann ich unabhängige Bäume eines Graphen erkennen und dann abspeichern?
Habt ihr vielleicht ein paar Denkanstöße?

LG und vielen Dank!

[BlackJack]

@asdfasdf: Was sind denn jetzt Bäume eines Graphen? Nicht zusammenhänge Teilgraphen die azyklisch sind (sonst kann es kein Baum sein) und die die Eigenschaften eines Baums erfüllen? Muss man die aus einem beliebigen Graphen herausfinden? Oder kann man davon ausgehen das es sich schon um einen Wald handelt? NetworkX nennt so einen Wald „branching“ und bietet zum einen eine Funktion die auf diese Eigenschaft testet (`is_branching()`) und man kann den dann mit `weakly_connected_components()` in die einzelnen Bäume zerlegen und da dann jeweils die Wurzel suchen wenn man die benötigt.

[asdfasdf]

Nicht zusammenhänge Teilgraphen die azyklisch sind aus einem beliebigen Graph. Sry, ich komm bei den Begriffen schnell durcheinander.

LG