Tag Archives: grafo

Implementazione Java di un algoritmo per il problema del massimo flusso su grafo

Recentemente ho dovuto implementare un algoritmo per il calcolo del massimo flusso su grafo per un progetto universitario. Il problema da risolvere era il calcolo del massimo flusso inviabile da un nodo sorgente (source node) a un nodo pozzo (sink node) utilizzando il grafo, oppure solo una parte di esso. C’era infatti la necessità di calcolare il massimo flusso al variare del sottografo indotto da un certo insieme dei nodi.

L’algoritmo doveva andare a integrarsi in un progetto più grande, quindi oltre ai requisiti di efficienza c’era la necessità di costruire una soluzione strutturata e modulare.

Algoritmo per il massimo flusso utilizzato

L’algoritmo che ho scelto di implementare è Improved shortest augmenting path di Ahuja e Orlin. Ho scelto questo algoritmo dopo aver visto che è risultato il più performante in un’analisi sperimentale degli algoritmi per il massimo flusso su grafo condotta da TopCoder.

Questo algoritmo si basa sulle idee di minimo cammino aumentante e etichette di distanza (distance label). L’algoritmo prevede, in generale, di cercare iterativamente il più breve cammino aumentante sulla rete residuale del grafo, e di terminare quando vengono soddisfatte alcune condizioni sulle distance label.

Nella figura seguente è riportato lo pseudocodice dell’algoritmo (fonte: TopCoder). Il nodo sorgente è indicato con s e il nodo pozzo con t.

improved-shortest-augmenting-path-alg

Dato un grafo, l’algoritmo inizialmente costruisce la rete residuale associata. Per ottenere una rete residuale, vengono aggiunti dei back-edge: per ogni arco (i, j) viene aggiunto un arco (j, i) con capacità e flusso nulli.

Sempre nella fase iniziale, viene effettuata una pre-etichettatura dei nodi del grafo. Ad ogni nodo i viene associata una distance label d[i] che rappresenta la lunghezza, in termini di numero di nodi, del cammino minimo tra i e il nodo pozzo nella rete residuale, con d[t] = 0. Quest’etichettatura è implementata mediante una visita in ampiezza al contrario del grafo, che parte dal nodo pozzo.

Se durante le iterazioni dell’algoritmo, la distance label associata al nodo s diventa maggiore o uguale al numero dei nodi del grafo, non ci potrà più essere un cammino aumentante nella rete residuale; questo è il principale criterio di terminazione dell’algoritmo.
Un arco (i, j) è definito ammissibile se d[i] = d[j] + 1. Se un cammino è costituito da archi ammissibili, e ciascun arco ha una capacità residua rij > 0, quel cammino è il più breve cammino aumentante tra s e t.

L’algoritmo si compone di 4 procedure principali: il ciclo principale, la procedura di advance, la procedura di retreat, e la procedura di augment. Nel ciclo principale, l’algoritmo cerca iterativamente di costruire un cammino aumentante da s a t, utilizzando archi ammissibili.

Se dal nodo corrente è possibile prendere un arco uscente ammissibile, viene effettuata una advance, mediante la quale viene aggiornato il cammino e il nodo corrente. Se si raggiunge il nodo t viene effettuato l’augment, che calcola l’incremento di flusso del cammino, aggiorna il grafo, e reimposta il nodo s come nodo corrente.

Se, al contrario, non ci sono archi uscenti ammissibili dal nodo corrente, viene effettuata l’operazione retreat, che retrocede il costruendo cammino aumentante al nodo precedente e incrementa la distance label del nodo corrente.

L’algoritmo prevede inoltre un criterio di terminazione aggiuntivo. Durante le iterazioni dell’algoritmo, si tiene traccia della distribuzione dei valori delle distance label sui nodi. Quando, nell’aggiornamento delle etichette, si incrementa la distance label di un nodo, si verifica se il numero di nodi che hanno associato il valore precedente dell’etichetta scende a 0: in questo caso, c’è la garanzia che non potrà più esistere un cammino aumentante nel grafo, e l’algoritmo termina.

