Esta duda se puede abordar de diferentes formas, sin embargo te damos la que para nosotros es la solución más completa.
Solución:
He usado la herramienta gráfica para tareas similares.
Graph-tool es un módulo de Python eficiente para la manipulación y el análisis estadístico de gráficos (también conocidos como redes). Incluso tienen excelente documentación sobre algoritmos de flujo máximo.
Actualmente herramienta gráfica soporta algoritmos dados:
- Edmonds-Karp: calcule el flujo máximo en el gráfico con el algoritmo de Edmonds-Karp.
- Pulsar reetiquetado: calcule el flujo máximo en el gráfico con el algoritmo de pulsación de reetiquetado.
- Boykov Kolmogorov: calcule el flujo máximo en el gráfico con el algoritmo de Boykov-Kolmogorov.
Ejemplo tomado de documentos: encuentre maxflow usando Boykov-Kolmogorov:
>>> g = gt.load_graph("flow-example.xml.gz") #producing example is in doc
>>> cap = g.edge_properties["cap"]
>>> src, tgt = g.vertex(0), g.vertex(1)
>>> res = gt.boykov_kolmogorov_max_flow(g, src, tgt, cap)
>>> res.a = cap.a - res.a # the actual flow
>>> max_flow = sum(res[e] for e in tgt.in_edges())
>>> print max_flow
6.92759897841
>>> pos = g.vertex_properties["pos"]
>>> gt.graph_draw(g, pos=pos, pin=True, penwidth=res, output="example-kolmogorov.png")
Ejecuté este ejemplo con un gráfico dirigido al azar (nodos = 4000, vértices = 23964), todo el proceso tomó solo 11 segundos.
bibliotecas alternativas:
- igraph: implementado principalmente en C, pero tiene interfaz Python y R
- Tema vinculado “Paquetes de Python para teoría de grafos”
- u otras herramientas gráficas seleccionadas en Sage wiki.
No sé si es más rápido, tendrás que comprobarlo, pero ¿has probado networkx? Parece que ofrece la funcionalidad que está buscando y, según mi experiencia, es una biblioteca muy fácil de usar para manejar gráficos.
SciPy, a partir de 1.4.0, también tiene una implementación en scipy.sparse.csgraph.maximum_flow eso podría ser más fácil de usar como parte de su cadena de compilación (ya que el paquete está disponible a través de pip/conda).
Funciona manipulando matrices dispersas (por lo tanto scipy.sparse) que representa la matriz de adyacencia del gráfico, y como tal, la estructura de datos subyacente está cerca del metal, y con el propio algoritmo implementado en Cython, el rendimiento debe estar a la par con, por ejemplo, la herramienta gráfica.
Cómo se comparan las diferentes implementaciones con respecto al rendimiento siempre dependerá de la estructura del gráfico cuyo flujo máximo le interese, pero como punto de referencia simple, intenté ejecutar gráficos aleatorios con diferentes dispersos a través de NetworkX, graph-tool y SciPy . Todos ellos funcionan bien con matrices NumPy, así que para garantizar la igualdad de condiciones, creemos métodos para que cada uno de ellos tome como entradas matrices NumPy con forma (densidad * 1000 * 1000, 3) cuyas filas son bordes y cuyas columnas son los dos vértices incidentes a una arista dada, así como la capacidad de la arista.
import numpy as np
from scipy.sparse import rand
def make_data(density):
m = (rand(1000, 1000, density=density, format='coo', random_state=42)*100).astype(np.int32)
return np.vstack([m.row, m.col, m.data]).T
data01 = make_data(0.1)
data03 = make_data(0.3)
data05 = make_data(0.5)
Con esto, los diversos marcos pueden calcular el valor de un flujo máximo de la siguiente manera:
import graph_tool.all as gt
from scipy.sparse import coo_matrix, csr_matrix
from scipy.sparse.csgraph import maximum_flow
import networkx as nx
def networkx_max_flow(data, primitive):
m = coo_matrix((data[:, 2], (data[:, 0], data[:, 1])))
G = nx.from_numpy_array(m.toarray(), create_using=nx.DiGraph())
return nx.maximum_flow_value(G, 0, 999, capacity='weight', flow_func=primitive)
def graph_tool_max_flow(data, primitive):
g = gt.Graph()
cap = g.new_edge_property('int')
eprops = [cap]
g.add_edge_list(data, eprops=eprops)
src, tgt = g.vertex(0), g.vertex(999)
res = primitive(g, src, tgt, cap)
res.a = cap.a - res.a
return sum(res[e] for e in tgt.in_edges())
def scipy_max_flow(data):
m = csr_matrix((data[:, 2], (data[:, 0], data[:, 1])))
return maximum_flow(m, 0, 999).flow_value
Y con esto, los ejemplos de puntos de referencia de IPython se vuelven
%timeit networkx_max_flow(data01, nx.algorithms.flow.shortest_augmenting_path)
%timeit graph_tool_max_flow(data03, gt.push_relabel_max_flow)
%timeit scipy_max_flow(data05)
Entonces veo los siguientes resultados:
+----------------------------------------------+----------------+----------------+---------------+
| Algorithm | Density: 0.1 | Density: 0.3 | Density: 0.5 |
+----------------------------------------------+----------------+----------------+---------------+
| nx.algorithms.flow.edmonds_karp | 1.07s | 3.2s | 6.39s |
| nx.algorithms.flow.preflow_push | 1.07s | 3.27s | 6.18s |
| nx.algorithms.flow.shortest_augmenting_path | 1.08s | 3.25s | 6.23s |
| gt.edmonds_karp_max_flow | 274ms | 2.84s | 10s |
| gt.push_relabel_max_flow | 71ms | 466ms | 1.42s |
| gt.boykov_kolmogorov_max_flow | 79ms | 463ms | 895ms |
| scipy.sparse.csgraph.maximum_flow | 64ms | 234ms | 580ms |
+----------------------------------------------+----------------+----------------+---------------+
Nuevamente, los resultados dependerán de la estructura del gráfico, pero esto al menos sugiere que SciPy debería ofrecerle un rendimiento a la par con la herramienta gráfica.
Comentarios y valoraciones
Tienes la opción de añadir valor a nuestra información colaborando tu experiencia en las anotaciones.