Implementierung und Visualisierung des Algorithmus von Ford-Fulkerson zur Berechnung eines maximalen (s, t)-Flusses in einem Netzwerk

Fabian Beck, Ansgar Jonietz
Softwarepraktikum C++, Wintersemester 2005/2006, Universität Trier

Aufgabe

Die Ermittlung eines maximalen Flusses in einem Graphen ist neben dem Kürzeste-Wege-Problem eine Standardaufgabe in der Graphentheorie. Ziel ist es, einen maximalen Fluss zwischen einem Start- und einem Zielknoten zu finden, so dass an keiner Kante die Kapazität überschritten wird. Unter Umständen existieren mehrere Möglichkeiten, die den gleichen Fluss haben – welche der Algorithmus wählt ist unerheblich.

Analog zum Maximalen-Fluss-Problem kann auch das Minimaler-Schnitt-Problem betrachtet werden, denn die Kapazität des minimalen Schnitts ist gerade der maximale Fluss des Graphen.

Anwendungen finden sich zum Beispiel bei der Modellierung verschiedener realer Netzwerke wie Datennetze, Verkehrsnetze usw. Auch in der Graphentheorie selbst wird bei Aufgabenstellungen wie der Bestimmung der Knoten- und Kantenzusammenhangszahl eines Graphen auf das Maximaler-Fluss/Minimaler-Schnitt-Problem zurückgegriffen.

Algorithmus

Eine Methode zur Bestimmung eines maximalen Flusses ist der Ford-Fulkerson-Algorithmus, er wurde 1956 von den amerikanischen Mathematikern Lester Randolph Ford und Delbert Ray Fulkerson veröffentlicht. Als Eingabe benötigt der Algorithmus einen gerichteten Graphen mit einer Kapazitätsfunktion, die jede Kante auf eine positive Zahl abbildet sowie den Startknoten s und den Zielknoten t.

Das Vorgehen des Ford-Fulkerson-Algorithmus lässt sich wie folgt beschreiben: ausgehend von der Annahme, dass der maximale Fluss 0 ist, wird der Graph mittels Tiefen- oder Breitensuche traversiert, um einen Weg zu finden, auf dem der Fluss noch erhöht werden kann. Ob dies der Fall ist, lässt sich einfach aus dem momentanen Fluss und der Kapazität der Kanten auf dem Weg ermitteln. Wurde ein solcher Weg gefunden, kann der (bisherige) maximale Fluss um die Kapazität dieses Weges erhöht werden. Wenn beim Durchmustern kein weiterer Weg gefunden wird, ist der Fluss maximal und der Algorithmus endet.

Implementierung

Für die Implementierung des Ford-Fulkerson-Algorithmus in C++ wurde auf die Klassenbibliothek LEDA zurückgegriffen – sie enthält zahlreiche algorithmische Grundstrukturen und ermöglicht damit ein effizientes Arbeiten mit Graphalgorithmen. So wird etwa Graphwin aus der LEDA-Bibliothek eingesetzt, das in einem grafischen Fenster einen Editor bereitstellt, mit dem ein Graph komfortabel bearbeitet und der Algorithmus visualisiert werden kann.

Für den Algorithmus selbst wurde eine Klasse MaxFlowGraph erstellt. Dem Konstruktor der Klasse wird als Parameter ein Zeiger auf das Graphwin übergeben, in dem sich der Eingabgegraph befindet und auch die Visualisierung durchgeführt werden soll. Dieser Zeiger wird als globale Variable in der Klasse abgelegt, weiterhin werden dort Start- und Zielknoten sowie Felder mit den Flüssen und Kapazitäten aller Kanten gespeichert.

Die Kapazitätswerte werden mit der Methode parseLabels aus den Labels der Kanten ausgelesen, dabei wird die Kapazität auch korrekt erkannt, wenn zusätzlich ein Fluss angegeben ist – etwa weil der Algorithmus schon einmal gelaufen ist. Umgekehrt werden die momentanen Fluss- und Kapazitätswerte durch die Methode updateLabels in die Labels zurückgeschrieben. Die Methode getSourceTarget ermittelt den Start- und Zielknoten aus der Auswahl im Graphwin.

