[PYTHON] NetworkX-Memo (gerichtete Grafik)

Überblick

Da ich kürzlich angefangen habe, NetworkX in meiner Forschung zu verwenden, werde ich ein Modul schreiben, von dem ich glaube, dass ich es oft als Memo für mich selbst verwenden werde.

Ich habe gerade angefangen, Python zu verwenden, daher glaube ich nicht, dass ich es intelligent schreiben kann. Es kann auch Teile geben, in denen der Wortlaut falsch ist (Methoden, Pakete usw.).

Sie können das NetworkX-Paket mit pip installieren. Sie können pip install network x verwenden.

Reference : http://networkx.readthedocs.io/en/stable/

NetworkX-Pakete importieren

Importieren Sie zunächst das NetworkX-Paket. In der NetworkX-Dokumentation wird es als "nx" abgekürzt.

python3.5

import networkx as nx

Diagramm erstellen

Erstellen eines leeren Diagramms

Erstellen Sie zunächst ein leeres Diagramm, um mit dem Diagramm zu arbeiten. Im Fall eines gerichteten Graphen kann er mit "DiGraph ()" erzeugt werden. Für ungerichtete Diagramme ist es "Graph ()".

python3.5

Graph = nx.DiGraph()

Knoten hinzufügen

Fügen Sie dem zuvor erstellten leeren Diagramm Knoten hinzu. Knoten können mit der Methode DiGraph.add_node () hinzugefügt werden.

python3.5

>>> Graph.add_node('hoge')
>>> Graph.add_node('fuga')

Liste der Knoten abrufen

Es ist DiGraph.nodes (), um die Liste der Knoten abzurufen. Alternativ können Sie auch mit "Graph.nodes (data = True / False)" ausgeben. Wenn kein Argument angegeben wird, ist der Standardwert für Daten False. Wenn "data = True" gesetzt ist, wird es als eine Liste von Tapples erfasst, die aus einem Wörterbuch von Knotennamen und Attributen der Knoten besteht.

