Solving the Maximum Flow Problem with LEMON Preflow Algorithm

Lemon_Preflow.cpp

#include <lemon/smart_graph.h>
#include <lemon/lgf_reader.h>
#include <lemon/lgf_writer.h>
#include <lemon/list_graph.h>
#include <lemon/cycle_canceling.h>

#include <lemon/preflow.h>

using namespace lemon;
typedef ListDigraph Graph;
typedef int LimitValueType;

void flowPreflow()
{
// example from http://en.wikipedia.org/wiki/Max_flow
//     o--->q
//    /|    |\
//   / |    | \
//  s  |    |  t
//   \ |    | /
//    \|    |/
//     p--->r
	Graph g;

	// source and sink vertices
	Graph::Node s = g.addNode(), t = g.addNode();

	// a and b
	Graph::Node o = g.addNode(), p = g.addNode(), q = g.addNode(), r = g.addNode();

	Graph::Arc so = g.addArc(s, o), sp = g.addArc(s, p),
			   op = g.addArc(o, p), oq = g.addArc(o, q),
			   pr = g.addArc(p, r), qr = g.addArc(q, r),
			   rt = g.addArc(r, t), qt = g.addArc(q, t);

	std::vector<Graph::Arc> arcs = { so, sp, op, oq, pr, qr, rt, qt };

	ListDigraph::ArcMap<LimitValueType> capacity(g);
	capacity[so] = 3; capacity[sp] = 3;
	capacity[oq] = 3; capacity[op] = 2;
	capacity[pr] = 2; capacity[qr] = 4;
	capacity[qt] = 2; capacity[rt] = 3;

	/**
	 * calculate max flow via preflows
	 */
	Preflow<Graph> preflow(g, capacity, s, t);

	preflow.run();

	std::cout << "maximum flow by preflow: " << preflow.flowValue() << std::endl;

	// print graph details
	digraphWriter(g).                 			 // write g to the standard output
			arcMap("cap", capacity).        	 // write 'cost' for for arcs
			arcMap("flow", preflow.flowMap()).   // write 'flow' for for arcs
			node("source", s).            		 // write s to 'source'
			node("target", t).            		 // write t to 'target'
			run();

}