Neben Konstruktor und Destruktor ist nur die Methode maxFlow als Public ausgezeichnet. Sie ermittelt mit Hilfe des Ford-Fulkerson-Algorithmus den maximalen Fluss durch den Graphen und gibt ihn als Ganzzahl zurück. Wie oben beschrieben wird dazu wiederholt ein Weg von s nach t gesucht, auf dem der Fluss erhöht werden kann – dies übernimmt die Methode findPath. Nachdem mit getCapacity ermittelt wurde, um welchen Wert der Fluss auf diesem Weg erhöht werden kann, ohne die Kapazitäten zu überschreiten, wird der maximale Fluss um diesen Wert erhöht. Zusätzlich wird mittels addCapacity der Fluss der einzelnen Kanten auf dem Weg entsprechend erhöht.

Parallel zum Algorithmus werden die einzelnen Schritte visualisert, etwa durch unterschiedliche Hintergrundfarben der Knoten je nach momentanem Status – weiteres dazu unten. Damit der Anwender den Schritten des Programmes folgen kann, werden je nach Kontext unterschiedlich lange Pausen eingefügt. Alle Werte wie Farben, Wartezeiten etc. sind am Anfang des Quelltextes via Präprozessor-Befehl definiert und können so zentral angepasst werden.

Bedienung

Nach dem Start des Programmes kann Graphwin-üblich ein Graph erstellt werden – neben der manuellen Eingabe ist es auch möglich, einen Graph aus einer Datei zu laden oder durch die Zufallsfunktion von Graphwin erzeugen zu lassen. Über das Kontextmenü der Kanten (Punkt label) können dann die Kapazitätswerte vergeben werden. Für Kanten mit leerem Label werden zufällige Kapazitäten zwischen 1 und 10 generiert. Die Funktion select im Kontextmenü der Knoten wird dazu genutzt, Start- und Zielknoten zu wählen: der erste selektierte Knoten wird als s interpretiert, der zweite als t.

Mit der Schaltfläche Done in der Graphwin-Menüleiste kann nun der Algorithmus gestartet werden. Start- und Zielknoten werden mit s und t beschriftet und optisch hervorgehoben.

Der Ablauf des Algorithmus wird farblich visualisiert und durch Erläuterungen am oberen Fensterrand beschrieben. So kann etwa die Breitensuche zur Suche eines neuen Weges optisch nachvollzogen werden: der aktive Knoten ist kräftig rot, bereits besucht Knoten dunkelrot, gefundene, aber noch nicht bearbeitete Knoten graugrün gekennzeichnet usw. Wenn ein Weg gefunden wurde, auf dem der Fluss erhöht werden kann, wird dieser grün hervorgehoben und die Kapazität ausgegeben. Ebenso werden auch die Kanten eingefärbt, an der Beschriftung der Kanten kann auch der momentane Fluss und die Kapazität abgelesen werden. Zusätzlich wird der Fluss durch eine Kante mit der Dicke der Linie angedeutet.

Wenn ein maximaler Fluss gefunden wurde, wird dies in einem Hinweisfenster mitgeteilt. Durch die Visualisierung des Flusses durch die Dicke der Kanten erschließt sich leicht, welche Wege der Fluss durch den Graphen genommen hat.

Bildschirmfotos

Bildschirmfoto: Suchen eines neuen Weges von s nach t Bildschirmfoto: Weg gefunden; erhöhe Fluss Bildschirmfoto: Algorithmus beendet

Quelltext

/**
 * Implementierung und Visualisierung des Algorithmus von Ford-Fulkerson 
 * zur Berechnung eines maximalen (s, t)-Flusses in einem Netzwerk
 * 
 * Fabian Beck, Ansgar Jonietz
 * Softwarepraktikum C++, Wintersemester 2005/2006, Universitaet Trier
 */

  
#include <LEDA/graphwin.h>
#include <LEDA/random_source.h>
#include <LEDA/panel.h>

