SciPy Estructura de Grafos

La estructura de grafos es uno de los marcos más poderosos en el estudio de algoritmos.

Un grafo es una colección de nodos y aristas que representan diversas relaciones; los nodos son vértices que corresponden a objetos, y las aristas son conexiones entre objetos.

SciPy proporciona el módulo scipy.sparse.csgraph para trabajar con estructuras de grafos.

Matriz de adyacencia

La matriz de adyacencia (Adjacency Matrix) es una matriz que representa las relaciones de adyacencia entre los vértices.

La estructura lógica de la matriz de adyacencia se divide en dos partes: los conjuntos V y E, donde V son los vértices, E son las aristas. Las aristas a veces tienen pesos, que indican la intensidad de la conexión entre los nodos.

Se utiliza un arreglo unidimensional para almacenar los datos de todos los vértices del grafo, y un arreglo bidimensional para almacenar los datos de las relaciones entre vértices (aristas o arcos); este arreglo bidimensional se denomina matriz de adyacencia.

Vea el ejemplo de la siguiente figura:

Los vértices son A, B, C; los pesos de las aristas son 1 y 2.

A y B están conectados, con un peso de 1.

A y C están conectados, con un peso de 2.

C y B no están conectados.

Esta matriz de adyacencia se puede representar como el siguiente arreglo bidimensional:
     A B C
   A:[0 1 2]  
   B:[1 0 0]
   C:[2 0 0]

La matriz de adyacencia se divide además en matriz de adyacencia de grafo dirigido y matriz de adyacencia de grafo no dirigido.

El grafo no dirigido tiene relaciones bidireccionales; las aristas no tienen dirección:

Las aristas del grafo dirigido tienen dirección; son relaciones unidireccionales:

Nota:El nodo D en las dos figuras anteriores es un bucle; un bucle se refiere a que ambos extremos de una arista son el mismo nodo.

Componentes conectados

Para ver todos los componentes conectados se usa el método connected_components().

Ejemplo

import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

arr = np.array([
  [0, 1, 2],
  [1, 0, 0],
  [2, 0, 0]
])

newarr = csr_matrix(arr)

print(connected_components(newarr))

El resultado del código anterior es:

(1, array([0, 0, 0], dtype=int32))

Dijkstra -- Algoritmo de camino más corto

El algoritmo de camino más corto de Dijkstra se utiliza para calcular el camino más corto desde un nodo a todos los demás nodos.

Scipy utiliza el método dijkstra() para calcular el camino más corto desde un elemento a otros elementos.

El método dijkstra() puede configurar los siguientes parámetros:
  1. return_predecessors:Un valor booleano; si se establece en True, recorre todos los caminos; si no se desea recorrer todos los caminos, se puede establecer en False.
  2. indices:El índice del elemento; devuelve todos los caminos de ese elemento.
  3. limit:El peso máximo del camino.

Ejemplo

Encuentra el camino más corto del elemento 1 al elemento 2:

import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

arr = np.array([
  [0, 1, 2],
  [1, 0, 0],
  [2, 0, 0]
])

newarr = csr_matrix(arr)

print(dijkstra(newarr, return_predecessors=True, indices=0))

El resultado del código anterior es:

(array([ 0.,  1.,  2.]), array([-9999,     0,     0], dtype=int32))

Floyd Warshall -- Algoritmo de Floyd-Warshall

El algoritmo de Floyd-Warshall es un algoritmo que resuelve el camino más corto entre cualquier par de puntos.

Scipy utiliza el método floyd_warshall() para encontrar el camino más corto entre todos los pares de elementos.

Ejemplo

Encuentra el camino más corto entre todos los pares de elementos:

import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

arr = np.array([
  [0, 1, 2],
  [1, 0, 0],
  [2, 0, 0]
])

newarr = csr_matrix(arr)

print(floyd_warshall(newarr, return_predecessors=True))

El resultado del código anterior es:

(array([[ 0.,  1.,  2.],
       [ 1.,  0.,  3.],
       [ 2.,  3.,  0.]]), array([[-9999,     0,     0],
       [    1, -9999,     0],
       [    2,     0, -9999]], dtype=int32))

Bellman Ford -- Algoritmo de Bellman-Ford

El algoritmo de Bellman-Ford es un algoritmo que resuelve el camino más corto entre cualquier par de puntos.

Scipy utiliza el método bellman_ford() para encontrar el camino más corto entre todos los pares de elementos. Generalmente se puede usar en cualquier grafo, incluidos grafos dirigidos y grafos con aristas de peso negativo.

Ejemplo

Usando un grafo con aristas de peso negativo, encuentra el camino más corto desde el elemento 1 al elemento 2:

import numpy as np
from scipy.sparse.csgraph import bellman_ford
from scipy.sparse import csr_matrix

arr = np.array([
  [0, -1, 2],
  [1, 0, 0],
  [2, 0, 0]
])

newarr = csr_matrix(arr)

print(bellman_ford(newarr, return_predecessors=True, indices=0))

El resultado del código anterior es:

(array([ 0., -1.,  2.]), array([-9999,     0,     0], dtype=int32))

Orden de recorrido en profundidad

El método depth_first_order() devuelve el orden del recorrido en profundidad desde un nodo.

Puede aceptar los siguientes parámetros:

  • grafo
  • El elemento del grafo desde el cual comienza el recorrido.

Ejemplo

Dada una matriz de adyacencia, devuelve el orden del recorrido en profundidad:

import numpy as np
from scipy.sparse.csgraph import depth_first_order
from scipy.sparse import csr_matrix

arr = np.array([
  [0, 1, 0, 1],
  [1, 1, 1, 1],
  [2, 1, 1, 0],
  [0, 1, 0, 1]
])

newarr = csr_matrix(arr)

print(depth_first_order(newarr, 1))

El resultado del código anterior es:

(array([1, 0, 3, 2], dtype=int32), array([    1, -9999,     1,     0], dtype=int32))

Orden de recorrido en amplitud

El método breadth_first_order() devuelve el orden del recorrido en amplitud desde un nodo.

Puede aceptar los siguientes parámetros:

  • grafo
  • El elemento del grafo desde el cual comienza el recorrido.

Ejemplo

Dada una matriz de adyacencia, devuelve el orden del recorrido en amplitud:

import numpy as np
from scipy.sparse.csgraph import breadth_first_order
from scipy.sparse import csr_matrix

arr = np.array([
  [0, 1, 0, 1],
  [1, 1, 1, 1],
  [2, 1, 1, 0],
  [0, 1, 0, 1]
])

newarr = csr_matrix(arr)

print(breadth_first_order(newarr, 1))

El resultado del código anterior es:

(array([1, 0, 2, 3], dtype=int32), array([    1, -9999,     1,     1], dtype=int32))
Otras extensiones