Gráficos en Python - Teoría e implementación - Representación de gráficos en código

Los gráficos son una estructura de datos extremadamente versátil. ¡Más de lo que la mayoría de la gente cree! Los gráficos se pueden usar para modelar prácticamente cualquier cosa, dada su naturaleza de modo...

Los gráficos en Python se pueden representar de varias maneras diferentes. Los más notables son matrices de adyacencia, listas de adyacencia y listas de aristas. En esta guía, los cubriremos todos. Al implementar gráficos, puede cambiar entre estos tipos de representaciones cuando lo desee.

En primer lugar, recapitularemos rápidamente la teoría de grafos, luego explicaremos las estructuras de datos que puede usar para representar un gráfico y, finalmente, le daremos una implementación práctica para cada representación.

{.icon aria-hidden=“true”}

Nota: Las implementaciones encontradas en esta lección se pueden encontrar en el siguiente repositorio de GitHub.

¿Qué es un gráfico? En resumen

Repasemos rápidamente las definiciones básicas con respecto a los gráficos una vez más. Un gráfico es una estructura de datos que puede usar para modelar la jerarquía y las relaciones entre objetos. Consiste en un conjunto de nodos y un conjunto de aristas. Los nodos representan objetos individuales, mientras que los bordes ilustran las relaciones entre esos objetos.

{.icon aria-hidden=“true”}

Nota: Nuevamente, los términos 'nodo' y 'vértice' ('nodos' y 'vértices') a menudo se usan indistintamente. En este curso, hemos optado por usar el término nodo, pero tiene el mismo significado que el término vértice.

Si cada borde de un gráfico ilustra una conexión bidireccional, llamamos a ese gráfico no dirigido. Por otro lado, si puede atravesar cada borde en una sola dirección, el gráfico está dirigido.

No todos los nodos de un gráfico necesitan estar conectados con otros. Si puede acceder a cada nodo desde cualquier otro nodo en un gráfico, llamamos a ese gráfico conectado. Pero a veces hay algunos nodos a los que no se puede acceder desde ningún otro nodo en un gráfico; de eso se tratan los gráficos desconectados. El concepto erróneo común es que cada gráfico tiene que estar conectado, pero la realidad es que no es así; de hecho, un gráfico no puede contener bordes, solo nodos:

Desde el punto de vista de la implementación, lo último que debemos cubrir es el peso de un borde. Es un valor numérico asignado al borde que describe cuánto cuesta atravesar ese borde. Cuanto menor sea el peso de un borde, más barato será atravesarlo. En base a eso, los gráficos con pesos asignados a sus bordes se denominan gráficos ponderados:

¡Armado con el conocimiento fundamental, puede profundizar en las formas de implementar un gráfico!