// colors
#define COL_DEFAULT_NODE		color(255,255,255)
#define COL_DEFAULT_EDGE		color(0,0,0)
#define COL_ACTIVE 			color(255,0,0)
#define COL_VISITED_USED		color(200,120,120)
#define COL_VISITED_NOT_USED		color(200,200,200)
#define COL_SOON_ACTIVE			color(200,220,200)
#define COL_FOUND_PATH			color(0,220,0)

// sleep times
#define SLEEP_TIME			0.5
#define SLEEP_TIME_LONG			3.0

// pixel
#define MAX_EDGE_WIDTH			5

using namespace leda;


class MaxFlowGraph
{
	GraphWin* gw;			// graphwin
	node s, t;			// source, target
	edge_array<int> flow;		// flow
	edge_array<int> capacity;	// capacity

	int maxCapacity;		// maximum capacity of an edge

	void setGraphwin(GraphWin* graphwin)
	// set graphwin and initialize flow and capacity
	{
		gw = graphwin;
		flow.init(gw->get_graph());
		capacity.init(gw->get_graph());
	}
	
	int getSourceTarget()
	// use first two selected nodes as source and target
	{
		list<node> selection = gw->get_selected_nodes();

		if (selection.size()<2)
		{
			gw->message("Please select source and target nodes.");
			return 0;
		}
		else
		{
			gw->del_message();
			s = selection.pop_back();
			t = selection.pop_back();
			
			return 1;
		}
	}
	
	void updateSourceTargetView()
	// update shapes and labels of all nodes
	{
		node v;
		forall_nodes(v, gw->get_graph())
		{
			if (v == s || v == t)
				gw->set_shape(v, square_node);
			else 
			{
				gw->set_shape(v, circle_node);
				gw->set_label_type(v, index_label);
				gw->deselect(v);
			}
		}
		gw->set_label_type(s, user_label);
		gw->set_label_type(t, user_label);
		gw->set_user_label(s, "s");
		gw->set_user_label(t, "t");
	}

	void parseLabels()
	// parse labels and write result to flow[] and capacity[]
	{
		edge e;
		random_source S;
		maxCapacity = 0;
		forall_edges(e, gw->get_graph())
		{
			string label = gw->get_user_label(e);
			char *slash = strchr(label, '/');
			if (slash==NULL)
			{
				flow[e] = 0;
				if (label == "")
					capacity[e] = S(1, 10);
				else
					capacity[e] = atoi(label);
			}
			else
			{
				flow[e] = 0;
				capacity[e] = atoi(++slash);
			}
			if (capacity[e] > maxCapacity)
				maxCapacity = capacity[e];
		}
	}
	
	void updateLabels()
	// update labels with values from flow[] and capacity[]
	{
		edge e;
		forall_edges(e, gw->get_graph())
		{
			gw->set_user_label(e, string("%d / %d", flow[e], capacity[e]));
			gw->set_width(e, (int)(((double)flow[e]/(double)maxCapacity)*MAX_EDGE_WIDTH+1.99));
		}
		gw->update_graph();
	}
	
	list<edge> findPath()
	// search for a path from source to target (breadth first search)
	{		
		resetColoring();
		string message = "Searching for a new path from 's' to 't' (breadth first search).";
		list<node> nodeList;
		node_array<bool> label(gw->get_graph(), false);
		edge_array<bool> used(gw->get_graph(), false);
		node_array<edge> predEdge(gw->get_graph());
		label[s] = true;
		nodeList.push_back(s);
		bool stop = false;
		while (!nodeList.empty())
		{
			node v = nodeList.pop_front();
			gw->set_color(v, COL_ACTIVE);
			wait(message);
			edge e;
			forall_inout_edges(e, v) 
			{
				if (!used[e])
				{
					used[e] = true;
					gw->set_color(e, COL_ACTIVE);
					wait(message);
					if ((!label[target(e)] && flow[e] < capacity[e])
									|| (!label[source(e)] && flow[e] > 0)) 
					{
						node w;
						if (!label[target(e)])
							w = target(e);
						else
							w = source(e);
						gw->set_color(w, COL_SOON_ACTIVE);
						label[w] = true;
						nodeList.push_back(w);
						predEdge[w] = e;
						if (w == t)
							stop = true;
						gw->set_color(e, COL_VISITED_USED);
					}
					else
					{
						gw->set_color(e, COL_VISITED_NOT_USED);
					}
					wait(message);
				}
				if (stop == true)
					break;
			}
			gw->set_color(v, COL_VISITED_USED);
			if (stop == true)
				break;
		}
		resetColoring();
		list<edge> path;
		if (predEdge[t] != NULL) 
		{
			node v = t;
			gw->set_color(v, COL_FOUND_PATH);
			while (predEdge[v] != NULL) 
			{
				edge e = predEdge[v];
				path.push_front(e);
				v = target(e) == v ? source(e) : target(e);
				gw->set_color(e, COL_FOUND_PATH);
				gw->set_color(v, COL_FOUND_PATH);
			}
		}
		return path;
	}
	