Wenn es sich um einen interaktiven Interpreter handelt, wird die Liste nur durch Drücken von "Graph.nodes ()" ausgegeben. Da Sie jedoch im Wesentlichen nur die Knotenliste abrufen, sollten Sie "print (Graph", wenn Sie die Knotenliste während der Dateiausführung ausgeben möchten. Sie müssen node ()) `tun.

python3.5

>>> Graph.nodes()
['fuga', 'hoge']
>>> Graph.nodes(data=False)
['fuga', 'hoge']
>>> Graph.nodes(data=True)
[('fuga', {}), ('hoge', {})]

Fügen Sie Knoten zusammen

Sie können auch Knoten auf einmal aus einer Liste oder einem Wörterbuch hinzufügen. Dies verwendet die Methode DiGraph.add_nodes_from ().

python3.5

>>> Graph.add_nodes_from(['foo','bar'])
>>> Graph.nodes(data=False)
['fuga', 'bar', 'hoge', 'foo']

Erstellen Sie einen Knoten mit Attributen

In der vorherigen Ausgabe der Knotenliste habe ich eingeführt, dass beim Festlegen von "DiGraph.nodes (data = True)" eine Liste von Tapples ausgegeben wird, die aus einem Wörterbuch mit Knotennamen und Attributen von Knoten besteht. Es ist auch "DiGraph.add_node ()", um einen Knoten mit Attributen zu erzeugen.

python3.5

>>> Graph.add_node('hoge', color = 'green')
>>> Graph.add_node('fuga', color = 'red')
>>> Graph.nodes(data=True)
[('fuga', {'color': 'red'}), ('hoge', {'color': 'green'})]

Sie können beliebig viele Attribute hinzufügen.

python3.5

>>> Graph.add_node('foo', color = 'white', lang = 'en')
>>> Graph.nodes(data=True)
[('fuga', {'color': 'red'}), ('foo', {'color': 'white', 'lang': 'en'}), ('hoge', {'color': 'green'})]

Knoten löschen

Verwenden Sie die Methode DiGraph.remove_node (), um einen dem Diagramm hinzugefügten Knoten zu entfernen.

python3.5

>>> Graph.nodes()
['fuga', 'hoge', 'bar', 'foo']
>>> Graph.remove_node('bar')
>>> Graph.nodes()
['fuga', 'hoge', 'foo']

Knoten sofort löschen

Wie beim Hinzufügen von Knoten können Sie auch Knoten in großen Mengen aus einer Liste oder einem Wörterbuch löschen. Dies verwendet die Methode DiGraph.remove_nodes_from ().

python3.5

>>> e = Graph.nodes()
>>> e
['fuga', 'hoge', 'foo']
>>> Graph.remove_nodes_from(e)
>>> Graph.nodes()
[]

Kante hinzufügen

Wir werden Kanten hinzufügen, die Knoten verbinden. Kanten können mit der Methode DiGraph.add_edge () hinzugefügt werden. Da es sich um einen gerichteten Graphen handelt, ist das erste Argument start und das zweite Argument ist target.

Python3.5

>>> Graph.nodes(data=False)
['hoge', 'foo', 'fuga', 'bar']
>>> Graph.add_edge('hoge','fuga')
>>> Graph.add_edge('foo','bar')

Kantenliste abrufen

Es ist DiGraph.edges (), um die Liste der Kanten abzurufen. Wie bei Knoten können Sie auswählen, ob Attribute mit "data = True / False" angezeigt / ausgeblendet werden sollen, um die Kantenliste zu erhalten.

Wenn dies auch ein interaktiver Interpreter ist, wird die Liste nur durch Drücken von "Graph.edges ()" ausgegeben. Wenn Sie die Liste jedoch durch Ausführen der Codedatei ausgeben möchten, müssen Sie "print (Graph.edges ())" ausführen. Ist nutzlos.

Python3.5

>>> Graph.edges()
[('hoge', 'fuga'), ('foo', 'bar')]
>>> Graph.edges(data=False)
[('hoge', 'fuga'), ('foo', 'bar')]
>>> Graph.edges(data=True)
[('hoge', 'fuga', {}), ('foo', 'bar', {})]

Kanten zusammenfügen

Kanten können gemeinsam aus einer Liste oder einem Wörterbuch sowie aus Knoten hinzugefügt werden. Verwenden Sie für Kanten die Methode DiGraph.add_edges_from ().

Python3.5

>>> Graph.nodes()
['fuga', 'hoge', 'foo', 'bar']
>>> Graph.add_edges_from([('hoge','fuga'),('foo','bar')])
>>> Graph.edges()
[('hoge', 'fuga'), ('foo', 'bar')]

Fügen Sie eine zugeordnete Kante hinzu

Natürlich können Sie Kanten auch Attribute hinzufügen. Vielmehr ist es möglicherweise üblicher, Kanten Attribute hinzuzufügen. Sie können jetzt ein gewichtetes Diagramm erstellen.

Übrigens ist es im Fall eines gewichteten Diagramms einfach, wenn Sie das Gewicht mit "Gewicht" einstellen, da der Standardwert des Schlüssels bei der späteren Suche nach einer Route häufig "Gewicht" ist. Kanten mit Attributen sind auch "DiGraph.add_edge ()".

Python3.5

>>> Graph.add_edge('foo', 'hoge', weight=0.7)
>>> Graph.add_edge('bar', 'fuga', weight=0.7)
>>> Graph.edges(data=True)
[('foo', 'hoge', {'weight': 0.7}), ('bar', 'fuga', {'weight': 0.7})]

Fügen Sie gewichtete Kanten zusammen

Da es viele Situationen gibt, in denen ein gewichtetes Diagramm erstellt werden muss, verfügt NetworkX über die Methode "DiGraph.add_weighted_edges_from ()", um das Hinzufügen gewichteter Kanten zu vereinfachen.

In add_edges_from () werden Kanten aus der 2-Tupel-Liste von (Startpunkt, Endpunkt) addiert. add_weighted_edges_from () fügt gewichtete Kanten aus der 3-Tupel-Liste von (Start, Ende, Gewicht) hinzu.

python3.5

>>> Graph.add_weighted_edges_from([('hoge','fuga',0.4),('foo','bar',0.2)])
>>> Graph.edges(data=True)
[('hoge', 'fuga', {'weight': 0.4}), ('foo', 'bar', {'weight': 0.2})]

Sofern nicht anders angegeben, wird der Gewichtungsschlüssel mit "Gewicht" gesetzt. Wenn Sie das Gewicht jedoch mit einem anderen Schlüssel als "weight" angeben möchten, können Sie es ändern. Stellen Sie in diesem Fall den Schlüssel wie folgt ein.

python3.5

>>> Graph.add_weighted_edges_from([('hoge','fuga',0.4),('foo','bar',0.2)],weight='omomi')
>>> Graph.edges(data=True)
[('hoge', 'fuga', {'omomi': 0.4}), ('foo', 'bar', {'omomi': 0.2})]

Kante löschen

Verwenden Sie die Methode DiGraph.remove_edge (), um die dem Diagramm hinzugefügte Kante zu entfernen.

python3.5

>>> Graph.edges()
[('hoge', 'fuga'), ('foo', 'bar')]
>>> Graph.remove_edge('hoge','fuga')
>>> Graph.edges()
[('foo', 'bar')]

Kanten sofort löschen

Wie beim Hinzufügen von Kanten können Sie auch Kanten in großen Mengen aus einer Liste oder einem Wörterbuch entfernen. Dies verwendet die Methode "DiGraph.remove_edges_from ()".

python3.5

>>> e = Graph.edges()
>>> e
[('hoge', 'fuga'), ('foo', 'bar')]
>>> Graph.remove_edges_from(e)
>>> Graph.edges()
[]

Löschen Sie alle Knoten und Kanten

Wenn Sie alle hinzugefügten Knoten und Kanten löschen und zu einem leeren Diagramm zurückkehren möchten, verwenden Sie die Methode DiGraph.clear ().

python3.5

>>> Graph.nodes()
['fuga', 'hoge', 'bar', 'foo']
>>> Graph.edges()
[('fuga', 'foo'), ('hoge', 'fuga'), ('bar', 'hoge'), ('foo', 'bar')]
>>> Graph.clear()
>>> Graph.nodes()
[]
>>> Graph.edges()
[]

Routensuche

Sie haben jetzt ein Diagramm erstellt. NetworkX enthält auch verschiedene Routensuchalgorithmen, die die Routensuche vereinfachen. In meiner Forschung ist es notwendig, alle Routen vom Startpunkt bis zum Endpunkt zu erfassen, daher werde ich dies zuerst schreiben.

Erfassung aller Routen

Nehmen wir dieses Mal unter der Annahme des folgenden Diagramms als Beispiel die gesamte Route vom Knoten "a" zum Knoten "c" an.

Bei der Routensuche wird häufig die kürzeste Route gefunden, aber NetworkX verfügt auch über ein Modul, das alle Routen erfasst: "nx.all_simple_paths (G, Quelle, Ziel, Cutoff = Keine)". "Cutoff" ist die Tiefe, in der die Suche gestoppt wird. Wenn dies angegeben ist, werden nur Routen mit einer Länge kleiner oder gleich "Cutoff" zurückgegeben. Standardmäßig nicht angegeben.

Ich habe den folgenden Code geschrieben, um alle Routen zu erhalten.

allpaths.py

import networkx as nx

Graph = nx.DiGraph()

Graph.add_nodes_from(['a','b','c','d'])

Graph.add_edges_from([('a','b'),('a','c'),('a','d'),('b','c'),('b','d'),('d','c')])

print('all paths')
for path in nx.all_simple_paths(Graph, source='a', target='c'):
    print(path)

Die folgenden Ausführungsergebnisse.

Ausführungsergebnis

all paths
['a', 'b', 'c']
['a', 'b', 'd', 'c']
['a', 'c']
['a', 'd', 'c']

Es wurde bestätigt, dass alle Routen erworben werden konnten.

Kürzeste Routensuche

Das Modul für die Suche nach kürzesten Routen implementiert verschiedene Algorithmen, die bereits die Dyxtra-Methode, die Worshall-Floyd-Methode und die Bellman-Ford-Methode implementieren (ich weiß nicht, um welche Art von Algorithmus es sich handelt, da ich den Graphen überhaupt nicht kenne). Das Thema meines Forschungsinteresses ist nicht der kürzeste Weg, daher werde ich ihn hinzufügen, wenn meine Energie in Zukunft weiter besteht.

Die Referenz des Suchmoduls für kürzeste Routen lautet übrigens hier.