COIN-OR::LEMON - Graph Library

source: lemon-0.x/demo/csp_demo.cc @ 2366:bfbdded3763a

Last change on this file since 2366:bfbdded3763a was 2360:72c7075ad5ba, checked in by Alpar Juttner, 13 years ago

Lagrange relaxation based algorithm for the delay constrained least cost
path problem.

File size: 2.2 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
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 Dijkstra algorithm
22///
23/// Dijkstra's algorithm computes shortest paths between two nodes in
24/// a graph with edge lengths. Here we only show some of the
25/// facilities supplied by our implementation: for the detailed
26/// documentation of the LEMON Dijkstra class read \ref lemon::Dijkstra "this".
27///
28/// \include dijkstra_demo.cc
29
30#include <iostream>
31#include <lemon/list_graph.h>
32#include <lemon/csp.h>
33#include <lemon/random.h>
34
35
36using namespace lemon;
37
38
39int main (int, char*[])
40{
41
42    typedef ListGraph Graph;
43    typedef Graph::Node Node;
44    typedef Graph::Edge Edge;
45    typedef Graph::EdgeIt EdgeIt;
46    typedef Graph::EdgeMap<double> LengthMap;
47
48    Graph g;
49
50    const int N=100;
51    const int M=20000;
52    std::vector<Node> nodes;
53    std::vector<Edge> edges;
54   
55    for(int i=0;i<N;i++) nodes.push_back(g.addNode());
56
57    for(int i=0;i<M;i++)
58      edges.push_back(g.addEdge(nodes[rnd[N]],nodes[rnd[N]]));
59   
60    LengthMap cost(g);
61    LengthMap delay(g);
62    for(EdgeIt e(g);e!=INVALID;++e)
63      {
64        cost[e]=0.01+rnd(.99);
65        delay[e]=0.01+rnd(.99);
66      }
67   
68    ConstrainedShortestPath<Graph,LengthMap,LengthMap> csp(g,cost,delay);
69    for(double d=0;d<2;d+=.01)
70      {
71        double lo_bo;
72        std::cout << d << ": ";
73        SimplePath<Graph> r = csp.larac(nodes[0],nodes[1],d,lo_bo);
74        if(r.empty()) std::cout << "INFEASIBLE\n";
75        else std::cout << "delay: " << csp.delay(r)
76                       << " cost: " << csp.cost(r)
77                       << " (lb: " << lo_bo
78                       << " gap: " << csp.cost(r)-lo_bo
79                       << " , " << (csp.cost(r)-lo_bo)/csp.cost(r)*100
80                       << "%)" << std::endl;
81      }
82                       
83    return 0;
84}
Note: See TracBrowser for help on using the repository browser.