Las tres formas más comunes de representar un gráfico {#las tres formas más comunes de representar un gráfico}

En esta sección, repasaremos las formas más comunes de representar un gráfico. Te explicaremos la intuición detrás de cada uno de ellos y te daremos algunos ejemplos ilustrativos. Luego, puede usar ese conocimiento para implementar un gráfico en Python.

En términos generales, los nodos de cualquier gráfico dado están etiquetados con números (comenzando desde cero) en aras de una implementación más simple. Es por eso que usaremos esa notación en los siguientes ejemplos e implementaciones.

Usaremos el siguiente gráfico dirigido ponderado como ejemplo en las siguientes secciones:

{.icon aria-hidden=“true”}

Nota: Hemos elegido un gráfico dirigido ponderado como ejemplo porque ilustra la mayoría de los matices de implementación. En términos generales, cambiar entre gráficos ponderados y no ponderados es bastante sencillo. Cambiar entre gráficos dirigidos y no dirigidos también es algo bastante fácil de hacer. Cubriremos cada uno de esos temas en las siguientes secciones cuando sea necesario.

Lista de bordes

Una lista de aristas es probablemente la forma más sencilla de representar un gráfico, pero dado que carece de una estructura adecuada, a menudo se usa solo con fines ilustrativos. Lo usaremos para explicar algunos algoritmos de gráficos porque proporciona poca o ninguna sobrecarga y nos permite centrarnos en la implementación del algoritmo, en lugar de la implementación del gráfico en sí.

Como ya sabe, cada borde conecta dos nodos y puede tener un peso asignado. Por lo tanto, cada borde está representado por una lista de la siguiente manera: [nodo1, nodo2, peso], donde peso es una propiedad opcional (no requerida si tiene un gráfico no ponderado). Como sugiere su nombre, una lista de aristas almacena un gráfico como una lista de aristas representadas de la manera descrita.

Echemos un vistazo a un gráfico ponderado dirigido y su lista de aristas:

Como puede ver, una lista de aristas es efectivamente una tabla. Cada fila de esa tabla representa un borde: dos de sus nodos y el peso de ese borde. Dado que este es un gráfico ponderado, el orden de los nodos en la representación del borde ilustra la dirección del borde. Puede atravesar el borde solo desde nodo1 a nodo2.

Por otro lado, tiene dos enfoques para tratar con gráficos no dirigidos. El primer enfoque es agregar dos filas para cada nodo, una para cada dirección del borde. Ese enfoque es ineficiente en el espacio, pero debe usarlo si está usando gráficos dirigidos y no dirigidos indistintamente. El segundo enfoque se puede usar solo si está seguro de que solo tratará con gráficos no dirigidos. En ese caso, puede considerar que cada borde no está dirigido y mantener la representación igual: una fila para cada borde.

PROS:

  • Simple y fácil de entender
  • Ideal para fines ilustrativos.
  • Representa un gráfico por definición (un conjunto de nodos y un conjunto de aristas)

CONTRAS:

  • No estructurado en ninguna forma o forma.
  • No elegible para ninguna aplicación del mundo real
  • No eficiente
  • No es lo suficientemente versátil para representar gráficos dirigidos y no dirigidos indistintamente.

Matriz de adyacencia

Una matriz de adyacencia es una de las formas más populares de representar un gráfico porque es la más fácil de entender e implementar y funciona razonablemente bien para muchas aplicaciones. Utiliza una matriz nxn para representar un gráfico (n es el número de nodos en un gráfico). En otras palabras, el número de filas y columnas es igual al número de nodos en un gráfico.

Inicialmente, cada campo de la matriz se establece en un valor especial que elija: inf, 0, -1, False, etc., lo que sugiere que no hay nodos presentes en el gráfico. Después de la etapa inicial, puede agregar cada borde del gráfico llenando el campo apropiado con 1 (para gráficos no ponderados) o el peso del borde (para gráficos ponderados).

La matriz mencionada es esencialmente una tabla en la que cada fila y columna representa un nodo del gráfico. Por ejemplo, la fila 3 se refiere al nodo 3; es por eso que puede usar una matriz de adyacencia para representar solo gráficos con nodos etiquetados con números.

{.icon aria-hidden=“true”}

Nota: De hecho, puede modificar la implementación de una matriz de adyacencia para que pueda manejar nodos con nombres diferentes, pero el trabajo adicional necesario generalmente anula las ganancias potenciales. Es por eso que hemos optado por usar la implementación más simple: solo nodos etiquetados con números.

El campo que es la intersección de la fila i y la columna j se refiere a la presencia o peso del borde entre los nodos i y j. Por ejemplo, si completa el campo que es la intersección de la fila 1 y la columna 4, indica que hay un borde que conecta los nodos 1 y 4 (en ese orden específico). Si un gráfico está ponderado, rellena ese campo con el peso del borde o 1 en el caso de un gráfico no ponderado.

En el caso de gráficos no dirigidos, debe agregar dos entradas para cada borde, una para cada dirección.

Si la explicación anterior no fue lo suficientemente clara, intentemos simplificarla mostrando cómo crear una matriz de adyacencia en el ejemplo del siguiente gráfico:

Hay n nodos en este gráfico. Por lo tanto, creamos una tabla con n filas y columnas e inicializamos todas las celdas con 0, el valor especial que indica que no hay bordes entre dos nodos. Dado que el gráfico de ejemplo está ponderado y dirigido, debe:

  • Escanea cada borde en un gráfico
  • Determinar el inicio y el nodo final de ese borde
  • Determinar el peso de ese borde.
  • Rellene el campo apropiado de la matriz con el valor de peso

Usemos el borde 3-4 como ejemplo. El nodo inicial es 3 y el nodo final es 4, por lo tanto, sabe que debe completar el campo que es la intersección de la fila 3 y la columna 4. En la imagen, puede leer que el peso del borde es 11, por lo tanto, complete el campo apropiado con 11. Ahora has marcado la presencia del borde 3-4. Ese proceso se repite hasta que haya marcado cada borde en un gráfico.

PROS:

  • Tiempo de búsqueda bajo: puede determinar si existe un borde en el tiempo de O (1)
  • Agregar/eliminar bordes lleva tiempo O(1)
  • Fácil de implementar y entender.

CONTRAS:

  • Ocupa más espacio O(num_of_nodes²)
  • La adición de un nodo requiere un tiempo de O(num_of_nodes²)
  • Es costoso encontrar nodos adyacentes al nodo seleccionado - O(num_of_nodes)
  • Costoso recorrer un gráfico - O(num_of_nodes²)
  • Costoso etiquetar/enumerar bordes - O(num_of_nodes²)

Lista de adyacencias

Una lista de adyacencia es la forma más eficiente de almacenar un gráfico. Le permite almacenar solo los bordes que están presentes en un gráfico, que es lo opuesto a una matriz de adyacencia, que almacena explícitamente todos los bordes posibles, tanto existentes como inexistentes. Una matriz de adyacencia se desarrolla inicialmente para representar solo gráficos no ponderados, pero de la manera más efectiva posible: utilizando solo una matriz.

Como puede ver en la ilustración a continuación, podemos representar nuestro gráfico de ejemplo usando solo una matriz de 12 valores enteros. Compare eso con la matriz de adyacencia: consta de elementos (n es el número de nodos en un gráfico), donde la lista de adyacencia solo toma elementos n+e (e es el número de bordes) . Mucho más eficiente en el uso del espacio si un gráfico no es denso (tiene una pequeña cantidad de bordes).

El problema es que una lista de adyacencia es más difícil de entender en comparación con la matriz de adyacencia, por lo que si no las ha interpretado antes, siga con cuidado:

Lo primero que debe saber para construir una lista de adyacencia es el número de nodos en un gráfico. En nuestro gráfico de ejemplo, hay 5 nodos, por lo que los primeros 5 lugares en una lista representan esos nodos, p. El elemento con el índice 1 representa un nodo 1. Después de reservar los primeros 5 lugares en una lista, puede comenzar a llenar la lista. El valor en el índice i se refiere al índice en la lista donde puede encontrar índices de nodos adyacentes al nodo i.

Por ejemplo, el valor en el índice ‘0’ es ‘5’, lo que significa que debe mirar el índice ‘5’ en la lista de adyacencia para encontrar qué nodos están conectados al nodo ‘0’; esos son los nodos ‘0’. , 1 y 2. Pero, ¿cómo sabíamos cuándo dejar de buscar nodos adyacentes? ¡Es bastante simple! Mire el valor en el índice al lado de 0 en la lista. El siguiente índice es 1, representa el nodo 1 y su valor es 8, lo que significa que puede encontrar nodos adyacentes al nodo 1 a partir del índice 8 en la lista de adyacencia. Por lo tanto, puede encontrar nodos adyacentes al nodo 0 como valores de la lista entre los índices 5 y 8.

Para comprender mejor esta estructura, puede reordenar los elementos de la lista de adyacencia de una forma más estructurada. Si lo hace, puede ver que la estructura resultante se parece mucho a una lista enlazada:

Además, la estructura de la lista enlazada se parece mucho a la de los diccionarios (o mapas). Tiene un conjunto de claves - nodos y un conjunto de valores para cada clave - un conjunto de nodos adyacentes al nodo clave. Si desea representar un gráfico ponderado, debe encontrar una forma de almacenar el peso además del nodo adyacente (como puede ver en la siguiente ilustración). Pero cubriremos los detalles de implementación en secciones posteriores.

La siguiente ilustración muestra la lista de adyacencia del gráfico de ejemplo, con y sin pesos:

Cuando echa un vistazo a la lista adyacente ponderada, puede construir fácilmente el conjunto de bordes del gráfico de ejemplo. El nodo 0 tiene tres nodos adyacentes: 0, 1, 2, lo que significa que el gráfico tiene bordes 0-0, 0-1 y 0-2. El peso de esos bordes también se puede leer en la lista de adyacencia. El peso del borde ‘0-0’ es ‘25’, el peso del borde ‘0-1’ es ‘5’, y así sucesivamente, para cada borde del gráfico.

PROS:

  • Barato para encontrar nodos adyacentes al nodo seleccionado - O(1)
  • Eficiente para gráficos menos densos (bajo número de aristas en comparación con el número de nodos)
  • Puede usarlo para nodos etiquetados con letras y números
  • Bajo costo de recorrer un gráfico - O(longitud_de_lista)
  • Bajo costo de etiquetado/enumeración de bordes - O(longitud_de_lista)

CONTRAS:

  • Tiempo de búsqueda elevado - O(longitud_de_lista)
  • Alto costo de eliminar un borde - O(longitud_de_lista) (extensión lógica de tiempo de búsqueda alto)

{.icon aria-hidden=“true”}

Nota: La longitud_de_la_lista es igual a la suma del número de nodos y el número de aristas en un gráfico.

Cómo implementar un gráfico en Python

¡Ahora sabes cómo representar un gráfico con las estructuras de datos más comunes! Lo siguiente que debe hacer es implementar esas estructuras de datos en Python. El objetivo de esta guía es brindarle una implementación gráfica lo más universal posible, pero aún así hacerlo liviano. Eso es lo que le permite concentrarse en implementar algoritmos gráficos en lugar de un gráfico como estructura de datos. Idealmente, tendría una clase contenedora que representa una estructura de datos de gráfico que puede usar para envolver cualquier método de algoritmo gráfico que desee implementar más adelante.

{.icon aria-hidden=“true”}

Nota: Las implementaciones simples que crearemos en esta guía deberían cubrirlo en todos los casos de uso no altamente específicos. Por ejemplo, supondremos que todos los nodos están etiquetados con números a partir de cero. Pero si necesita implementaciones más completas, ¡lo tenemos cubierto! Puedes encontrar implementaciones completas en el siguiente repositorio de GitHub.

La clase Graph almacenará la representación del gráfico, así como todos los demás métodos que pueda necesitar para manipular un gráfico. Echemos un vistazo a su estructura general y profundicemos en la implementación después:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Graph:
    # Constructor
        # Number of edges
        # Adjacancy matrix, adjacency list, list of edges

    # Methods for adding edges
    
    # Methods for removing edges

    # Methods for searching a graph
        # BFS, DFS, Dijkstra, A*...

    # Methods for finding a minimum spanning tree
        # Prim's algorithm, Kruskal's algorithm, Borůvka's algorithm...
    
    # Other interesting methods

Como puede ver, hay varias, digamos, "secciones" que debe implementar en una clase Graph. La sección más importante y en la que nos centraremos en esta sección es la sección Constructor. Ahí es donde debe poner la implementación de su gráfico (representación de la estructura de datos). Después de eso, puede implementar cualquier algoritmo relacionado con gráficos como método en esta clase. Alternativamente, puede implementar cualquier algoritmo de búsqueda de gráficos/recorrido de gráficos como un método independiente y pasar el gráfico en sí. La diferencia es, literalmente, solo en si el algoritmo hace referencia a ‘yo’ (gráfico principal) o al ‘gráfico’ pasado.

Echemos un vistazo a cómo implementar cada una de las representaciones gráficas mencionadas en la clase Graph. En esta sección, usaremos el gráfico de ejemplo mostrado anteriormente para probar cada implementación:

Cómo implementar una lista de bordes en Python

Como dijimos antes, una lista de bordes no tiene muchas aplicaciones en el mundo real, pero a menudo se usa con fines ilustrativos. Puede usarlo cuando necesite una implementación simple de un gráfico que no complique innecesariamente la implementación de un algoritmo.

Echemos un vistazo a la implementación de la clase Graph que usa una lista de aristas para representar un gráfico:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Graph:
    # Constructor
    def __init__(self, num_of_nodes, directed=True):
        self.m_num_of_nodes = num_of_nodes
        self.m_directed = directed
        
        # Different representations of a graph
        self.m_list_of_edges = []
    
    # Add edge to a graph
    def add_edge(self, node1, node2, weight=1):        
        # Add the edge from node1 to node2
        self.m_list_of_edges.append([node1, node2, weight])
        
        # If a graph is undirected, add the same edge,
        # but also in the opposite direction
        if not self.m_directed:
            self.m_list_of_edges.append([node1, node2, weight])

    # Print a graph representation
    def print_edge_list(self):
        num_of_edges = len(self.m_list_of_edges)
        for i in range(num_of_edges):
            print("edge ", i+1, ": ", self.m_list_of_edges[i])

Como puede ver, esta implementación es bastante simple. Un gráfico se representa como una lista de aristas, donde cada arista se representa mediante una lista de la siguiente forma: [nodo1, nodo2, peso]. Por lo tanto, un gráfico es efectivamente una matriz, donde cada fila representa un borde.

Vamos a crear nuestro gráfico de ejemplo y ver cómo lo almacena la lista de aristas.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
graph = Graph(5)

graph.add_edge(0, 0, 25)
graph.add_edge(0, 1, 5)
graph.add_edge(0, 2, 3)
graph.add_edge(1, 3, 1)
graph.add_edge(1, 4, 15)
graph.add_edge(4, 2, 7)
graph.add_edge(4, 3, 11)

graph.print_edge_list()

En primer lugar, el gráfico de ejemplo tiene 5 nodos, por lo tanto, crea un gráfico con 5 nodos usando el constructor. Luego agrega todos los bordes al gráfico creado e imprime el gráfico. Eso generará lo siguiente:

1
2
3
4
5
6
7
edge  1 :  [0, 0, 25]
edge  2 :  [0, 1, 5]
edge  3 :  [0, 2, 3]
edge  4 :  [1, 3, 1]
edge  5 :  [1, 4, 15]
edge  6 :  [4, 2, 7]
edge  7 :  [4, 3, 11]

Como puede ver, esta salida está en línea con la lista de ejemplo de bordes que hemos mostrado en secciones anteriores:

{.icon aria-hidden=“true”}

Nota: Si quisieras hacer este gráfico no dirigido, deberías construir el constructor de la siguiente manera: graph = Graph(5,directed=False).

Cómo implementar una matriz de adyacencia en Python

Una matriz de adyacencia es esencialmente una matriz nxn simple, donde n es el número de nodos en un gráfico. Por lo tanto, lo implementaremos como la matriz con filas y columnas num_of_nodes. Usaremos una lista de comprensión para construirla e inicializar todos los campos a 0.

En este caso, 0 es un valor especial que se refiere al hecho de que inicialmente no hay bordes en un gráfico. Agregar bordes es bastante simple, solo necesitamos marcar el campo apropiado de la matriz con ‘1’ o ‘peso’ dependiendo de si un gráfico está ponderado o no:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Graph:
    def __init__(self, num_of_nodes, directed=True):
        self.m_num_of_nodes = num_of_nodes
        self.m_directed = directed

        # Initialize the adjacency matrix
        # Create a matrix with `num_of_nodes` rows and columns
        self.m_adj_matrix = [[0 for column in range(num_of_nodes)] 
                            for row in range(num_of_nodes)]

    def add_edge(self, node1, node2, weight=1):
        self.m_adj_matrix[node1][node2] = weight

        if not self.m_directed:
            self.m_adj_matrix[node2][node1] = weight

    def print_adj_matrix(self):
        print(self.m_adj_matrix)

Ahora probemos esta implementación de la manera descrita anteriormente:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
graph = Graph(5)

graph.add_edge(0, 0, 25)
graph.add_edge(0, 1, 5)
graph.add_edge(0, 2, 3)
graph.add_edge(1, 3, 1)
graph.add_edge(1, 4, 15)
graph.add_edge(4, 2, 7)
graph.add_edge(4, 3, 11)

graph.print_edge_list()

Ejecutar el código anterior producirá el siguiente resultado:

1
2
3
4
5
[25, 5, 3, 0, 0]
[0, 0, 0, 1, 15]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 7, 11, 0]

