Calcul de la valeur de débit maximale avec des réseaux pour un graphe orienté

Question

J'ai un réseau dirigé de 27000 arcs, chacun avec un poids.

Avec le code:

G=nx.Graph(G) 
nx.maximum_flow(G,'CHN',"CHL") 

Je reçois l'erreur:

NetworkXUnbounded: Infinite capacity path, flow unbounded above.

Est-ce que quelqu'un sait comment obtenir la valeur de débit maximal?

D'ailleurs, quand je lance: G.edges(data=True), je reçois un dictionnaire avec des trucs comme ça en elle:

('BGR', 'NCL', {'Edge Id': u'3727', 'weight': 334716.84}), 
('BGR', 'ARE', {'Edge Id': u'3606', 'weight': 28347011.33}), 
('BGR', 'ARG', {'Edge Id': u'3733', 'weight': 26294089.16}), 
('BGR', 'SDN', {'Edge Id': u'3591', 'weight': 78929738.06}), 

Merci.

Answer 1

Ce n'est pas beaucoup d'informations pour travailler avec.

Mais je suis assez sûr que la raison est simple: vous n'avez pas défini de capacités. Il est évident que il n'y a pas de limite supérieure sur le flux car nous pouvons pousser une quantité infinie de flux à travers le graphique! (Car aucune capacité explicite est interprétée comme capacité infinie)

Excerpt from the docs:

capacity (string)

Edges of the graph G are expected to have an attribute capacity that indicates how much flow the edge can support. If this attribute is not present, the edge is considered to have infinite capacity. Default value: ‘capacity’.

Une remarque: vous résoudre le problème du maximum de flux ici. Il n'y a pas d'utilisation de poids! Ceux-ci sont pour max-flow-min-coût et co. (également supporté par networkx).