Représenter des graphiques (structure de données) en Python

Comment représenter proprement un graphe en Python ? (À partir de zéro, c'est-à-dire pas de bibliothèques!)
Quelle structure de données (par exemple dicts / tuples / dict (tuples)) sera rapide mais aussi efficace en mémoire?
Il faut pouvoir y effectuer diverses opérations graphiques .

Comme indiqué, les différentes représentations graphiques peuvent aider. Comment les implémenter en Python?

Quant aux bibliothèques, cette question a d'assez bonnes réponses.

Même si c'est une question un peu ancienne, j'ai pensé donner une réponse pratique à quiconque trébucherait dessus.

Disons que vous obtenez vos données d'entrée pour vos connexions sous la 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 la plus efficace pour les graphiques en Python est un dict d'ensembles . Ce sera la structure sous-jacente de notre Graphclasse. Vous devez également savoir si ces connexions sont des arcs (dirigés, connecter dans un sens) ou des arêtes (non dirigés, connecter dans les deux sens). Nous allons gérer cela en ajoutant un directedparamètre à la Graph.__init__méthode. Nous ajouterons également d'autres méthodes utiles.

import pprint
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.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):
        """ 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" pour créer une find_shortest_pathméthode et d'autres.

Voyons cela en action cependant ...

>>> 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)  # undirected
>>> 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']

NetworkX est une superbe bibliothèque de graphes Python. Vous aurez du mal à trouver quelque chose dont vous avez besoin et qu'il ne fait pas déjà.

Et c'est open source afin que vous puissiez voir comment ils ont implémenté leurs algorithmes. Vous pouvez également ajouter des algorithmes supplémentaires.

https://github.com/networkx/networkx/tree/master/networkx/algorithms

Premièrement, le choix des représentations classiques par liste ou par matrice dépend du but (de ce que vous voulez faire de la représentation). Les problèmes et algorithmes bien connus sont liés au choix. Le choix du type de représentation abstraite dicte comment il doit être implémenté.

Deuxièmement, la question est de savoir si les sommets et les arêtes doivent être exprimés uniquement en termes d'existence, ou s'ils portent des informations supplémentaires.

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

La liste Python est implémentée comme un tableau dynamique de références, le tuple Python est implémenté comme un tableau statique de références avec un contenu constant (la valeur des références ne peut pas être modifiée). Pour cette raison, ils peuvent être facilement indexés. De cette façon, la liste peut également être utilisée pour l'implémentation de matrices.

Une autre façon de représenter les matrices est les tableaux implémentés par le module standard array - plus contraints par rapport au type stocké, valeur homogène. Les éléments stockent directement la valeur. (La liste stocke les références aux objets de valeur à la place). De cette façon, la mémoire est plus efficace et l'accès à la valeur est plus rapide.

Parfois, vous pouvez trouver utile une représentation encore plus restreinte comme bytearray.

Il existe deux excellentes bibliothèques de graphiques NetworkX et igraph . Vous pouvez trouver les deux codes sources de la bibliothèque sur GitHub. Vous pouvez toujours voir comment les fonctions sont écrites. Mais je préfère NetworkX car il est facile à comprendre.
Voir leurs codes pour savoir comment ils font les fonctions. Vous obtiendrez plusieurs idées et pourrez ensuite choisir comment vous souhaitez créer un graphique en utilisant des structures de données.