Même si c'est une question quelque peu ancienne, j'ai pensé donner une réponse pratique à quiconque tomberait dessus.
Disons que vous obtenez vos données d'entrée pour vos connexions sous forme d'une liste de tuples comme ceci :
[('A', 'B'), ('B', 'C'), ('B', 'D'), ('C', 'D'), ('E', 'F'), ('F', 'C')]
La structure de données que j'ai trouvée la plus utile et efficace pour les graphiques en Python est un dictionnaire d'ensembles. Cela sera la structure sous-jacente pour notre classe Graph. Vous devez également savoir si ces connexions sont des arcs (dirigés, connectent dans un sens) ou des arêtes (non dirigés, connectent dans les deux sens). Nous gérerons cela en ajoutant un paramètre directed à la méthode Graph.__init__. Nous ajouterons également quelques autres méthodes utiles.
import pprint
from collections import defaultdict
class Graph(object):
""" Structure de données de graphique, non dirigée par défaut. """
def __init__(self, connections, directed=False):
self._graph = defaultdict(set)
self._directed = directed
self.add_connections(connections)
def add_connections(self, connections):
""" Ajouter des connexions (liste de paires de tuples) au graphique """
for node1, node2 in connections:
self.add(node1, node2)
def add(self, node1, node2):
""" Ajouter une connexion entre le nœud1 et le nœud2 """
self._graph[node1].add(node2)
if not self._directed:
self._graph[node2].add(node1)
def remove(self, node):
""" Supprimer toutes les références au nœud """
for n, cxns in self._graph.items(): # python3: items(); python2: iteritems()
try:
cxns.remove(node)
except KeyError:
pass
try:
del self._graph[node]
except KeyError:
pass
def is_connected(self, node1, node2):
""" Le nœud1 est-il directement connecté au nœud2 """
return node1 in self._graph and node2 in self._graph[node1]
def find_path(self, node1, node2, path=[]):
""" Trouver un chemin entre le nœud1 et le nœud2 (peut ne pas être le plus court) """
path = path + [node1]
if node1 == node2:
return path
if node1 not in self._graph:
return None
for node in self._graph[node1]:
if node not in path:
new_path = self.find_path(node, node2, path)
if new_path:
return new_path
return None
def __str__(self):
return '{}({})'.format(self.__class__.__name__, dict(self._graph))
Je laisse comme "exercice pour le lecteur" la création d'une méthode find_shortest_path et d'autres méthodes.
Voyons cela en action...
>>> connections = [('A', 'B'), ('B', 'C'), ('B', 'D'),
('C', 'D'), ('E', 'F'), ('F', 'C')]
>>> g = Graph(connections, directed=True)
>>> pretty_print = pprint.PrettyPrinter()
>>> pretty_print.pprint(g._graph)
{'A': {'B'},
'B': {'D', 'C'},
'C': {'D'},
'E': {'F'},
'F': {'C'}}
>>> g = Graph(connections) # non dirigé
>>> pretty_print = pprint.PrettyPrinter()
>>> pretty_print.pprint(g._graph)
{'A': {'B'},
'B': {'D', 'A', 'C'},
'C': {'D', 'F', 'B'},
'D': {'C', 'B'},
'E': {'F'},
'F': {'E', 'C'}}
>>> g.add('E', 'D')
>>> pretty_print.pprint(g._graph)
{'A': {'B'},
'B': {'D', 'A', 'C'},
'C': {'D', 'F', 'B'},
'D': {'C', 'E', 'B'},
'E': {'D', 'F'},
'F': {'E', 'C'}}
>>> g.remove('A')
>>> pretty_print.pprint(g._graph)
{'B': {'D', 'C'},
'C': {'D', 'F', 'B'},
'D': {'C', 'E', 'B'},
'E': {'D', 'F'},
'F': {'E', 'C'}}
>>> g.add('G', 'B')
>>> pretty_print.pprint(g._graph)
{'B': {'D', 'G', 'C'},
'C': {'D', 'F', 'B'},
'D': {'C', 'E', 'B'},
'E': {'D', 'F'},
'F': {'E', 'C'},
'G': {'B'}}
>>> g.find_path('G', 'E')
['G', 'B', 'D', 'C', 'F', 'E']