	int getCapacity(list<edge> path)
	// return the free capacity value of the given path 
	{
		if (path.empty())
			return 0;
		edge e = path.pop();
		node v = target(e);
		int minFlow = capacity[e]-flow[e];
		while (!path.empty()) 
		{
			e = path.pop();
			int i;
			if (source(e) == v)
			{
				i = capacity[e]-flow[e];
				v = target(e);
			} 
			else
			{
				i = flow[e];
				v = source(e);
			}
			minFlow = i < minFlow? i : minFlow;
		}
		return minFlow;
	}
	
	void addCapacity(list<edge> path, int addFlow) 
	// add the flow value to the existing flow values along the path
	{
		if (path.empty())
			return;
		edge e;
		node v = s;
		while (!path.empty()) 
		{
			e = path.pop();
			if (source(e) == v)
			{
				flow[e] += addFlow;
				v = target(e);
			} 
			else
			{
				flow[e] -= addFlow;
				v = source(e);
			}
		}
		updateLabels();
	}
	
	void wait(string s) 
	// waiting for the animation to be continued
	{
		gw->wait(SLEEP_TIME, s);
	}
	
	void waitLong(string s) 
	// waiting long for the animation to be continued
	{
		gw->wait(SLEEP_TIME_LONG, s);
	}
	
	void resetColoring() 
	// reset colors to default values
	{
		edge e;
		forall_edges(e, gw->get_graph())
			gw->set_color(e, COL_DEFAULT_EDGE);	
		node v;
		forall_nodes(v, gw->get_graph())
			gw->set_color(v, COL_DEFAULT_NODE);
	}


	public:

	MaxFlowGraph(GraphWin* graphwin)
	// constructor
	{
		setGraphwin(graphwin);
		
		parseLabels();
		updateLabels();
	}
	
	~MaxFlowGraph()
	// destructor
	{
	}

	int maxFlow()
	// calculate the maximum flow from source to target
	{
		int capSum = 0;
		if (getSourceTarget()) 
		{
			updateSourceTargetView();
			list<edge> path;
			while (!(path = findPath()).empty())
			{
				waitLong("Path from 's' to 't' found.");
				int cap = getCapacity(path);
				capSum += cap;
				addCapacity(path, cap);
				waitLong(string("Increasing flow along the path. Additional flow is %d.", cap));
			}		
			panel p;
			p.text_item("Algorithm finished.");
			p.text_item(string("Maximum flow is %d.", capSum));
			p.button("Ok");
			gw->open_panel(p);
		}
		return capSum;
	}

};


int main()
{
	GraphWin gw("maxFlow");
	gw.display();
	while (gw.edit())
	{
		MaxFlowGraph mfg(&gw);
		mfg.maxFlow();
	}
}

Download

maxFlow.cpp – Quelltext
maxFlowLinux.gz – Ausführbare Datei für Linux (gzip-Archiv, 1157 kByte)
maxFlow.zip – Ausführbare Datei für Win32(gzip-Archiv, 1.5 MB)
graph.gw – Beispielgraph im Graphwin-Format

Fabian Beck, Ansgar Jonietz 16.02.2006