[PYTHON] Mémo NetworkX (graphique dirigé)

Aperçu

Depuis que j'ai récemment commencé à utiliser NetworkX dans mes recherches, j'écrirai un module que je pense que je vais souvent utiliser comme mémo pour moi-même.

Je viens de commencer à utiliser Python, donc je ne pense pas pouvoir l'écrire intelligemment. De plus, il peut y avoir des parties où le libellé est incorrect (méthodes, packages, etc.).

Vous pouvez installer le package NetworkX avec pip. Vous pouvez le faire avec pip install network x.

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

Importation de packages NetworkX

Tout d'abord, importez le package NetworkX. Dans la documentation NetworkX, il est abrégé en «nx».

python3.5

import networkx as nx

Créer un graphique

Créer un graphique vide

Tout d'abord, créez un graphique vide pour travailler avec le graphique. Dans le cas d'un graphe orienté, il peut être généré avec DiGraph (). Pour les graphes non orientés, c'est Graph ().

python3.5

Graph = nx.DiGraph()

Ajouter un nœud

Ajoutez des nœuds au graphique vide créé précédemment. Les nœuds peuvent être ajoutés avec la méthode DiGraph.add_node ().

python3.5

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

Obtenir la liste des nœuds

C'est DiGraph.nodes () pour obtenir la liste des nœuds. Alternativement, vous pouvez également sortir avec Graph.nodes (data = True / False). Si aucun argument n'est donné, la valeur par défaut des données est False. Lorsque data = True est défini, il est acquis sous la forme d'une liste de tapples constituée d'un dictionnaire des noms de nœuds et des attributs des nœuds.

S'il s'agit d'un interpréteur interactif, la liste sera sortie simplement en appuyant sur Graph.nodes (), mais comme il s'agit essentiellement d'obtenir la liste des nœuds, si vous voulez afficher la liste des nœuds pendant l'exécution du fichier, print (Graph. Vous devez faire des nœuds ()) .

python3.5

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

Ajouter des nœuds ensemble

Vous pouvez également ajouter tous les nœuds à la fois à partir d'une liste ou d'un dictionnaire. Cela utilise la méthode DiGraph.add_nodes_from ().

python3.5

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

Créer un nœud avec des attributs

Dans la sortie de la liste des nœuds plus tôt, j'ai introduit que si vous définissez DiGraph.nodes (data = True), une liste de taples composée du nom du nœud et du dictionnaire des attributs du nœud sera sortie. C'est aussi DiGraph.add_node () pour générer un nœud avec des attributs.

python3.5

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

Vous pouvez ajouter autant d'attributs que vous le souhaitez.

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'})]

Supprimer le nœud

Utilisez la méthode DiGraph.remove_node () pour supprimer un nœud ajouté au graphe.

python3.5

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

Supprimer les nœuds à la fois

Comme pour l'ajout de nœuds, vous pouvez également supprimer des nœuds en bloc dans une liste ou un dictionnaire. Cela utilise la méthode DiGraph.remove_nodes_from ().

python3.5

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

Ajouter un bord

Nous ajouterons des arêtes qui relient les nœuds. Les bords peuvent être ajoutés avec la méthode DiGraph.add_edge (). Puisqu'il s'agit d'un graphe orienté, le premier argument est start et le second argument est target.

Python3.5

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

Obtenir la liste des bords

C'est DiGraph.edges () pour obtenir la liste des arêtes. Comme pour les nœuds, vous pouvez choisir d'afficher / masquer les attributs avec data = True / False pour obtenir la liste des arêtes.

Si c'est aussi un interpréteur interactif, la liste sera sortie en appuyant simplement sur Graph.edges (), mais si vous voulez sortir la liste en exécutant le fichier de code, vous devez faire print (Graph.edges ()). Est inutile.

Python3.5

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

Ajouter des bords ensemble

Les bords peuvent être ajoutés collectivement à partir d'une liste ou d'un dictionnaire ainsi que des nœuds. Pour les arêtes, utilisez la méthode 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')]

Ajouter un bord attribué

Bien entendu, vous pouvez également ajouter des attributs aux arêtes. Au contraire, il peut être plus courant d'ajouter des attributs aux arêtes. Vous pouvez maintenant réaliser un graphique pondéré.

En passant, dans le cas d'un graphique pondéré, si vous définissez le poids avec «poids», c'est facile car la valeur par défaut de la clé est souvent «poids» lors de la recherche d'un itinéraire plus tard. Les arêtes avec des attributs sont également 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})]

Ajouter des bords pondérés ensemble

Comme il existe de nombreuses situations pour créer un graphe pondéré, NetworkX a une méthode DiGraph.add_weighted_edges_from () pour faciliter l'ajout d'arêtes pondérées.

Dans ʻadd_edges_from () , les arêtes sont ajoutées ensemble à partir de la liste à 2 tuples de (point de départ, point de fin). ʻAdd_weighted_edges_from () ajoute des arêtes pondérées ensemble à partir de la liste à 3 tuples de (début, fin, poids).

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})]

Sauf indication contraire, la clé de poids est définie avec «poids». Cependant, si vous souhaitez spécifier le poids avec une clé autre que "weight", vous pouvez le modifier. Dans ce cas, définissez la clé comme suit.

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})]

Supprimer le bord

Utilisez la méthode DiGraph.remove_edge () pour supprimer l'arête ajoutée au graphique.

python3.5

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

Supprimer les bords à la fois

Comme pour l'ajout d'arêtes, vous pouvez également supprimer des arêtes en vrac d'une liste ou d'un dictionnaire. Cela utilise la méthode DiGraph.remove_edges_from ().

python3.5

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

Supprimer tous les nœuds et arêtes

Si vous voulez supprimer tous les nœuds et arêtes ajoutés et revenir à un graphe vide, utilisez la méthode 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()
[]

Recherche d'itinéraire

Vous venez de créer un graphique. NetworkX comprend également divers algorithmes de recherche d'itinéraire, ce qui facilite la recherche d'itinéraire. Dans mes recherches, il est nécessaire d'acquérir toutes les routes du point de départ au point d'arrivée, je vais donc l'écrire en premier.

Acquisition de tous les itinéraires

Cette fois, en supposant le graphique suivant comme exemple, recherchons la route entière du nœud de ʻaau nœud dec`.

Dans le cas de la recherche d'itinéraire, l'itinéraire le plus court est souvent trouvé, mais NetworkX dispose également d'un module qui acquiert toutes les routes, qui est nx.all_simple_paths (G, source, cible, cutoff = None). cutoff est la profondeur à laquelle la recherche est arrêtée, et si cela est spécifié, seuls les itinéraires d'une longueur inférieure ou égale à cutoff seront renvoyés. Non spécifié par défaut.

J'ai écrit le code suivant pour obtenir toutes les routes.

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)

Les résultats d'exécution suivants.

Résultat d'exécution

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

Il a été confirmé que toutes les routes pouvaient être acquises.

Recherche d'itinéraire le plus court

Le module de recherche d'itinéraire le plus court implémente divers algorithmes, qui implémentent déjà la méthode Dyxtra, la méthode Worshall-Floyd et la méthode Bellman-Ford (je ne sais pas de quel type d'algorithme il s'agit car je ne connais pas du tout le graphique). Le sujet de mon intérêt de recherche n'est pas le chemin le plus court, je l'ajouterai donc si mon énergie continue dans le futur.

À propos, la référence du module de recherche d'itinéraire le plus court est ici.