program - Biblioteca de corte mínimo de flujo máximo rápido para Python

python graph theory

Question

¿Existe una biblioteca de Python confiable y bien documentada con una implementación rápida de un algoritmo que encuentre flujos máximos y cortes mínimos en gráficos dirigidos?

pygraph.algorithms.minmax.maximum_flow de python-graph resuelve el problema pero es terriblemente lento: encontrar flujos máximos y mínimos cortes en un gráfico dirigido con algo así como 4000 nodos y 11000 bordes toma> 1 minuto. Estoy buscando algo que sea al menos un orden de magnitud más rápido.

Recompensa : Estoy ofreciendo una recompensa por esta pregunta para ver si la situación ha cambiado desde que se hizo esta pregunta. ¡Puntos de bonificación si tiene experiencia personal con la biblioteca que recomienda!

Answer 1

He utilizado la herramienta gráfica para tareas similares.

Graph-tool es un módulo eficiente de Python para la manipulación y el análisis estadístico de gráficos (también conocidas como redes). Incluso tienen una excelente documentación sobre los algoritmos de flujo máximo .

Actualmente la herramienta gráfica soporta algoritmos dados:

• Edmonds-Karp: calcule el flujo máximo en el gráfico con el algoritmo de Edmonds-Karp.
• Etiqueta de inserción: calcule el flujo máximo en el gráfico con el algoritmo de etiqueta de inserción.
• 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 una interfaz Python y R
• Tema vinculado "Paquetes de Python para la teoría de grafos"
• u otras herramientas gráficas seleccionadas en Sage wiki .

Answer 2

No sé si es más rápido, tendrá que comprobarlo, pero ¿ha intentado networkx ? Parece que ofrece la functionality que estás buscando y, según mi experiencia, es una biblioteca muy fácil de usar para el manejo de gráficos.

Answer 3

Para obtener un rendimiento realmente bueno, puede intentar reformular su problema como un programa lineal integral, cualquiera de las herramientas ILP estándar debería ofrecerle un rendimiento más que adecuado.

Wikipedia contiene una buena lista de tales tools comerciales y de código abierto, muchas de las cuales parecen tener enlaces de python. Entre los más conocidos están CPLEX y lp_solve .

Personalmente he usado lp_solve bastante fuerte en los últimos años y encontré suficiente para escribir entradas en lp_solve como archivos de texto sin formato e invocar lp_solve usando el shell. Pensándolo bien, probablemente debería haber invertido un poco más de esfuerzo para hacer que los enlaces oficiales de python funcionen en lp_solve.