Calcolo del flusso minimo di un grafo in Python

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

Per fare questo, ho bisogno di un grafo con capacità sugli archi e di utilizzare gli algoritmi di flusso massimo.

Il problema del flusso minimo può essere interpretato come un problema di flusso massimo su un grafo con capacità sugli archi invertite. Quindi, per calcolare il "flusso minimo" in un digrafo di solito si utilizza il "flusso massimo" in rete.

Prima di tutto importo il modulo networkx in memoria.

import networkx as nx

Creo un grafo orientato ossia un digrafo

G = nx.DiGraph()

Poi aggiungo gli archi indicando per ciascuno la sua capacità

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)

Per completezza 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.

Poiché mi interessa il calcolo del flusso minimo, devo invertire il verso degli archi con la funzione reverse()

GR = G.reverse()

Ora visualizzo il grafo inverso per completezza.

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

A questo punto, sul grafo inverso GR calcolo il flusso massimo tra due nodi usando la funzione maximum_flow() di networkx.

Specifico una sorgente e un pozzo (sink) nel grafo. Ad esempio, suppongo che 'A' sia la sorgente e 'E' sia il pozzo.

Quindi, calcolo il flusso massimo da A a E

flow_value, flow_dict = nx.maximum_flow(GR, '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: 0
Dettaglio del flusso su ciascun arco:
A -> {'C': 0}
B -> {'A': 0}
C -> {'B': 0}
D -> {'A': 0, 'B': 0}
E -> {'B': 0, 'D': 0}

Il flusso massimo rappresenta la quantità massima di flusso che può passare da una sorgente a un pozzo (o destinazione) in una rete di grafi, tenendo conto delle capacità degli archi, ovvero del limite massimo di flusso che ogni arco può sopportare.

In questo caso dal nodo A posso mandare 2 unità di flusso verso il nodo C ma non riuscirò mai a farle arrivare al nodo E.

Quindi, il flusso massimo da A a E nel grafo inverso GR è 0.

Questo vuol dire che il flusso minimo da A a E nel grafo G è 0. 

E così via.