Instantly share code, notes, and snippets.

andrewandrepowell/mcfp_cf_itermaxflow_lemon.cc

Last active October 24, 2016 19:34
Show Gist options
• Save andrewandrepowell/5188040c9f784654fde4f4b167c286b6 to your computer and use it in GitHub Desktop.
Solves the Concurrent Flow variant of the Multi-Commodity Flow Problem with an iterative algorithm, which breaks down the problem into Maximum Flow Problems.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 /** * @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 #include #include #include #include #include #include #include /* 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; }
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 /** * @file mcfp_cf_itermaxflow_lemon.h * @author Andrew Powell * @date Oct 9, 2016 * * @brief Contains the declarations. */ template using Set = std::vector; 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 Bounds; typedef Graph::NodeMap Supplies; typedef int Commodity; typedef Set Commodities; typedef std::map Sources; typedef std::map Sinks; typedef std::map Demands; typedef std::map,Flow> Flows; typedef lemon::Circulation Circ; typedef Circ::Traits::FlowMap FlowMap; typedef std::string Label; typedef Graph::NodeMap