Implementazione Java

Per implementare la soluzione è stato necessario innanzitutto progettare il grafo, che è la struttura dati sulla quale l’algoritmo esegue. Ho implementato un grafo orientato adatto ai problemi di flusso, con archi di capacità limitata. Il grafo è rappresentato internamente mediante liste di adiacenza e di incidenza; questo permette di navigare il grafo più facilmente: per un nodo è possibile richiedere, oltre alla lista degli archi adiacenti, anche quella degli archi incidenti. Questo consente di ottimizzare alcune operazioni che verranno eseguite dall’algoritmo max flow.

Nei diagrammi seguenti viene mostrata la struttura e le relazioni dei 5 moduli del progetto: l’interfaccia Graph e le classi FlowGraph, Node, Edge, e MaxFlowCalculator.

class-node-edgeLe classi Edge e Node rappresentano gli archi e i nodi del grafo. Per gli archi vengono modellati, con valori double, la capacità e il flusso. I nodi sono rappresentati da un id intero e un’etichetta (stringa).

graph-interfaceL’interfaccia del grafo (di cui FlowGraph è un’implementazione concreta) prevede i principali metodi per la manipolazione e la navigazione della struttura, oltre a:

  • un metodo clone() che restituisce una copia “profonda” del grafo;
  • i metodi setSource(Node) e setSink(Node) per specificare quali sono i nodi sorgente e pozzo;
  • un metodo getSubGraph(Set<Integer> s) che restituisce il sottografo indotto da un certo sottoinsieme di nodi (id) e dai nodi source e sink.

L’algoritmo max flow è stato implementato nella classe MaxFlowCalculator. Questa classe, come rappresentato nel diagramma successivo, espone un unico metodo pubblico e statico double getMaxFlow(Graph) che calcola e restituisce il valore del massimo flusso sul grafo in input.

maxflowcalculator

I vari passi dell’algoritmo sono stati implementati in metodi privati separati per ragioni di chiarezza. Le etichette di distanza vengono gestite da una classe DistanceLabels, che fornisce i metodi per ottenere e impostare le etichette dei nodi, e tiene traccia della loro distribuzione (questo è utile per implementare il criterio di terminazione secondario dell’algoritmo).

Esempio di utilizzo

Vediamo come è possibile usare questa libreria di classi per calcolare il massimo flusso su un semplice grafo di test, riportato nella figura seguente:

graph

 Si tratta di un grafo di flusso con 7 nodi e 12 archi; il nodo a è la sorgente e il nodo b il pozzo. Vediamo innanzitutto come costruire il grafo:

private static Graph buildTestGraph()
{
    Graph graph = new FlowGraph();

    Node na = new Node(0, "A");
    Node n1 = new Node(1, "N1");
    Node n2 = new Node(2, "N2");
    Node n3 = new Node(3, "N3");
    Node n4 = new Node(4, "N4");
    Node n5 = new Node(5, "N5");
    Node nb = new Node(6, "B");

    graph.addNode(na);
    graph.setSource(na);
    
    graph.addNode(n1);
    graph.addNode(n2);
    graph.addNode(n3);
    graph.addNode(n4);
    graph.addNode(n5);
    
    graph.addNode(nb);
    graph.setSink(nb);

    graph.addEdge(new Edge(na, n1, 3));
    graph.addEdge(new Edge(na, n3, 5));
    graph.addEdge(new Edge(na, n2, 3));
    graph.addEdge(new Edge(n1, n3, 4));
    graph.addEdge(new Edge(n1, n4, 3));
    graph.addEdge(new Edge(n3, n4, 2));
    graph.addEdge(new Edge(n3, nb, 1));
    graph.addEdge(new Edge(n3, n5, 4));
    graph.addEdge(new Edge(n2, n3, 2));
    graph.addEdge(new Edge(n2, n5, 2));
    graph.addEdge(new Edge(n4, nb, 4));
    graph.addEdge(new Edge(n5, nb, 4));

    return graph;
}

