Solves the Concurrent Flow variant of the Multi-Commodity Flow Problem with an iterative algorithm, which breaks down the problem into Maximum Flow Problems.

mcfp_cf_itermaxflow_lemon.cc

/**
 * @file mcfp_cf_itermaxflow_lemon.cc
 * @author Andrew Powell
 * @date Oct 9, 2016
 *
 * @brief Solves the Concurrent Flow variant of the Multi-
 * Commodity Flow Problem.
 *
 * In this example, the Concurent Flow variant
 * of the Multi-Commodity Flow Problem is solved with
 * an iterative algorithm ( really a method ), where for each commodity,
 * the Maximum Flow Problem is solved and the capacities
 * of each arc are then updated accordingly. The method was based on
 * a similar approach from the following link.
 *
 * http://www.es.ele.tue.nl/~kgoossens/Stefan12PHD.pdf
 *
 * This problem can be formally formulated as the following. Say the flow network \f$G\f$
 * has the following form.
 *
\f{align*}{
G & = \text{Directed Graph} \\
& = (V,E) \\
V & = \text{Node Set} \\
E & = \text{Arc Set} \\
e & = (v_e\in V,w_e\in V,c_e\in \mathbf{R}_{\ge 0}) \\
& \in E \\
v_e & = \text{Source Node of $e\in E$} \\
w_e & = \text{Sink Node of $e\in E$} \\
c_{e} & = \text{Capacity ( Upper Bound ) of Arc $e\in E$}
\f}
 *
 * Let, the commodities \f$K\f$ have the following definition.
 *
\f{align*}{
K & = \text{Commodity Set} \\
k & = (s_k\in V,t_k\in V,d_k\in \mathbf{R}_{\ge 0}) \\
& \in K \\
s_k & = \text{Source Node of Commodity $k\in K$} \\
t_k & = \text{Sink Node of Commodity $k\in K$} \\
d_k & = \text{Demand of Commodity $k\in K$} \\
\f}
 *
 * Given a particular commodity \f$k\in K\f$ and the network \f$G\f$, the \f$\text{Maximum Flow Problem}\f$
 * is formalized as the following.
 *
\f{align*}{
\text{Maximize} & : \sum_{v\in V}f_{k,(s_k,v)} : k \in K \\
f_{k,e} & = \text{Flow of Commodity $k\in K$ on Edge $e\in E$} \\ \\
\text{Subject to:} & \\
\Delta_{k,v} & = \text{Net Flow of Arc $e\in E$ of Commodity $k\in K$.} \\
& = \sum_{w \in V} f_{k,(v,w)} - \sum_{w \in V} f_{k,(w,v)} \\
& = 0 : k \in K, \forall v \in \{ w \in V: w \neq s_k,t_k \} \\
& = d_k : k \in K, \forall v \in \{ w \in V: w = s_k \} \text{( Defined by Node Supply)}\\
& = -d_k : k \in K, \forall v \in \{ w \in V: w = t_k \} \text{( Defined by Node Supply)}\\
c_{e} & \ge f_{k,e}\ \ge 0 : k \in K, \forall e \in E \\
\f}
 *
 * The \f$\text{Maximum Flow Problem}\f$ is solved with the LEMON's implementation
 * of an algorithm that solves the network circulation problem. Details on the
 * LEMON implementation can be found from the following link:
 *
 * http://lemon.cs.elte.hu/pub/doc/1.2.3/a00533.html
 *
 * The iterative algorithm is finally described below.
 *
\f{algorithm}{
\caption{Calculate $f_{k,e}, \forall k\in K, \forall e\in E$}
\label{alg1}
\begin{algorithmic}
	\REQUIRE $c \ge 0, G, K $
	\ENSURE $f_{k,e} : \forall k\in K, \forall e\in E$
	\STATE $c_{k,e} \Leftarrow c_e : \forall k\in K$
	\WHILE{$|K|>0$}
		\STATE $k^* \Leftarrow \text{argmax}_{k\in K}\{d_k \}$
		\STATE $f_{k^*,e} \Leftarrow \text{Solve Maximum Flow Problem for Commodity $k^*$ and Graph $G$}$
		\STATE $c_{e} \Leftarrow c_{e}-f_{k^*,e} : \forall e\in E$
		\IF{$c_e < 0 : \exists e \in E$}
			\RETURN \FALSE
		\ENDIF
		\STATE $K \Leftarrow K - \{k^*\}$
	\ENDWHILE
	\RETURN \TRUE
\end{algorithmic}
\f}
 *
 * The following library is needed to compile and run this application:
 *
 * lemon
 *
 * Also noted that the -std=c++11 flag is needed, as well.
 *
 * In order to generate a tex file of this documented sources, the
 * following extra packages are necessary:
 *
 * amsmath
 * algorithm
 * algorithmic
 *
 * Cheers!
 */

#include <iostream>
#include <stdexcept>
#include <lemon/list_graph.h>
#include <lemon/circulation.h>
#include <utility>
#include <vector>
#include <map>
#include <string>

/* Just so this application looks cleaner
all the declarations are stored in the following
header file. */
#include "mcfp_cf_itermaxflow_lemon.h"

/**
 * @brief Creates directed graph, commodities, and
 * performs the iterative algorithm.
 */
