Biblioteca de corte mínimo de flujo máximo para Python

Question

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

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

Bounty: Estoy ofreciendo una recompensa en esta pregunta para ver si la situación ha cambiado desde que se hizo esta pregunta. ¡Puntos de bonificación si tienes experiencia personal con la biblioteca que recomiendas!

Answer 1

He usado graph-tool 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 (a.k.a. las redes). Incluso tienen una excelente documentación sobre max-flow algorithms.

algoritmos Actualmente gráfico-herramienta soportes dado:

• Edmonds-Karp - Calcular el flujo máximo en el gráfico con el algoritmo de Edmonds-Karp.
• Reetiquetado a presión - Calcule el flujo máximo en el gráfico con el algoritmo push-relabel.
• Boykov Kolmogorov - Calcule el flujo máximo en el gráfico con el algoritmo Boykov-Kolmogorov.

Ejemplo tomado de docs: find maxflow using 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") 

I ejecutado este ejemplo con al azar gráfico dirigido (nodos = 4,000, vértices = 23964), todo proceso tomó justo 11 segundos.

bibliotecas alternativas:

• igraph - implementado principalmente en C, pero tiene Python y la interfaz R
• Vinculado tema "Python packages for graph theory"
• u otras herramientas de gráfico seleccionado en Sage wiki.

Answer 2

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

Answer 3

Para un buen rendimiento, puede intentar reformular su problema como un Integer Linear Program, cualquiera de las herramientas ILP estándar debería proporcionarle un rendimiento más que adecuado.

Wikipedia contiene una buena lista de tales fuentes comerciales y de código abierto tools, 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 de forma considerable en los últimos años y he encontrado que es suficiente escribir simplemente la entrada en lp_solve como plain text files e invocar lp_solve con el intérprete de comandos. Pensando en el pasado, probablemente debería haber invertido un poco más de esfuerzo para lograr que las vinculaciones de python oficiales para lp_solve funcionen.