Guía Completa para Trabajar con Grafos en Python: Ejemplos y Técnicas Esenciales

 Los grafos son una estructura de programación que nos permite, de manera más ágil, encontrar la ruta más rápida para llegar de un origen a un destino. En la programación, recuerden que siempre tratamos de representar algo del mundo real en un concepto que pueda ser programado (paradigmas de la programación). Imaginemos que estamos pensando en hacer un viaje en metro donde nuestro origen es Polanco y queremos llegar a Terminal Aérea. Para ello, existen algunas posibles rutas para llegar al destino. Esto lo podemos visualizar en la siguiente imagen.

Ahora vamos a llevar esto a como se vería en un grafo 

En la imagen cada círculo representa un punto por dónde podemos pasar y la flecha indica la dirección del grado y el número en ese caso representa los kilómetros entre cada punto. Vemos 3 caminos dibujados uno café, otro negro y otro rosa, si sumamos un punto por cada parada , el camino mas rápido es de 16 paradas. Hay mas opciones de caminos que podemos trazar y también en lugar de dar un valor de 1 a cada parada, podemos ponerles un mayor valor de acuerdo al tiempo de trayecto entre cada uno. Ahora es importante mencionar que este ejemplo es un grafo dirigido, porque el camino tiene una dirección o un sentido, es decir la flechita esta orientada a otro punto. También hay grafos no dirigidos. 

Ahora este grafo lo podemos llevar a un programa por medio de la librería networkx  la cual nos permite poder trabajar con grafos y Python. Documentación de la libreria https://networkx.org/documentation/stable/install.html

Recuerden siempre que vamos a utilizar una nueva librería en Python debemos instalarla en este caso utilizaremos el comando  PIP pip install networkx[default]

Una vez instalado vamos armar un programa que represente el grafo 

Luego la lógica para que encuentre el camino más rápido 

import networkx as nx

import matplotlib.pyplot as plt

# Crear un grafo vacío

G = nx.Graph()

# Agregar nodos (estaciones) y aristas (conexiones)

# Aquí estamos agregando algunas estaciones y conexiones de ejemplo.

estaciones = ["Pantitlán", "Zaragoza", "Gómez Farías", "Boulevard Puerto Aéreo", "Balbuena", "Moctezuma", "San Lázaro", "Candelaria", "Merced", "Pino Suárez"]

conexiones = [("Pantitlán", "Zaragoza"), ("Zaragoza", "Gómez Farías"), ("Gómez Farías", "Boulevard Puerto Aéreo"),

              ("Boulevard Puerto Aéreo", "Balbuena"), ("Balbuena", "Moctezuma"), ("Moctezuma", "San Lázaro"),

              ("San Lázaro", "Candelaria"), ("Candelaria", "Merced"), ("Merced", "Pino Suárez")]

# Agregar nodos al grafo

G.add_nodes_from(estaciones)

# Agregar aristas al grafo

G.add_edges_from(conexiones)

# Dibujar el grafo

pos = nx.spring_layout(G)  # Disposición de los nodos

nx.draw(G, pos, with_labels=True, node_size=500, node_color="skyblue", font_size=10, font_color="black", font_weight="bold")

# Mostrar el grafo

plt.show()

Ahora vamos analizar el punto mas rápido para llegar de Pantitlán a  Pino Suárez

Si quieren agregar dos líneas del metro, les comparto el código

import networkx as nx

import matplotlib.pyplot as plt

# Crear un grafo vacío

G = nx.Graph()

# Listas de estaciones por línea (esto es un ejemplo simplificado)

linea_1 = ["Observatorio", "Tacubaya", "Juanacatlán", "Chapultepec", "Sevilla", "Insurgentes", "Cuauhtémoc", "Balderas", "Salto del Agua", "Isabel la Católica", "Pino Suárez", "Merced", "Candelaria", "San Lázaro", "Moctezuma", "Balbuena", "Boulevard Puerto Aéreo", "Gómez Farías", "Zaragoza", "Pantitlán"]

linea_2 = ["Cuatro Caminos", "Panteones", "Tacuba", "Cuitláhuac", "Popotla", "Colegio Militar", "Normal", "San Cosme", "Revolución", "Hidalgo", "Bellas Artes", "Allende", "Zócalo", "Pino Suárez", "San Antonio Abad", "Chabacano", "Viaducto", "Xola", "Villa de Cortés", "Nativitas", "Portero", "Ermita", "General Anaya", "Tasqueña"]

#estos dataset se tienen que hacer uno por cada línea del metro

# Agregar conexiones (aristas) a cada línea

conexiones_1 = [(linea_1[i], linea_1[i + 1]) for i in range(len(linea_1) - 1)]

conexiones_2 = [(linea_2[i], linea_2[i + 1]) for i in range(len(linea_2) - 1)]

# Agregar nodos y aristas al grafo

G.add_nodes_from(linea_1)

G.add_nodes_from(linea_2)

G.add_edges_from(conexiones_1)

G.add_edges_from(conexiones_2)

# Definir posiciones de los nodos para una visualización mejorada

pos = nx.spring_layout(G, seed=42)

# Dibujar la línea 1 en rojo

nx.draw_networkx_nodes(G, pos, nodelist=linea_1, node_color='red', label='Línea 1')

nx.draw_networkx_edges(G, pos, edgelist=conexiones_1, edge_color='red')

# Dibujar la línea 2 en azul

nx.draw_networkx_nodes(G, pos, nodelist=linea_2, node_color='blue', label='Línea 2')

nx.draw_networkx_edges(G, pos, edgelist=conexiones_2, edge_color='blue')

# Dibujar etiquetas de los nodos

nx.draw_networkx_labels(G, pos, font_size=8)

# Mostrar leyenda

plt.legend(scatterpoints=1)

# Mostrar el grafo

plt.title("Red de Metro de la Ciudad de México")

plt.show()

Si lo que requieren es agregar todas las líneas del metro, pueden hacerlo de la pagina de Datos CDMX

Les comparto la liga del vídeo explicando la ejecución del programa.

Espero que esté ejemplo les haya servido para comprender mejor el concepto de grafos y como pueden desarrollarlo en Python.