LEDA Guide: Example MIN

Algorithmic Solutions > LEDA > LEDA Guide > Graph Algorithms > Minimum Cut > Example MIN_CUT()

Example of How to Use `MIN_CUT()`

The following program shows how the function MIN_CUT() can be used to compute a minimum cut in a graph with non-negative edge weights.

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 five nodes and six edges. We use an edge_array<int> weight to store the weights of the edges of G. We define a list<node> cutto store the result of MIN_CUT(). Then we call MIN_CUT() for G, weight, and cut and output the resulting cut_value and the nodes of the cut.

#include <LEDA/graph/graph.h>
#include <LEDA/graph/min_cut.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();
  node n4=G.new_node();
  
  edge e0=G.new_edge(n0,n1); edge e1=G.new_edge(n0,n3);
  edge e2=G.new_edge(n0,n4); edge e3=G.new_edge(n1,n2);
  edge e4=G.new_edge(n1,n3); edge e5=G.new_edge(n2,n3);

  edge_array<int> weight(G);
  weight[e0]=1; weight[e1]=3; weight[e2]=3;
  weight[e3]=4; weight[e4]=1; weight[e5]=1;

  list<node> cut;
  int cut_value=MIN_CUT(G,weight,cut);

  std::cout << "The minimum cut has value: " << cut_value << std::endl;
  std::cout << "cut:"; node v; forall(v,cut) G.print_node(v);
  std::cout << std::endl;

  return 0;
}

Example of How to Use MIN_CUT()

See also:

Example of How to Use `MIN_CUT()`