python - barplot - pandas plot

Representando gráficos(estructura de datos) en Python

Question

¿Cómo se puede representar claramente un graph en Python ? (Comenzando desde cero, es decir, ¡sin bibliotecas!)
¿Qué estructura de datos (p. Ej., Dicts / tuples / dict (tuplas)) será rápida pero también eficiente en cuanto a la memoria?
Uno debe ser capaz de hacer varias operations gráficos en él.

Como se señaló, las diversas representaciones gráficas podrían ayudar. ¿Cómo se puede implementar en Python?

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

Answer 1

Aunque esta es una pregunta algo vieja, pensé que podría dar una respuesta práctica para cualquiera que tropezara con esto.

Supongamos que obtiene los datos de entrada de sus conexiones como una lista de tuplas, por ejemplo:

[(''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 los gráficos en Python es una definición de conjuntos . Esta será la estructura subyacente de nuestra clase Graph . También debe saber si estas conexiones son arcos (dirigidos, conectarse en una dirección) o bordes (no dirigidos, conecte en ambos sentidos). Lo manejaremos agregando un parámetro directed al método Graph.__init__ . También agregaremos algunos otros métodos útiles.

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

Lo dejo como un "ejercicio para el lector" para crear un find_shortest_path y otros métodos.

Veamos esto en acción, aunque ...

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

Answer 2

En primer lugar, la elección de la lista clásica frente a las representaciones matriciales depende del propósito (sobre 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 alguna información adicional.

Desde el punto de vista de los tipos de datos incorporados en Python, cualquier valor contenido en otra parte se expresa como una referencia (oculta) al objeto de destino. Si se trata de una variable (es decir, referencia nombrada), el nombre y la referencia siempre se almacenan en un diccionario (interno). Si no necesita nombres, entonces la referencia puede almacenarse en su propio contenedor; en este caso, probablemente la lista de Python siempre se utilizará 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 pueden indexarse ​​fácilmente. De esta manera, la lista también se puede usar para la implementación de matrices.

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

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

Answer 3

Hay dos excelentes bibliotecas de gráficos NetworkX e igraph . Puede encontrar ambos códigos fuente de la biblioteca en GitHub. Siempre puedes ver cómo se escriben las funciones. Pero prefiero NetworkX por su facilidad de comprensión.
Vea sus códigos cómo hacen las funciones. Obtendrá una idea múltiple y luego elegirá cómo quiere hacer un gráfico utilizando estructuras de datos.

Answer 4

networkx.github.io es una impresionante biblioteca de gráficos de Python. Te costará mucho encontrar algo que necesites que ya no funciona.