Ora vediamo come calcolare il massimo flusso inviabile tra a e b utilizzando l’intero grafo:

// costruisci il grafo di test
Graph g = buildTestGraph();
    
// calcola il massimo flusso tra sorgente e pozzo su g
double f = MaxFlowCalculator.getMaxFlow(g);
System.out.println("max flow on g = " + f);
// stampa la distribuzione di flusso di g
System.out.println("flow distribution on g = " + g.getEdges());

L’output è:

max flow on g = 9.0
flow distribution on g = [(0, 1) [3.0 / 3.0], (0, 3) [5.0 / 5.0], (0, 2) [1.0 / 3.0], (1, 3) [0.0 / 4.0], (1, 4) [3.0 / 3.0], (2, 3) [0.0 / 2.0], (2, 5) [1.0 / 2.0], (3, 4) [1.0 / 2.0], (3, 6) [1.0 / 1.0], (3, 5) [3.0 / 4.0], (4, 6) [4.0 / 4.0], (5, 6) [4.0 / 4.0]]

Il massimo flusso inviabile tra a e b utilizzando l’intera rete è quindi 9. In output viene stampata anche la distribuzione di flusso (attraverso il metodo getEdges() del grafo). Vediamo ora come cambia il massimo flusso se si utilizza solo una parte del grafo di test.

Il sottografo indotto dai nodi 1, 3 e 4 è il seguente:

graph-134

Questo sottografo è ottenuto dal grafo di test originale, eliminando i nodi 2, 5, e gli archi associati. Segue il codice per ottenere il sottografo e calcolare il massimo flusso:

// calcola il massimo flusso tra sorgente e pozzo utilizzando il
// sottografo indotto dai nodi 1, 3 e 4
Set<Integer> s134 = new HashSet<Integer>();
s134.add(1);
s134.add(3);
s134.add(4);
Graph g134 = buildTestGraph().getSubGraph(s134);
double f134 = MaxFlowCalculator.getMaxFlow(g134);
System.out.println("max flow on g[1, 3, 4] = " + f134);
System.out.println("flow distribution on g[1, 3, 4] = " +
    g134.getEdges());

Per ottenere il sottografo è necessario utilizzare il metodo getSubGraph del grafo, al quale va passato come parametro un insieme di id di nodi (in questo caso 1, 3 e 4). L’output ottenuto è:

max flow on g[1, 3, 4] = 5.0
flow distribution on g[1, 3, 4] = [(0, 1) [3.0 / 3.0], (0, 3) [2.0 / 5.0], (1, 3) [0.0 / 4.0], (1, 4) [3.0 / 3.0], (3, 4) [1.0 / 2.0], (3, 6) [1.0 / 1.0], (4, 6) [4.0 / 4.0]]

Utilizzando una rete più piccola, il massimo flusso inviabile è inferiore. Consideriamo infine un caso limite, nel quale non è possibile avere flusso tra i due nodi. Il sottografo indotto dal nodo 2 è:

graph-2

In questo caso non esiste un cammino tra la sorgente e il pozzo, quindi ci si aspetta che il flusso sia nullo. Il codice è molto simile ai casi precedenti:

Set<Integer> s2 = new HashSet<Integer>();
s2.add(2);
Graph g2 = buildTestGraph().getSubGraph(s2);
double f2 = MaxFlowCalculator.getMaxFlow(g2);
System.out.println("max flow on g[2] = " + f2);
System.out.println("flow distribution on g[2] = " + g2.getEdges());

Il risultato ottenuto è:

max flow on g[2] = 0.0
flow distribution on g[2] = [(0, 2) [0.0 / 3.0]]

Download codice sorgente