1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/demo/csp_demo.cc	Mon Feb 12 17:54:36 2007 +0000
     1.3 @@ -0,0 +1,84 @@
     1.4 +/* -*- C++ -*-
     1.5 + *
     1.6 + * This file is a part of LEMON, a generic C++ optimization library
     1.7 + *
     1.8 + * Copyright (C) 2003-2006
     1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    1.11 + *
    1.12 + * Permission to use, modify and distribute this software is granted
    1.13 + * provided that this copyright notice appears in all copies. For
    1.14 + * precise terms see the accompanying LICENSE file.
    1.15 + *
    1.16 + * This software is provided "AS IS" with no warranty of any kind,
    1.17 + * express or implied, and with no claim as to its suitability for any
    1.18 + * purpose.
    1.19 + *
    1.20 + */
    1.21 +
    1.22 +///\ingroup demos
    1.23 +///\file
    1.24 +///\brief Demonstrating the usage of LEMON's Dijkstra algorithm
    1.25 +///
    1.26 +/// Dijkstra's algorithm computes shortest paths between two nodes in
    1.27 +/// a graph with edge lengths. Here we only show some of the
    1.28 +/// facilities supplied by our implementation: for the detailed
    1.29 +/// documentation of the LEMON Dijkstra class read \ref lemon::Dijkstra "this".
    1.30 +///
    1.31 +/// \include dijkstra_demo.cc
    1.32 +
    1.33 +#include <iostream>
    1.34 +#include <lemon/list_graph.h>
    1.35 +#include <lemon/csp.h>
    1.36 +#include <lemon/random.h>
    1.37 +
    1.38 +
    1.39 +using namespace lemon;
    1.40 +
    1.41 +
    1.42 +int main (int, char*[])
    1.43 +{
    1.44 +
    1.45 +    typedef ListGraph Graph;
    1.46 +    typedef Graph::Node Node;
    1.47 +    typedef Graph::Edge Edge;
    1.48 +    typedef Graph::EdgeIt EdgeIt;
    1.49 +    typedef Graph::EdgeMap<double> LengthMap;
    1.50 +
    1.51 +    Graph g;
    1.52 +
    1.53 +    const int N=100;
    1.54 +    const int M=20000;
    1.55 +    std::vector<Node> nodes;
    1.56 +    std::vector<Edge> edges;
    1.57 +    
    1.58 +    for(int i=0;i<N;i++) nodes.push_back(g.addNode());
    1.59 +
    1.60 +    for(int i=0;i<M;i++)
    1.61 +      edges.push_back(g.addEdge(nodes[rnd[N]],nodes[rnd[N]]));
    1.62 +    
    1.63 +    LengthMap cost(g);
    1.64 +    LengthMap delay(g);
    1.65 +    for(EdgeIt e(g);e!=INVALID;++e)
    1.66 +      {
    1.67 +	cost[e]=0.01+rnd(.99);
    1.68 +	delay[e]=0.01+rnd(.99);
    1.69 +      }
    1.70 +    
    1.71 +    ConstrainedShortestPath<Graph,LengthMap,LengthMap> csp(g,cost,delay);
    1.72 +    for(double d=0;d<2;d+=.01)
    1.73 +      {
    1.74 +	double lo_bo;
    1.75 +	std::cout << d << ": ";
    1.76 +	SimplePath<Graph> r = csp.larac(nodes[0],nodes[1],d,lo_bo);
    1.77 +	if(r.empty()) std::cout << "INFEASIBLE\n";
    1.78 +	else std::cout << "delay: " << csp.delay(r)
    1.79 +		       << " cost: " << csp.cost(r)
    1.80 +		       << " (lb: " << lo_bo
    1.81 +		       << " gap: " << csp.cost(r)-lo_bo
    1.82 +		       << " , " << (csp.cost(r)-lo_bo)/csp.cost(r)*100
    1.83 +		       << "%)" << std::endl;
    1.84 +      }
    1.85 +    			
    1.86 +    return 0;
    1.87 +}