Minimum cost flow using C++ Lemon library. CapacityScaling implements the capacity scaling version of the successive shortest path algorithm for finding a minimum cost flow amo93networkflows, edmondskarp72theoretical

min_cost.cc

#include <iostream>
#include <lemon/smart_graph.h>
#include <lemon/lgf_reader.h>
#include <lemon/lgf_writer.h>
#include <lemon/capacity_scaling.h>

using namespace lemon;

int main() {
    SmartDigraph g;
    SmartDigraph::ArcMap<int> cap(g);
    SmartDigraph::ArcMap<int> cost(g);
    SmartDigraph::ArcMap<int> flow(g);
    SmartDigraph::Node s, t;

  try {
        digraphReader(g, "digraph.lgf"). // read the directed graph into g
        arcMap("capacity", cap).       // read the 'capacity' arc map into cap
        arcMap("cost", cost).          // read 'cost' for for arcs
        node("source", s).             // read 'source' node to s
        node("target", t).             // read 'target' node to t
        run();
    } catch (Exception& error) { // check if there was any error
        std::cerr << "Error: " << error.what() << std::endl;
        return -1;
    }

    std::cout << "A digraph is read from 'digraph.lgf'." << std::endl;
    std::cout << "Number of nodes: " << countNodes(g) << std::endl;
    std::cout << "Number of arcs: " << countArcs(g) << std::endl;

    CapacityScaling<SmartDigraph> cs(g);

    // First run
    cs.upperMap(cap).costMap(cost).stSupply(s, t, 100).run();

    std::cout << "Total cost: " << cs.totalCost<double>() << std::endl;

    std::cout << "We can write it to the standard output:" << std::endl;

    cs.flowMap(flow);

    digraphWriter(g).                  // write g to the standard output
        arcMap("capacity", cap).       // write cap into 'capacity'
        arcMap("cost", cost).          // write 'cost' for for arcs
        arcMap("flow", flow).          // write 'flow' for for arcs
        node("source", s).             // write s to 'source'
        node("target", t).             // write t to 'target'
        run();

    return 0;
}

@nodes
label
0
1
2
3
4
5
6
7
@arcs
label capacity cost
0 1 0 16 1
0 2 1 12 1
0 3 2 20 2
1 2 3 10 1
1 4 4 10 4
1 5 5 13 1
2 3 6 10 1
2 4 7 8 3
2 6 8 8 1
5 3 9 20 1
3 6 10 25 1
4 7 11 15 6
5 7 12 15 1
6 7 13 18 1
@attributes
source 0
target 7

<- digraph.lgf

    label   capacity    cost    flow    

0 1 0 16 1 16
0 2 1 12 1 12
0 3 2 20 2 14
1 2 3 10 1 0
1 4 4 10 4 4
1 5 5 13 1 13
2 3 6 10 1 0
2 4 7 8 3 8
2 6 8 8 1 4
5 3 9 20 1 0
3 6 10 25 1 14
4 7 11 15 6 12
5 7 12 15 1 13
6 7 13 18 1 18