Como era de esperar, la salida es la misma matriz que la que hemos mostrado en las secciones anteriores:

{.icon aria-hidden=“true”}

Nota: Si quisieras hacer este gráfico no dirigido, deberías construir el constructor de la siguiente manera: graph = Graph(5,directed=False). En ese caso, la matriz de adyacencia será simétrica.

Cómo implementar una lista de adyacencia en Python

Como explicamos en las secciones anteriores, la mejor manera de representar una lista de adyacencia en Python es usando un diccionario: tiene un conjunto de claves y los valores correspondientes.

Crearemos una clave para cada nodo y un conjunto de nodos adyacentes para cada clave. De esa forma, crearemos efectivamente un conjunto de nodos adyacentes para cada nodo en un gráfico. En esencia, un nodo adyacente representa el borde entre el nodo clave y el nodo adyacente, por lo tanto, debemos asignar un peso a cada borde. Es por eso que representaremos cada nodo adyacente como una tupla - un par del nombre del nodo adyacente y el peso de ese borde:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Graph:
    def __init__(self, num_of_nodes, directed=True):
        self.m_num_of_nodes = num_of_nodes
        self.m_nodes = range(self.m_num_of_nodes)

        # Define the type of a graph
        self.m_directed = directed

        self.m_adj_list = {node: set() for node in self.m_nodes}      

    def add_edge(self, node1, node2, weight=1):
        self.m_adj_list[node1].add((node2, weight))
        
        if not self.m_directed:
            self.m_adj_list[node2].add((node1, weight))

    def print_adj_list(self):
        for key in self.m_adj_list.keys():
            print("node", key, ": ", self.m_adj_list[key])

