/* -*- C++ -*-

  *

  * This file is a part of LEMON, a generic C++ optimization library

  *

  * Copyright (C) 2003-2006

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  *

  * Permission to use, modify and distribute this software is granted

  * provided that this copyright notice appears in all copies. For

  * precise terms see the accompanying LICENSE file.

  *

  * This software is provided "AS IS" with no warranty of any kind,

  * express or implied, and with no claim as to its suitability for any

  * purpose.

  *

  */

 ///\ingroup demos

 ///\file

 ///\brief Demonstrating the usage of LEMON's Dijkstra algorithm

 ///

 /// Dijkstra's algorithm computes shortest paths between two nodes in

 /// a graph with edge lengths. Here we only show some of the

 /// facilities supplied by our implementation: for the detailed

 /// documentation of the LEMON Dijkstra class read \ref lemon::Dijkstra "this".

 ///

 /// \include dijkstra_demo.cc

 #include <iostream>

 #include <lemon/list_graph.h>

 #include <lemon/csp.h>

 #include <lemon/random.h>

 using namespace lemon;

 int main (int, char*[])

 {

     typedef ListGraph Graph;

     typedef Graph::Node Node;

     typedef Graph::Edge Edge;

     typedef Graph::EdgeIt EdgeIt;

     typedef Graph::EdgeMap<double> LengthMap;

     Graph g;

     const int N=100;

     const int M=20000;

     std::vector<Node> nodes;

     std::vector<Edge> edges;

     for(int i=0;i<N;i++) nodes.push_back(g.addNode());

     for(int i=0;i<M;i++)

       edges.push_back(g.addEdge(nodes[rnd[N]],nodes[rnd[N]]));

     LengthMap cost(g);

     LengthMap delay(g);

     for(EdgeIt e(g);e!=INVALID;++e)

       {

 	cost[e]=0.01+rnd(.99);

 	delay[e]=0.01+rnd(.99);

       }

     ConstrainedShortestPath<Graph,LengthMap,LengthMap> csp(g,cost,delay);

     for(double d=0;d<2;d+=.01)

       {

 	double lo_bo;

 	std::cout << d << ": ";

 	SimplePath<Graph> r = csp.larac(nodes[0],nodes[1],d,lo_bo);

 	if(r.empty()) std::cout << "INFEASIBLE\n";

 	else std::cout << "delay: " << csp.delay(r)

 		       << " cost: " << csp.cost(r)

 		       << " (lb: " << lo_bo

 		       << " gap: " << csp.cost(r)-lo_bo

 		       << " , " << (csp.cost(r)-lo_bo)/csp.cost(r)*100

 		       << "%)" << std::endl;

       }

     return 0;

 }