int main()
try
{
	/* Define the graph. */
	Node A = addNode("A");
	Node B = addNode("B");
	Node C = addNode("C");
	addArc(A,B,1.0,"AB");
	addArc(B,C,1.0,"BC");
	addArc(C,A,1.0,"CA");

	/* Define the Commodities. */
	addCommodity(A,C,0.5,"k0");
	addCommodity(C,B,0.5,"k1");

	/* Execute iterative algorithm. Basically,
	solve the Maximum Flow problem for the
	remaining commodity whose demand is the highest.
	Repeat until there are no more remaining commodities. */
	Commodities rks( ks );
	while ( rks.size() )
	{
		/* Acquire commodity with largest demand. */
		Commodities::iterator ldk = rks.begin();
		for ( Commodities::iterator k=rks.begin();
				k!=rks.end(); ++k )
			if ( kds[*k]>kds[*ldk] )
				ldk = k;

		/* Generate the supply map. */
		Supplies s(g,0.0);
		Demand d = kds[*ldk];
		s[kss[*ldk]] = d;
		s[kts[*ldk]] = -d;

		/* Solve the Maximum Flow Problem for the
		current commodity. */
		FlowMap fm(g);
		Circ(g,bls,bus,s).flowMap(fm).run();

		/* Update the upper bounds and store flows. */
		for ( Graph::ArcIt a(g); a!=lemon::INVALID; ++a )
		{
			bus[a] -= fm[a];
			if ( bus[a]<0.0 )
				throw std::runtime_error( "Algorithm failed." );
			kfs[std::make_pair(*ldk,a)] = fm[a];
		}

		/* Remove commodity from the remaining commodities. */
		rks.erase(ldk);
	}

	/* Display the results. */
	displayResults();

	return 0;
}
catch ( std::exception& e )
{
	std::cerr << e.what() << std::endl;
}
catch (...)
{
	std::cerr << "A serious error occurred" << std::endl;
}

mcfp_cf_itermaxflow_lemon.h

/**
 * @file mcfp_cf_itermaxflow_lemon.h
 * @author Andrew Powell
 * @date Oct 9, 2016
 *
 * @brief Contains the declarations.
 */

template <typename T_> using Set = std::vector<T_>;
typedef double Weight;
typedef Weight Demand;
typedef Weight Capacity;
typedef Weight Flow;
typedef lemon::ListDigraph Graph;
typedef Graph::Node Node;
typedef Graph::Arc Arc;
typedef Graph::ArcMap<Capacity> Bounds;
typedef Graph::NodeMap<Demand> Supplies;
typedef int Commodity;
typedef Set<Commodity> Commodities;
typedef std::map<Commodity,Node> Sources;
typedef std::map<Commodity,Node> Sinks;
typedef std::map<Commodity,Demand> Demands;
typedef std::map<std::pair<Commodity,Arc>,Flow> Flows;
typedef lemon::Circulation<Graph,Bounds,Bounds,Supplies> Circ;
typedef Circ::Traits::FlowMap FlowMap;
typedef std::string Label;
typedef Graph::NodeMap<Label> NodeLabels;
typedef Graph::ArcMap<Label> ArcLabels;
typedef std::map<Commodity,Label> ComLabels;

Graph g;			/**< Defines the graph. */
Bounds bls(g,0.0);	/**< Defines the lower bound constraint on flow. */
Bounds bus(g,0.0);	/**< Defines the upper bound constraint on flow. */
Commodities ks;		/**< Defines the commodities. */
Sources kss;		/**< Defines the source nodes of the commodities. */
Sinks kts;			/**< Defines the sink nodes of the commodities. */
Demands kds;		/**< Defines the demands of the commodities. */
Flows kfs;			/**< Defines the flows of the commodities across the graph's arcs. */

NodeLabels nls(g);	/**< Defines the labels for the nodes. */
ArcLabels als(g);	/**< Defines the labels for the arcs. */
ComLabels kls;		/**< Defines the labels for the commodities. */

/** @brief Adds Node with corresponding label. */
Node addNode( Label l )
{
	Node n = g.addNode();
	nls[n] = l;
	return n;
}

/** @brief Adds Arc with corresponding capacity and label. */
Arc addArc( Node s, Node t, Capacity c, Label l )
{
	Arc a = g.addArc(s,t);
	bus[a] = c;
	als[a] = l;
	return a;
}

/** @brief Adds commodity with corresponding source node,
sink node, demand, and label. */
Commodity addCommodity( Node s, Node t, Demand d, Label l )
{
	Commodity k = ( ks.size() ) ? ks.back()+1 : 0;
	ks.push_back(k);
	kss[k] = s;
	kts[k] = t;
	kds[k] = d;
	kls[k] = l;
	return k;
}

/** @brief Displays the results after applying the solver. */
void displayResults()
{
	std::cout << "Displaying the flows..." << std::endl;
	for ( Commodities::iterator k=ks.begin(); k!=ks.end(); ++k )
	{
		std::cout << "For Commodity " << kls[*k] << "..." << std::endl;
		for ( Graph::ArcIt a(g); a!=lemon::INVALID; ++a )
			std::cout << "Arc " << als[a] << ": " <<
			kfs[std::make_pair(*k,a)] << std::endl;
	}
}