Libreria min-cut veloce per Max-flow per Python

Question

Esiste una libreria Python affidabile e ben documentata con un'implementazione veloce di un algoritmo che trova i flussi massimi e i tagli minimi nei grafici diretti?

pygraph.algorithms.minmax.maximum_flow da python-graph risolve il problema ma è dolorosamente lento: trovare max-flussi e min-tagli in un grafico diretto con qualcosa come 4000 nodi e 11000 archi richiede> 1 minuto. Sto cercando qualcosa che sia almeno di un ordine di grandezza più veloce.

Bounty: Offro taglie su questa domanda per vedere se la situazione è cambiata da quando è stata posta questa domanda. Punti bonus se hai esperienza personale con la libreria che consigli!

Answer 1

Ho utilizzato graph-tool per attività simili.

Graph-tool è un modulo Python efficiente per la manipolazione e l'analisi statistica di grafici (reti a.k.a.). Hanno anche una documentazione superba su max-flow algorithms.

Attualmente grafico-strumento supporta dato algoritmi:

• Edmonds-Karp - Calcola flusso massimo sul grafico con l'algoritmo di Edmonds-Karp.
• Push relabel - Calcola il flusso massimo sul grafico con l'algoritmo push-relabel.
• Boykov Kolmogorov - Calcola il flusso massimo sul grafico con l'algoritmo Boykov-Kolmogorov.

Esempio tratto da documenti: 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") 

ho eseguito questo esempio con casuale grafo orientato (nodi = 4000, vertici = 23964), tutti i processi voluti solo 11 secondi .

librerie alternative:

• igraph - attuate principalmente in C, ma ha Python e l'interfaccia R
• Linked argomento "Python packages for graph theory"
• o altri strumenti di grafico selezionato in Sage wiki.

Answer 2

Non so se è più veloce, è necessario verificarlo, ma hai provato networkx? Sembra che offra lo functionality che stai cercando e dalla mia esperienza è una libreria molto facile da usare per la gestione dei grafici.

Answer 3

Per prestazioni davvero buone, è possibile provare a riformulare il problema come programma integer lineare, qualsiasi strumento ILP standard dovrebbe fornire prestazioni più che adeguate.

Wikipedia contiene un buon elenco di tali sia commerciali che open source tools, molti dei quali sembrano avere collegamenti Python. Tra i più noti sono CPLEX e lp_solve.

Personalmente ho usato lp_solve in modo ragionevolmente pesante negli ultimi anni e ho trovato sufficiente scrivere solo input su lp_solve come plain text files e invocare lp_solve utilizzando la shell. Ripensandoci, probabilmente avrei dovuto investire un po 'più di impegno per ottenere il binding ufficiale di python su lp_solve working.