# | Likes | Tech tags | Title | Creator | Created date |
---|---|---|---|---|---|
1 | 0 |
2022-10-15 14:23
|
An \(O(UC nm^2)\) implementation of the Klein's cycle canceling algorithm (\(U\) is maximum absolute cost of an edge, \(C\) is maximum capacity of an edge, \(n\) is number of vertices, \(m\) is number of edges). In practical scenarios, performs much faster than the complexity estimate suggests. Uses Bellman–Ford algorithm to find negative cost cycles.
Solves the Min-Cost Flow problem. To turn it into a solution for the Min-Cost Max-Flow problem, just create an edge connecting your sink vertex to your source vertex with a cost lower than \(-Um\) and capacity greater than \(C\).
#include<vector>
#include<deque>
#include<limits>
#include<algorithm>
#include<iostream>
struct CycleCancellingFlowNetwork {
struct Arc {
int start_;
int end_;
int flow_;
int capacity_;
int cost_;
int get_dest(int from) { // Return the destination node if we were to traverse the arc from node `from`
if(from == start_) {
return end_;
} else {
return start_;
}
}
void add_flow(int from, int to_add) { // Adds flow from originating vertex `from`
if(from == start_) {
flow_ += to_add;
} else {
flow_ -= to_add;
}
}
int get_capacity(int from) { // Gets the capacity of the edge if the originating vertex is `from`
if(from == start_) {
return capacity_ - flow_;
} else {
return flow_;
}
}
int get_cost_from(int from) {
if(from == start_) {
return cost_;
} else {
return -cost_;
}
}
};
struct Node {
int index_;
std::vector<Arc*> connected_arcs_;
};
std::vector<Node> nodes_;
std::deque<Arc> arcs_;
void add_node() {
nodes_.push_back({int(nodes_.size()), {}});
}
void add_arc(int start, int end, int flow, int capacity, int cost) {
arcs_.push_back({start, end, flow, capacity, cost});
nodes_[start].connected_arcs_.push_back(&arcs_.back());
nodes_[end].connected_arcs_.push_back(&arcs_.back());
}
void cycle_cancel_min_flow() {
struct State {
int distance;
Arc* arc_traversed;
};
while(1) {
std::vector<std::vector<State> > state(1, std::vector<State>(nodes_.size(), {0, NULL}));
// Perform the Bellman–Ford algorithm to find a negative cost cycle
for(int level=0; level < (int)nodes_.size(); level++) {
state.push_back(state[level]); // Create next edge level
for(int i=0; i < (int)nodes_.size(); i++) {
if(level == 0 || state[level][i].distance < state[level-1][i].distance) { // Node is active?
for(Arc* arc : nodes_[i].connected_arcs_) {
if(arc->get_capacity(i) > 0) {
int next_distance = state[level][i].distance + arc->get_cost_from(i);
int next_i = arc->get_dest(i);
if(next_distance < state[level+1][next_i].distance) {
state[level+1][next_i].distance = next_distance;
state[level+1][next_i].arc_traversed = arc;
}
}
}
}
}
}
// Now identify the cycle
bool valid = false;
for(int i=0; i<(int)nodes_.size(); i++) {
// See if this node ends in a path of length n+1 (and thus has to contain a cycle)
if(state[(int)nodes_.size()-1][i].distance > state[(int)nodes_.size()][i].distance) {
std::vector<Arc*> path; // The path we traversed to get to our cycle
std::vector<bool> explr((int)nodes_.size(), false); // Nodes we have explored
int cur_i = i; // Index of current node
int cur_level = (int)nodes_.size(); // Current level in the Belleman-Ford computed matrix
int capacity = std::numeric_limits<int>::max(); // Maximum capacity in the cycle
valid = true;
while(!explr[cur_i]) {
State cur_state = state[cur_level][cur_i];
explr[cur_i] = true;
path.push_back(cur_state.arc_traversed);
cur_i = cur_state.arc_traversed->get_dest(cur_i); // Traverse backwards
cur_level--;
}
int initial_i = cur_i;
reverse(path.begin(), path.end());
for(int j=0; j == 0 || cur_i != initial_i; j++) {
capacity = std::min(capacity, path[j]->get_capacity(cur_i));
cur_i = path[j]->get_dest(cur_i); // Traverse forward
if(cur_i == initial_i) {
path.resize(j+1); // Cut out part of the path that exceeds the cycle
break;
}
}
for(auto arc : path) { // Push the flow through the cycle
arc->add_flow(cur_i, capacity);
cur_i = arc->get_dest(cur_i);
}
break;
}
}
if(!valid) return; // There are no longer any negative cycles
}
}
};
int main() {
CycleCancellingFlowNetwork graph;
for(int i=0; i<6; i++) graph.add_node(); // Initialize 6 nodes
// Add edges of our graph
graph.add_arc(0, 1, 4, 4, 1);
graph.add_arc(0, 3, 2, 2, 5);
graph.add_arc(1, 2, 2, 2, 1);
graph.add_arc(1, 3, 2, 6, 1);
graph.add_arc(2, 1, 0, 2, 0);
graph.add_arc(2, 5, 2, 4, 0);
graph.add_arc(3, 4, 4, 8, 1);
graph.add_arc(4, 2, 0, 6, -3);
graph.add_arc(4, 5, 4, 4, 1);
graph.cycle_cancel_min_flow(); // Do the cycle cancelling
int result = 0;
for(auto& arc : graph.arcs_) { // Calculate the cost of our flow
result += arc.cost_ * arc.flow_;
}
std::cout << result << '\n';
return 0;
}
Sample problem:
Minimum Cost Maximum Flow - hackerearth.com
Resources:
Minimum Cost Flow Part Two: Cycle-Canceling Algorithm - topcoder.com
objects | ||
std::cout |
en.cppreference.com | cplusplus.com |
classes | ||
std::deque |
en.cppreference.com | cplusplus.com |
std::numeric_limits |
en.cppreference.com | cplusplus.com |
std::vector |
en.cppreference.com | cplusplus.com |
functions | ||
std::basic_ostream::operator<< |
en.cppreference.com | cplusplus.com |
std::deque::push_back |
en.cppreference.com | cplusplus.com |
std::min |
en.cppreference.com | cplusplus.com |
std::numeric_limits::max |
en.cppreference.com | cplusplus.com |
std::reverse |
en.cppreference.com | cplusplus.com |
std::vector::operator[] |
en.cppreference.com | cplusplus.com |
std::vector::resize |
en.cppreference.com | cplusplus.com |
std::vector::size |
en.cppreference.com | cplusplus.com |
std::vector::vector |
en.cppreference.com | cplusplus.com |
Implement the Cycle canceling algorithm for finding a minimum-cost flow on some existing flow network. Construct a flow network and use your code to find some minimum-cost flow on it.
A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems (Morton Klein)
Min Cost Flow: Cycle Canceling Algorithm - cs.princeton.edu
Flow network - wikipedia.org