Skip to content

Instantly share code, notes, and snippets.

@Zhouxing-Su

Zhouxing-Su/Lemon.MinCostFlow.NS.Sample.cpp

Last active December 31, 2022 16:57
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save Zhouxing-Su/6bb471f885dc29e5d25837abf78e7e5a to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save Zhouxing-Su/6bb471f885dc29e5d25837abf78e7e5a to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. Zhouxing-Su revised this gist Apr 8, 2017. No changes.
  2. Zhouxing-Su created this gist Apr 8, 2017.
    62 changes: 62 additions & 0 deletions Lemon.MinCostFlow.NS.Sample.cpp
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,62 @@
    #include <iostream>

    #include <lemon/smart_graph.h>
    #include <lemon/network_simplex.h>


    using namespace lemon;
    using namespace std;


    using Weight = int;
    using Capacity = int;

    using Graph = SmartDigraph;

    using Node = Graph::Node;
    using Arc = Graph::Arc;

    template<typename ValueType>
    using ArcMap = SmartDigraph::ArcMap<ValueType>;

    using NS = NetworkSimplex<SmartDigraph, Capacity, Weight>;


    int main() {
    Graph g;
    Node u = g.addNode();
    Node v = g.addNode();
    Arc a = g.addArc(u, v);
    Arc b = g.addArc(u, v);

    ArcMap<Weight> weights(g);
    weights[a] = 5;
    weights[b] = 2;

    ArcMap<Capacity> capacities(g);
    capacities[a] = 10;
    capacities[b] = 5;

    NS ns(g);
    ns.costMap(weights).upperMap(capacities).stSupply(u, v, 12);

    ArcMap<Capacity> flows(g);
    NS::ProblemType status = ns.run();
    switch (status) {
    case NS::INFEASIBLE:
    cerr << "insufficient flow" << endl;
    break;
    case NS::OPTIMAL:
    ns.flowMap(flows);
    cerr << "flow[a]=" << ns.flow(a) << " flow[b]=" << flows[b] << endl;
    cerr << "cost=" << ns.totalCost() << endl;
    break;
    case NS::UNBOUNDED:
    cerr << "infinite flow" << endl;
    break;
    default:
    break;
    }

    return 0;
    }