LEDA Guide: Example MIN_COST_MAX

Algorithmic Solutions > LEDA > LEDA Guide > Graph Algorithms > Minimum Cost Flow > Example MIN_COST_MAX_FLOW()

Example of How to Use `MIN_COST_MAX_FLOW()`

The following program shows how the function MIN_COST_MAX_FLOW() can be used to compute a minimum cost maximum 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 use edge_array<int> cap, cost to store the edge capacities and the costs on the edges of G, respectively. For the result of MIN_COST_MAX_FLOW() the edge_array<int> flow is defined . MIN_COST_MAX_FLOW() returns the value of the minimum cost maximum flow from s to t in G, with respect to cap, cost,.

#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);

  edge_array<int> cap(G), cost(G);
  cap[e0]=1; cost[e0]=1; cap[e1]=4; cost[e1]=2;
  cap[e2]=5; cost[e2]=1; cap[e3]=2; cost[e3]=3;
  cap[e4]=9; cost[e4]=2;
  
  edge_array<int> flow(G);
  int flowvalue=MIN_COST_MAX_FLOW(G,n1,n3,cap,cost,flow);
 
  int flowcost=0;
  edge e;forall_edges(e,G) {
    G.print_edge(e);
    std::cout << " cap: " << cap[e] << " 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;

  return 0;
}

Example of How to Use MIN_COST_MAX_FLOW()

See also:

Example of How to Use `MIN_COST_MAX_FLOW()`