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