Bibliothèque min-cut à débit max rapide pour Python

Est-il fiable et bien documentée de la bibliothèque Python avec un rapide la mise en œuvre d'un algorithme qui trouve le maximum de flux et le minimum de coupes dans les graphes orientés?

pygraph.les algorithmes.minmax.maximum_flow de python-graph résout le problème, mais il est très lent: trouver max-flux et min-coupe dans un graphe orienté avec quelque chose comme 4000 nœuds et 11000 bords prend > 1 minute. Je suis à la recherche de quelque chose qui est au moins un ordre de grandeur plus rapide.

Bounty: je suis en offrant une prime sur cette question pour voir si la situation a changé depuis lors, cette question a été posée. Les points de Bonus si vous avez de l'expérience personnelle avec la bibliothèque vous recommander!

source d'informationauteur Jukka Suomela

  1. 17

    J'ai utilisé graphique de l'outil pour des tâches similaires.

    Graphique de l'outil est efficace d'un module python pour la manipulation et l'analyse statistique des graphes (un.k.un. les réseaux). Ils ont même une superbe documentation sur max débit d'algorithmes.

    Actuellement graphique de l'outil prend en charge compte tenu des algorithmes:

    • Edmonds-Karp - Calculer le maximum de flux sur le graphique avec le Edmonds-Karp algorithme.
    • Pousser le reclassement d' - Calculer le maximum de flux sur le graphique avec le push-reclassement de l'algorithme.
    • Boykov de Kolmogorov - Calculer le maximum de flux sur le graphique avec le Boykov-Kolmogorov algorithme.

    Exemple tiré de docs: trouver maxflow à l'aide de 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")

    J'ai signé cet exemple au hasard des graphes orientés(nodes=4000, sommets = 23964), tous les processus a pris seulement 11seconds.

    autres bibliothèques:

  2. 5

    Je ne sais pas si c'est plus rapide, vous aurez besoin de vérifier cela, mais avez-vous essayé networkx ?
    Semble comme il offre la la fonctionnalité vous êtes à la recherche pour et de mon expérience, il est très facile à utiliser la bibliothèque pour la manipulation de graphes.

  3. 0

    Pour des performances vraiment très bonne, vous pouvez essayer de reformuler votre problème comme un Programme Linéaire en nombres Entiers, de la norme ILP outils devrait vous donner plus de suffisamment de performance.

    Wikipédia contient une bonne liste de ces, à la fois commerciale et open source outilsdont beaucoup semblent avoir bindings python. Parmi les plus connus sont CPLEX et lp_solve.

    J'ai personnellement utilisé lp_solve raisonnablement fortement au cours des dernières années et a constaté qu'il suffisait de simplement écrire à lp_solve comme les fichiers de texte brut et invoquer lp_solve l'aide de l'environnement. En y repensant, je devrais probablement avoir investi un peu plus d'effort pour obtenir le officiel liaisons python pour lp_solve de travail.