demo/csp_demo.cc
author deba
Tue, 10 Jun 2008 11:36:17 +0000
changeset 2612 3d65053d01a3
parent 2391 14a343be7a5a
permissions -rw-r--r--
Bug fix initialization
The std::numeric_limits<double>::min() means the smallest positive number,
and not the smallest number in the whole range of double.
alpar@2360
     1
/* -*- C++ -*-
alpar@2360
     2
 *
alpar@2360
     3
 * This file is a part of LEMON, a generic C++ optimization library
alpar@2360
     4
 *
alpar@2553
     5
 * Copyright (C) 2003-2008
alpar@2360
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@2360
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@2360
     8
 *
alpar@2360
     9
 * Permission to use, modify and distribute this software is granted
alpar@2360
    10
 * provided that this copyright notice appears in all copies. For
alpar@2360
    11
 * precise terms see the accompanying LICENSE file.
alpar@2360
    12
 *
alpar@2360
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@2360
    14
 * express or implied, and with no claim as to its suitability for any
alpar@2360
    15
 * purpose.
alpar@2360
    16
 *
alpar@2360
    17
 */
alpar@2360
    18
alpar@2360
    19
///\ingroup demos
alpar@2360
    20
///\file
alpar@2367
    21
///\brief Demonstrating the usage of LEMON's algorithm for solving the
alpar@2367
    22
/// Constrained shortest Path Problem 
alpar@2360
    23
///
alpar@2367
    24
/// \include csp_demo.cc
alpar@2360
    25
alpar@2360
    26
#include <iostream>
alpar@2360
    27
#include <lemon/list_graph.h>
alpar@2360
    28
#include <lemon/csp.h>
alpar@2360
    29
#include <lemon/random.h>
alpar@2360
    30
alpar@2360
    31
alpar@2360
    32
using namespace lemon;
alpar@2360
    33
alpar@2360
    34
alpar@2360
    35
int main (int, char*[])
alpar@2360
    36
{
alpar@2360
    37
alpar@2360
    38
    typedef ListGraph Graph;
alpar@2360
    39
    typedef Graph::Node Node;
alpar@2360
    40
    typedef Graph::Edge Edge;
alpar@2360
    41
    typedef Graph::EdgeIt EdgeIt;
alpar@2360
    42
    typedef Graph::EdgeMap<double> LengthMap;
alpar@2360
    43
alpar@2360
    44
    Graph g;
alpar@2360
    45
alpar@2360
    46
    const int N=100;
alpar@2360
    47
    const int M=20000;
alpar@2360
    48
    std::vector<Node> nodes;
alpar@2360
    49
    std::vector<Edge> edges;
alpar@2360
    50
    
alpar@2360
    51
    for(int i=0;i<N;i++) nodes.push_back(g.addNode());
alpar@2360
    52
alpar@2360
    53
    for(int i=0;i<M;i++)
alpar@2360
    54
      edges.push_back(g.addEdge(nodes[rnd[N]],nodes[rnd[N]]));
alpar@2360
    55
    
alpar@2360
    56
    LengthMap cost(g);
alpar@2360
    57
    LengthMap delay(g);
alpar@2360
    58
    for(EdgeIt e(g);e!=INVALID;++e)
alpar@2360
    59
      {
alpar@2360
    60
	cost[e]=0.01+rnd(.99);
alpar@2360
    61
	delay[e]=0.01+rnd(.99);
alpar@2360
    62
      }
alpar@2360
    63
    
alpar@2360
    64
    ConstrainedShortestPath<Graph,LengthMap,LengthMap> csp(g,cost,delay);
alpar@2367
    65
    for(double d=0;d<2;d+=.001)
alpar@2360
    66
      {
alpar@2360
    67
	double lo_bo;
alpar@2360
    68
	std::cout << d << ": ";
alpar@2360
    69
	SimplePath<Graph> r = csp.larac(nodes[0],nodes[1],d,lo_bo);
alpar@2360
    70
	if(r.empty()) std::cout << "INFEASIBLE\n";
alpar@2360
    71
	else std::cout << "delay: " << csp.delay(r)
alpar@2360
    72
		       << " cost: " << csp.cost(r)
alpar@2360
    73
		       << " (lb: " << lo_bo
alpar@2360
    74
		       << " gap: " << csp.cost(r)-lo_bo
alpar@2360
    75
		       << " , " << (csp.cost(r)-lo_bo)/csp.cost(r)*100
alpar@2360
    76
		       << "%)" << std::endl;
alpar@2360
    77
      }
alpar@2360
    78
    			
alpar@2360
    79
    return 0;
alpar@2360
    80
}