/* -*- 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;

}