Calcolo del flusso massimo in un grafo in Python

Provo a calcolare il flusso massimo in un grafo usando il modulo networkx di Python.

Il flusso massimo è la quantità massima di flusso che posso inviare da un nodo sorgente verso un nodo di destinazione in un digrafo.

Importo il modulo networkx in memoria.

import networkx as nx

Definisco un grafo orientato

G = nx.DiGraph()

Aggiungo gli archi del digrafo indicando per ciascuno la sua capacità massima

G.add_edge('A', 'B', capacity=4)
G.add_edge('B', 'C', capacity=3)
G.add_edge('C', 'A', capacity=2)
G.add_edge('A', 'D', capacity=2)
G.add_edge('B', 'D', capacity=3)
G.add_edge('B', 'E', capacity=4)
G.add_edge('D', 'E', capacity=3)

Poi visualizzo il grafo con le capacità

import matplotlib.pyplot as plt
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_size=700, node_color='lightblue')
labels = nx.get_edge_attributes(G, 'capacity')
nx.draw_networkx_edge_labels(G, pos, edge_labels=labels)
plt.show()

Ecco il digrafo con le capacità indicate su ciascun arco.

Per calcolare il flusso massimo tra due nodi uso la funzione maximum_flow() di networkx.

Specifico come nodo seorgente il nodo A e come nodo di destinazione il nodo E.

Quindi, calcolo il flusso massimo da A a E

flow_value, flow_dict = nx.maximum_flow(G, 'A', 'E')
print(f"Flusso massimo da A a E: {flow_value}")
print("Dettaglio del flusso su ciascun arco:")
for u, v in flow_dict.items():
    print(f"{u} -> {v}")

Il risultato mostra il valore del flusso massimo e il flusso su ciascun arco. Ecco un esempio del risultato atteso:

Flusso massimo da A a E: 6
Dettaglio del flusso su ciascun arco:
A -> {'B': 4, 'D': 2}
B -> {'C': 0, 'D': 0, 'E': 4}
C -> {'A': 0}
D -> {'E': 2}
E -> {}

Il flusso massimo è 6 perché dal nodo A posso mandare 4 unità di flusso verso il nodo B e 2 unità di flusso verso il nodo D.

• A->B: 4
• A->D: 2

Dal nodo B posso inviare tutte le 4 unità verso il nodo E perché la capacità dell'arco (B,E)=4 lo consente

• B->E: 4

Dal nodo D posso inviare tutte le 2 unità verso il nodo E, perché la capacità dell'arco (D,E)=3 è superiore.

• D->E: 2

Complessivamente, al nodo destinazione E arrivano 4+2=6 unità di flusso.

Quando si calcola il flusso massimo in un grafo con networkx è importante avere ben definite le capacità sugli archi, altrimenti il calcolo non ha senso.

E così via.