Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Solves the Concurrent Flow variant of the Multi-Commodity Flow Problem with an iterative algorithm, which breaks down the problem into Maximum Flow Problems.
/**
* @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;
}
/**
* @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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment