alpar@2360: /* -*- C++ -*-
alpar@2360:  *
alpar@2360:  * This file is a part of LEMON, a generic C++ optimization library
alpar@2360:  *
alpar@2360:  * Copyright (C) 2003-2006
alpar@2360:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@2360:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@2360:  *
alpar@2360:  * Permission to use, modify and distribute this software is granted
alpar@2360:  * provided that this copyright notice appears in all copies. For
alpar@2360:  * precise terms see the accompanying LICENSE file.
alpar@2360:  *
alpar@2360:  * This software is provided "AS IS" with no warranty of any kind,
alpar@2360:  * express or implied, and with no claim as to its suitability for any
alpar@2360:  * purpose.
alpar@2360:  *
alpar@2360:  */
alpar@2360: 
alpar@2360: ///\ingroup demos
alpar@2360: ///\file
alpar@2360: ///\brief Demonstrating the usage of LEMON's Dijkstra algorithm
alpar@2360: ///
alpar@2360: /// Dijkstra's algorithm computes shortest paths between two nodes in
alpar@2360: /// a graph with edge lengths. Here we only show some of the
alpar@2360: /// facilities supplied by our implementation: for the detailed
alpar@2360: /// documentation of the LEMON Dijkstra class read \ref lemon::Dijkstra "this".
alpar@2360: ///
alpar@2360: /// \include dijkstra_demo.cc
alpar@2360: 
alpar@2360: #include <iostream>
alpar@2360: #include <lemon/list_graph.h>
alpar@2360: #include <lemon/csp.h>
alpar@2360: #include <lemon/random.h>
alpar@2360: 
alpar@2360: 
alpar@2360: using namespace lemon;
alpar@2360: 
alpar@2360: 
alpar@2360: int main (int, char*[])
alpar@2360: {
alpar@2360: 
alpar@2360:     typedef ListGraph Graph;
alpar@2360:     typedef Graph::Node Node;
alpar@2360:     typedef Graph::Edge Edge;
alpar@2360:     typedef Graph::EdgeIt EdgeIt;
alpar@2360:     typedef Graph::EdgeMap<double> LengthMap;
alpar@2360: 
alpar@2360:     Graph g;
alpar@2360: 
alpar@2360:     const int N=100;
alpar@2360:     const int M=20000;
alpar@2360:     std::vector<Node> nodes;
alpar@2360:     std::vector<Edge> edges;
alpar@2360:     
alpar@2360:     for(int i=0;i<N;i++) nodes.push_back(g.addNode());
alpar@2360: 
alpar@2360:     for(int i=0;i<M;i++)
alpar@2360:       edges.push_back(g.addEdge(nodes[rnd[N]],nodes[rnd[N]]));
alpar@2360:     
alpar@2360:     LengthMap cost(g);
alpar@2360:     LengthMap delay(g);
alpar@2360:     for(EdgeIt e(g);e!=INVALID;++e)
alpar@2360:       {
alpar@2360: 	cost[e]=0.01+rnd(.99);
alpar@2360: 	delay[e]=0.01+rnd(.99);
alpar@2360:       }
alpar@2360:     
alpar@2360:     ConstrainedShortestPath<Graph,LengthMap,LengthMap> csp(g,cost,delay);
alpar@2360:     for(double d=0;d<2;d+=.01)
alpar@2360:       {
alpar@2360: 	double lo_bo;
alpar@2360: 	std::cout << d << ": ";
alpar@2360: 	SimplePath<Graph> r = csp.larac(nodes[0],nodes[1],d,lo_bo);
alpar@2360: 	if(r.empty()) std::cout << "INFEASIBLE\n";
alpar@2360: 	else std::cout << "delay: " << csp.delay(r)
alpar@2360: 		       << " cost: " << csp.cost(r)
alpar@2360: 		       << " (lb: " << lo_bo
alpar@2360: 		       << " gap: " << csp.cost(r)-lo_bo
alpar@2360: 		       << " , " << (csp.cost(r)-lo_bo)/csp.cost(r)*100
alpar@2360: 		       << "%)" << std::endl;
alpar@2360:       }
alpar@2360:     			
alpar@2360:     return 0;
alpar@2360: }