Nuevamente, probemos la implementación de la manera descrita anteriormente:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
graph = Graph(5)

graph.add_edge(0, 0, 25)
graph.add_edge(0, 1, 5)
graph.add_edge(0, 2, 3)
graph.add_edge(1, 3, 1)
graph.add_edge(1, 4, 15)
graph.add_edge(4, 2, 7)
graph.add_edge(4, 3, 11)

graph.print_edge_list()

La salida es idéntica a la lista enlazada descrita en las secciones anteriores:

1
2
3
4
5
node 0 :  {(2, 3), (0, 25), (1, 5)}
node 1 :  {(3, 1), (4, 15)}
node 2 :  set()
node 3 :  set()
node 4 :  {(2, 7), (3, 11)}

{.icon aria-hidden=“true”}

Nota: Si quisieras hacer este gráfico no dirigido, deberías construir el constructor de la siguiente manera: graph = Graph(5,directed=False).

Conclusión

Después de leer esta guía, es posible que se pregunte: ¿Qué representación gráfica debo usar en última instancia? Pero la respuesta, como de costumbre, no es sencilla: depende.

Cada representación gráfica tiene sus pros y sus contras: brilla en un caso de uso, pero tiene un bajo rendimiento en otros. Es por eso que le hemos brindado una descripción completa de las representaciones gráficas. Después de leer esta guía, debe tener una comprensión intuitiva de las representaciones gráficas, saber cómo implementar cada una de ellas y cuándo usar cada una según una lista útil de pros y contras. Por lo tanto, esta guía debería ser un buen punto de partida si desea profundizar en la implementación de algoritmos relacionados con gráficos.

Por otro lado, si quieres profundizar más en la implementación del propio grafo, te recomendamos que le eches un vistazo al siguiente repositorio de GitHub. Allí puede encontrar implementaciones más detalladas y completas de estructuras de datos de gráficos.

Licensed under CC BY-NC-SA 4.0