LEDA Guide: Example MIN_COST

> LEDA Guide > Graph Algorithms > Minimum Cost Flow > Example MIN_COST_FLOW()

Example of How to Use `MIN_COST_FLOW()`

The following program shows how the function MIN_COST_FLOW() can be used to compute a minimum cost flow in a directed graph.

Remark: The graph algorithms in LEDA are generic, that is, they accept graphs as well as parameterized graphs.

We first create a simple graph G with four nodes and five edges. We define node_array<int> supply to store the supply/demand values of the nodes of G. We use edge_array<int> lcap, ucap, cost to store the lower bounds and the upper bounds of the edge capacities, and the costs on the edges of G, respectively.

#include <LEDA/graph/graph.h>
#include <LEDA/graph/min_cost_flow.h>

using namespace leda;

int main()
{
  graph G; 

  node n0=G.new_node(); node n1=G.new_node();
  node n2=G.new_node(); node n3=G.new_node();
  
  edge e0=G.new_edge(n0,n1); edge e1=G.new_edge(n1,n2);
  edge e2=G.new_edge(n2,n0); edge e3=G.new_edge(n2,n3);
  edge e4=G.new_edge(n0,n3);

  node_array<int> supply(G);
  supply[n0]=4; supply[n1]=3; supply[n2]=-2; supply[n3]=-5;

  edge_array<int> lcap(G), ucap(G), cost(G);
  lcap[e0]=0; ucap[e0]=1; cost[e0]=1;
  lcap[e1]=2; ucap[e1]=4; cost[e1]=2;
  lcap[e2]=0; ucap[e2]=5; cost[e2]=1;
  lcap[e3]=1; ucap[e3]=2; cost[e3]=3;
  lcap[e4]=4; ucap[e4]=9; cost[e4]=2;

For the result of MIN_COST_FLOW() the edge_array<int> flow is defined . MIN_COST_FLOW() returns true if it found a feasible flow for G, lcap, ucap, cost, and supply and false otherwise. In our example true is returned and the result is printed. There is a second variant of MIN_COST_FLOW() that can be used if lcap[e]=0 for all edges e of G. It has an interface very similar to that of the first variant. The only difference is that lcap is missing.

  edge_array<int> flow(G);
  //first variant
  bool found_feasible_flow=MIN_COST_FLOW(G,lcap,ucap,cost,supply,flow);

  //second variant
  //bool found_feasible_flow=MIN_COST_FLOW(G,ucap,cost,supply,flow);
  
  if (found_feasible_flow) {
    int flowcost=0;
    edge e;
    forall_edges(e,G) {
      G.print_edge(e);
      std::cout << " cap: [" << lcap[e] << "," << ucap[e] << "]";
      std::cout << " cost: " << cost[e];
      std::cout << " flow: " << flow[e] << std::endl;
      flowcost+=(flow[e]*cost[e]);
    }

    std::cout << "The cost of this flow is: " << flowcost << std::endl;
  }

  else std::cout << "No feasible flow!" << std::endl;

  return 0;
}

Example of How to Use MIN_COST_FLOW()

See also:

Example of How to Use `MIN_COST_FLOW()`