LEDA Guide: Example MINIMUM_RATIO

Algorithmic Solutions > LEDA > LEDA Guide > Graph Algorithms > Shortest Path Algorithms > Algorithm for Minimum Cost Ratio Cycle > Example MINIMUM_RATIO_CYCLE()

Example of `MINIMUM_RATIO_CYCLE()`

The following program shows how the function MINIMUM_RATIO_CYCLE() can be used.

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

In main() we first create a simple graph G with four nodes and six edges. We use an edge_array<int> cost to store the costs of the edges of G and an edge_array<int> profit to store the profit from every edge.

The list<edge> min_cycle is used for the result of MINIMUM_RATIO_CYCLE(). The rational returned is the ratio of the minimum cycle.

#include <LEDA/graph/graph.h>
#include <LEDA/graph/shortest_path.h>
#include <LEDA/numbers/rational.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,n3);
  edge e2=G.new_edge(n3,n0); edge e3=G.new_edge(n1,n2);
  edge e4=G.new_edge(n2,n3); edge e5=G.new_edge(n3,n1);
 
  edge_array<int> cost(G);
  cost[e0]=1; cost[e1]=2; cost[e2]=3;
  cost[e3]=2; cost[e4]=3; cost[e5]=4;

  edge_array<int> profit(G);
  profit[e0]=3; profit[e1]=2; profit[e2]=1;
  profit[e3]=1; profit[e4]=2; profit[e5]=3;
  
  list<edge> min_cycle;
  rational ratio=MINIMUM_RATIO_CYCLE(G,cost,profit,min_cycle);
 
  std::cout << "The minimum cost ratio cycle:" << std::endl;
  edge e;
  forall(e,min_cycle) G.print_edge(e);
  std::cout << std::endl << "has a cost-profit-ratio of " << ratio << std::endl;
	

  return 0;
}

Example of MINIMUM_RATIO_CYCLE()

See also:

Example of `MINIMUM_RATIO_CYCLE()`