Représentant des graphes (structure de données) en Python

Même si c'est un peu vieille question, j'ai pensé donner une réponse pratique pour quiconque de tomber sur ce.

Disons que vous obtenez vos données d'entrée pour vos connexions comme une liste de tuples de la sorte:

[('A', 'B'), ('B', 'C'), ('B', 'D'), ('C', 'D'), ('E', 'F'), ('F', 'C')]

La structure de données que j'ai trouvé pour être le plus utile et efficace pour les graphiques en Python est un dict de jeux de. Ce sera la structure sous-jacente de notre Graph classe. Vous devez également savoir si ces connexions sont des arcs (mise en scène, connecter d'une manière) ou les bords (non orienté, connectez les deux sens). Nous prenons en charge que par l'ajout d'un directed paramètre à la Graph.__init__ méthode. Nous allons également ajouter quelques autres méthodes utiles.

from collections import defaultdict
class Graph(object):
""" Graph data structure, undirected by default. """
def __init__(self, connections, directed=False):
self._graph = defaultdict(set)
self._directed = directed
self.add_connections(connections)
def add_connections(self, connections):
""" Add connections (list of tuple pairs) to graph """
for node1, node2 in connections:
self.add(node1, node2)
def add(self, node1, node2):
""" Add connection between node1 and node2 """
self._graph[node1].add(node2)
if not self._directed:
self._graph[node2].add(node1)
def remove(self, node):
""" Remove all references to node """
for n, cxns in self._graph.iteritems():
try:
cxns.remove(node)
except KeyError:
pass
try:
del self._graph[node]
except KeyError:
pass
def is_connected(self, node1, node2):
""" Is node1 directly connected to node2 """
return node1 in self._graph and node2 in self._graph[node1]
def find_path(self, node1, node2, path=[]):
""" Find any path between node1 and node2 (may not be shortest) """
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 vais le laisser comme un "exercice pour le lecteur" afin de créer un find_shortest_path et d'autres méthodes.

Nous allons le voir en action, mais...

>>> connections = [('A', 'B'), ('B', 'C'), ('B', 'D'),
('C', 'D'), ('E', 'F'), ('F', 'C')]
>>> g = Graph(connections, directed=True)
>>> pprint(g._graph)
{'A': {'B'},
'B': {'D', 'C'},
'C': {'D'},
'E': {'F'},
'F': {'C'}}
>>> g = Graph(connections)  # undirected
>>> 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')
>>> 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')
>>> pprint(g._graph)
{'B': {'D', 'C'},
'C': {'D', 'F', 'B'},
'D': {'C', 'E', 'B'},
'E': {'D', 'F'},
'F': {'E', 'C'}}
>>> g.add('G', 'B')
>>> 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']

Tout d'abord, le choix de la classique liste vs matrice représentations dépend de l'objectif (sur ce que vous voulez faire avec la représentation). Les problèmes bien connus et les algorithmes sont liées au choix. Le choix de la représentation abstraite genre de dicte la façon dont il devrait être mis en œuvre.

Second lieu, la question est de savoir si les sommets et les arêtes doivent être exprimé uniquement dans les conditions d'existence, ou s'ils portent des informations supplémentaires.

De Python les types de données intégrés point de vue, toute valeur contenue ailleurs est exprimée en (caché) une référence à l'objet cible. Si c'est une variable (c'est à dire nommé référence), puis le nom et la référence est toujours stockée en interne) dictionnaire. Si vous n'avez pas besoin de noms, il peut être stocké dans votre propre conteneur -- ici, probablement, liste Python sera toujours utilisé pour la liste comme une abstraction.

Liste Python est implémenté sous la forme d'un tableau dynamique de références, Python tuple est mis en œuvre comme statique tableau de références avec la constante de contenu (la valeur de références ne peut pas être changé). En raison de qu'ils peuvent être facilement indexé. De cette façon, la liste peut être également utilisé pour la mise en œuvre de matrices.

Une autre façon de représenter les matrices sont des tableaux mis en œuvre par le module standard array -- plus de contrainte à l'égard de la stockées type, valeur homogène. Les éléments de stocker la valeur directement. (La liste des magasins les références à la valeur des objets à la place). De cette façon, il est plus efficace en terme de mémoire et aussi l'accès à la valeur est plus rapide.

Parfois, vous pouvez trouver utile encore plus restreint de la représentation comme bytearray.