Last active
June 18, 2019 16:01
-
-
Save fbaeuerlein/9464617 to your computer and use it in GitHub Desktop.
Solve the min cost flow circulation problem with Lemon CycleCanceling
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
#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 flowCycleCanceling() | |
{ | |
/** | |
* calculate min cost max flow via cycle canceling | |
* sample graph (arcs are dircted from left to right | |
* | |
* 2 5 | |
* / \ / \ | |
* / \ / \ | |
* 0 4--6--1 | |
* \ / \ / | |
* \ / \ / | |
* 3 7 | |
* | |
* vertex 0 represents the source, 1 target | |
* cost are set to 1, ecept for source and target arcs | |
* cost for (3,4) = 2 | |
*/ | |
Graph g; | |
// lower and upper bounds, cost | |
ListDigraph::ArcMap<LimitValueType> l_i(g), u_i(g), c_i(g); | |
// source and sink vertices | |
Graph::Node n0 = g.addNode(), n1 = g.addNode(); | |
// other nodes/vertices | |
Graph::Node n2 = g.addNode(), n3 = g.addNode(), n4 = g.addNode(), n5 = g.addNode(), | |
n6 = g.addNode(), n7 = g.addNode(); | |
Graph::Arc a02 = g.addArc(n0, n2), a03 = g.addArc(n0, n3), a24 = g.addArc(n2, n4), | |
a34 = g.addArc(n3, n4), a45 = g.addArc(n4, n5), a46 = g.addArc(n4, n6), | |
a47 = g.addArc(n4, n7), a51 = g.addArc(n5, n1), a61 = g.addArc(n6, n1), | |
a71 = g.addArc(n7, n1); | |
std::vector<Graph::Arc> arcs = { a02, a03, a24, a34, a45, a46, a47, a51, a61, a71 }; | |
// arcs for circulation! (source to target and vice versa) | |
Graph::Arc ts = g.addArc(n1, n0); | |
Graph::Arc st = g.addArc(n0, n1); | |
// graph must be finished before initializing cycle canceling ! | |
CycleCanceling<Graph, LimitValueType, LimitValueType> cycle(g); | |
// bounds for circulation arcs | |
l_i[ts] = 0; u_i[ts] = cycle.INF; c_i[ts] = 0; | |
l_i[st] = 0; u_i[ts] = cycle.INF; c_i[ts] = 0; | |
// set cost for arcs | |
for ( auto & a : arcs ) | |
{ | |
l_i[a] = 1; | |
u_i[a] = cycle.INF; | |
c_i[a] = (g.source(a) == n0|| g.target(a) == n1 ) ? 0 : 1; | |
} | |
c_i[a34] = 2; // arc (3,4) | |
//set lower/upper bounds, cost | |
cycle.lowerMap(l_i).upperMap(u_i).costMap(c_i); | |
CycleCanceling<Graph>::ProblemType ret = cycle.run(); | |
// get flow of arcs | |
ListDigraph::ArcMap<LimitValueType> flow(g); | |
cycle.flowMap(flow); | |
digraphWriter(g). // write g to the standard output | |
arcMap("cost", c_i). // write 'cost' for for arcs | |
arcMap("flow", flow). // write 'flow' for for arcs | |
arcMap("l_i", l_i). | |
arcMap("u_i", u_i). | |
node("source", n0). // write s to 'source' | |
node("target", n1). // write t to 'target' | |
run(); | |
switch ( ret ) | |
{ | |
case CycleCanceling<Graph>::INFEASIBLE: | |
std::cerr << "INFEASIBLE" << std::endl; | |
break; | |
case CycleCanceling<Graph>::OPTIMAL: | |
std::cerr << "OPTIMAL" << std::endl; | |
break; | |
case CycleCanceling<Graph>::UNBOUNDED: | |
std::cerr << "UNBOUNDED" << std::endl; | |
break; | |
} | |
// determine flow from source and flow to target | |
double flowToT = 0, flowToS = 0; | |
for (ListDigraph::ArcMap<LimitValueType>::ItemIt a(flow); a != INVALID; ++a) | |
{ | |
if ( g.target(a) == n1 ) | |
flowToT += cycle.flow(a); | |
if ( g.source(a) == n0 ) | |
flowToS += cycle.flow(a); | |
} | |
std::cerr << "flow to t = " << flowToT << " flow from s = " << flowToS << std::endl; | |
std::cerr << "total cost = " << cycle.totalCost<double>() << std::endl; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
I am looking for both lemon and min-cost circulation for days. Your script is fantastic!