Categories

# Successive shortest paths in C++

This solves the assignment problem by solving the associated minimum cost flow using the successive shortest paths method.

#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <limits>

using std::vector;

using node = int;
using edge = int;
using capacity = int;
using flow = int;
using cost = int;

struct Edge {
node from;   // from < 2^31
node to;     // to   < 2^31
cost c;      // cost < 2^31
capacity u;  // capacity < 2^31
flow f;      // flow <= capacity
};

// In an EdgeCollection we store both edges and their inverses.
// A edge is represented by an integer [0,edges.size) and its inverse edge
// by the negative minus one [-edges.size, 0).
class EdgeCollection {
public:
EdgeCollection(vector<Edge>& es): edges{es} {}

edge inverse(edge e) {
return -e-1;
}
node from(edge e) {
return e >= 0 ? edges[e].from : edges[inverse(e)].to;
}
node to(edge e) {
return e >= 0 ? edges[e].to : edges[inverse(e)].from;
}
cost get_cost(edge e) {
return e >= 0 ? edges[e].c : - edges[inverse(e)].c;
}
capacity capacity_left(edge e) {
return e >= 0 ? edges[e].u - edges[e].f : get_flow(inverse(e));
}
flow get_flow(edge e) {
return e >= 0 ? edges[e].f : capacity_left(inverse(e));
}
void augment(edge e, flow f) {
if(e >= 0) {
edges[e].f += f;
} else {
edges[inverse(e)].f -= f;
}
}
std::size_t size() {
return edges.size();
}
vector<Edge>& get_edges() {
return edges;
}
private:
vector<Edge> edges;
};

class AssignmentProblem {
public:
AssignmentProblem(int num_nodes, vector<Edge>& edges)
: ec(edges), pi(num_nodes + 2, 0), num_nodes{num_nodes}, s{num_nodes}, t{num_nodes + 1} {
// Since all the edges go from A to B,
// we can calculate the initial potential pi in linear time:
cost max = 0;
for(size_t i = 0; i < edges.size(); ++i) {
pi[edges[i].from] = - std::min( - pi[edges[i].from], edges[i].c);
max = - std::min(edges[i].c, - max);
}
pi[s] = max;
for(int i = 0; i < num_nodes/2; ++i) {
edges.push_back(Edge {s,i,0,1,0});
}
for(int i = num_nodes/2; i < num_nodes; ++i) {
edges.push_back(Edge {i,t,0,1,0});
}
ec = EdgeCollection(edges);
}

vector<Edge> succ_shortest_paths() {
for(int b_of_s = num_nodes/2; b_of_s > 0; --b_of_s) {
vector<int>  l(num_nodes + 2, std::numeric_limits<int>::max());
vector<bool> r(num_nodes + 2, false);
vector<edge> p(num_nodes + 2, -1);
l[s] = 0;
node next = s;
vector<vector<size_t>> incident(num_nodes + 2);
for(size_t i = 0; i < ec.size(); ++i) {
if(ec.capacity_left(i) > 0) {
incident[ec.from(i)].push_back(i);
}
if(ec.get_flow(i) > 0) {
incident[ec.to(i)].push_back(ec.inverse(i));
}
}
while(next != -1) { // Dijkstra
r[next] = true;

for(size_t i = 0; i < incident[next].size(); ++i) {
edge e = incident[next][i]; node w = ec.to(e);
cost c = l[next] + ec.get_cost(e) + pi[next] - pi[w];
if(!r[w] and l[w] > c) {
l[w] = c; p[w] = incident[next][i];
}
}

next = -1; cost min = std::numeric_limits<int>::max();
for(size_t i = 0; i < r.size(); ++i) {
if(!r[i] and l[i] < min) {
min = l[i];
next = i;
}
}
}

node w = t;
while(w != s) {
edge way = p[w];
ec.augment(way, 1); // In every iteration gamma will be 1.
w = ec.from(way);
}

for(size_t i = 0; i < pi.size(); ++i) {
pi[i] += l[i];
}
}
return ec.get_edges();
}
private:
EdgeCollection ec;
vector<int> pi;
int num_nodes;
node s, t;
};

void solve(int n, vector<Edge>& edges) {
AssignmentProblem ap(n, edges);
vector<Edge> f = ap.succ_shortest_paths();
int total_cost = 0;
for(size_t i = 0; i + n < f.size(); ++i) if(f[i].f == 1) total_cost += f[i].c;
std::cout << total_cost << std::endl;
for(size_t i = 0; i + n < f.size(); ++i) {
Edge e = f[i];
if(e.f == 1) {
std::cout << e.from << " " << e.to << std::endl;
}
}
}

int main(int argc, char *argv[]) {
if(argc != 2) {
// We expect exactly one argument...
std::cout << "Aufruf: " << argv[0] << " <filename>" << std::endl;
} else {
// which should be a filename...
std::ifstream file(argv[1]);
unsigned int n = 0;
vector<Edge> edges(0);
if(!file.is_open()) {
// of a non-busy file.
std::cout << "Konnte Datei nicht öffnen." << std::endl;
} else {
file >> n; // First we read the number of nodes...
node a, b; cost c;
while(file >> a >> b >> c) {
// and then the edges...
edges.push_back(Edge {a,b,c,1,0});
}
solve(n, edges);
}
}
}