Representar gráficos (estructura de datos) en Python

105

¿Cómo se puede representar claramente un gráfico en Python ? (¡Comenzando desde cero, es decir, sin bibliotecas!)
¿Qué estructura de datos (por ejemplo, dicts / tuples / dict (tuples)) será rápida pero también eficiente en memoria?
Uno debe poder realizar varias operaciones gráficas en él.

Como se señaló, las diversas representaciones gráficas pueden ayudar. ¿Cómo se implementan en Python?

En cuanto a las bibliotecas, esta pregunta tiene muy buenas respuestas.

shad0w_wa1k3r
fuente
1
Ya existen muchas bibliotecas: graph-tool.skewed.de/performance , code.google.com/p/python-graph , networkx.github.io
Kassym Dorsel
1
Para implementar un gráfico, consulte el artículo de Wikipedia que enumera implementaciones comunes y su eficiencia tanto en memoria como en velocidad: en.wikipedia.org/wiki/…
Kassym Dorsel
Puede probar GitHub.com/thePastor/pangaia. Necesita una pequeña reescritura para usar el defaultdict de la biblioteca estándar (que no estaba disponible cuando se escribió el código). Utiliza una estructura de datos recursiva para hacerlo más elegante que otras implementaciones.
theDoctor
1
Para gráficos dirigidos , este ensayo de python.org sugiere una dictde las siguientes opcioneslist . Básicamente algo como {<parent>: [<child>, ...], ...}.
djvg
Puede implementar el uso de diccionario como lista de adyacencia con claves como nodos y valores como una lista de nodos adyacentes para cada clave.
Shahrukh khan

Respuestas:

140

Aunque esta es una pregunta algo antigua, pensé en dar una respuesta práctica a cualquiera que se encuentre con esto.

Digamos que obtiene sus datos de entrada para sus conexiones como una lista de tuplas así:

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

La estructura de datos que he encontrado más útil y eficiente para gráficos en Python es un dictado de conjuntos . Esta será la estructura subyacente de nuestra Graphclase. También debe saber si estas conexiones son arcos (dirigidos, se conectan en una dirección) o bordes (no dirigidos, se conectan en ambos sentidos). Lo manejaremos agregando un directedparámetro al Graph.__init__método. También agregaremos algunos otros métodos útiles.

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

Lo dejo como un "ejercicio para que el lector" cree un find_shortest_pathy otros métodos.

Sin embargo, veamos esto en acción ...

>>> 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']
mVChr
fuente
6
Aunque esta pregunta es muy antigua, creo que este es exactamente el tipo de respuesta que esperaba en ese momento. El ejemplo realmente ayuda a explicar cómo se puede realizar la implementación al mismo tiempo que se mantiene realmente simple. Se pueden encontrar implementaciones de diferentes bibliotecas de código abierto, pero la explicación no estaría a la par. ¡Gracias!
shad0w_wa1k3r
2
¿Qué tipo de modificación se requiere para agregar peso a los bordes?
pshirishreddy
3
@pshirishreddy ¡Pregunta interesante! No había pensado en eso, pero mi instinto sería usar la heapqbiblioteca para apilar listas de tuplas en lugar de conjuntos. Por ejemplo, el gráfico sería un dictado de montones como: _graph = {'A': heapify([(0.3, 'D'), (0.5, 'B'), (0.75, 'A'), (0.9, 'C')])}(nota: en realidad no usaría heapifyasí, lea la ayuda de la biblioteca), entonces podría usar las heapqfunciones para insertar y obtener los bordes ponderados.
mVChr
@mVChr eso significaría un logtiempo de acceso. Pero, ¿cómo extender el diccionario que usó para mapear tanto nodeID como weight?
orezvani
Agradable ! La función se llama de forma recursiva. Esto parece ser un DFS ya que sigue expandiendo nodos. Para el camino más corto, podemos comparar la longitud de los caminos y devolver solo el más corto al final.
Jwalant Bhatt
36

NetworkX es una impresionante biblioteca de gráficos de Python. Te será difícil encontrar algo que necesites y que aún no funcione.

Y es de código abierto para que pueda ver cómo implementaron sus algoritmos. También puede agregar algoritmos adicionales.

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

terraza
fuente
7
Por eso NetworkX es un recurso fantástico. Es de código abierto para que pueda ver cómo implementaron sus algoritmos. También puede agregar algoritmos adicionales.
jterrace
2
Aproximadamente 2000 líneas de código para graph.py --> class Graph. Y todo lo que quiero ver es cómo se usan __iter__.
T.Woody
8

En primer lugar, la elección de las representaciones clásicas de lista frente a matrices depende del propósito (de qué quiere hacer con la representación). Los problemas y algoritmos conocidos están relacionados con la elección. La elección del tipo de representación abstracta dicta cómo debe implementarse.

En segundo lugar, la cuestión es si los vértices y los bordes deben expresarse solo en términos de existencia o si contienen información adicional.

Desde el punto de vista de los tipos de datos integrados de Python, cualquier valor contenido en otro lugar se expresa como una referencia (oculta) al objeto de destino. Si es una variable (es decir, una referencia con nombre), entonces el nombre y la referencia siempre se almacenan en un diccionario (interno). Si no necesita nombres, entonces la referencia se puede almacenar en su propio contenedor; aquí probablemente la lista de Python siempre se usará para la lista como abstracción.

La lista de Python se implementa como una matriz dinámica de referencias, la tupla de Python se implementa como una matriz estática de referencias con contenido constante (el valor de las referencias no se puede cambiar). Por eso se pueden indexar fácilmente. De esta forma, la lista se puede utilizar también para la implementación de matrices.

Otra forma de representar matrices son las matrices implementadas por el módulo estándar array, más restringidas con respecto al tipo almacenado, valor homogéneo. Los elementos almacenan el valor directamente. (En su lugar, la lista almacena las referencias a los objetos de valor). De esta manera, es más eficiente en memoria y también el acceso al valor es más rápido.

A veces, puede encontrar una representación útil incluso más restringida como bytearray.

pepr
fuente
7

Hay dos bibliotecas de gráficos excelentes NetworkX e igraph . Puede encontrar ambos códigos fuente de la biblioteca en GitHub. Siempre puede ver cómo se escriben las funciones. Pero prefiero NetworkX porque es fácil de entender.
Vea sus códigos para saber cómo hacen las funciones. Obtendrá varias ideas y luego podrá elegir cómo desea hacer un gráfico utilizando estructuras de datos.

Vineet Jain
fuente