1.1 --- a/demo/Makefile.am Mon Feb 12 10:27:03 2007 +0000
1.2 +++ b/demo/Makefile.am Mon Feb 12 17:54:36 2007 +0000
1.3 @@ -5,6 +5,7 @@
1.4 if WANT_DEMO
1.5
1.6 noinst_PROGRAMS += \
1.7 + demo/csp_demo \
1.8 demo/dim_to_dot \
1.9 demo/dijkstra_demo \
1.10 demo/reader_writer_demo \
1.11 @@ -36,6 +37,8 @@
1.12
1.13 endif WANT_DEMO
1.14
1.15 +demo_csp_demo_SOURCES = demo/csp_demo.cc
1.16 +
1.17 demo_dim_to_dot_SOURCES = demo/dim_to_dot.cc
1.18
1.19 demo_dijkstra_demo_SOURCES = demo/dijkstra_demo.cc
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/demo/csp_demo.cc Mon Feb 12 17:54:36 2007 +0000
2.3 @@ -0,0 +1,84 @@
2.4 +/* -*- C++ -*-
2.5 + *
2.6 + * This file is a part of LEMON, a generic C++ optimization library
2.7 + *
2.8 + * Copyright (C) 2003-2006
2.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
2.11 + *
2.12 + * Permission to use, modify and distribute this software is granted
2.13 + * provided that this copyright notice appears in all copies. For
2.14 + * precise terms see the accompanying LICENSE file.
2.15 + *
2.16 + * This software is provided "AS IS" with no warranty of any kind,
2.17 + * express or implied, and with no claim as to its suitability for any
2.18 + * purpose.
2.19 + *
2.20 + */
2.21 +
2.22 +///\ingroup demos
2.23 +///\file
2.24 +///\brief Demonstrating the usage of LEMON's Dijkstra algorithm
2.25 +///
2.26 +/// Dijkstra's algorithm computes shortest paths between two nodes in
2.27 +/// a graph with edge lengths. Here we only show some of the
2.28 +/// facilities supplied by our implementation: for the detailed
2.29 +/// documentation of the LEMON Dijkstra class read \ref lemon::Dijkstra "this".
2.30 +///
2.31 +/// \include dijkstra_demo.cc
2.32 +
2.33 +#include <iostream>
2.34 +#include <lemon/list_graph.h>
2.35 +#include <lemon/csp.h>
2.36 +#include <lemon/random.h>
2.37 +
2.38 +
2.39 +using namespace lemon;
2.40 +
2.41 +
2.42 +int main (int, char*[])
2.43 +{
2.44 +
2.45 + typedef ListGraph Graph;
2.46 + typedef Graph::Node Node;
2.47 + typedef Graph::Edge Edge;
2.48 + typedef Graph::EdgeIt EdgeIt;
2.49 + typedef Graph::EdgeMap<double> LengthMap;
2.50 +
2.51 + Graph g;
2.52 +
2.53 + const int N=100;
2.54 + const int M=20000;
2.55 + std::vector<Node> nodes;
2.56 + std::vector<Edge> edges;
2.57 +
2.58 + for(int i=0;i<N;i++) nodes.push_back(g.addNode());
2.59 +
2.60 + for(int i=0;i<M;i++)
2.61 + edges.push_back(g.addEdge(nodes[rnd[N]],nodes[rnd[N]]));
2.62 +
2.63 + LengthMap cost(g);
2.64 + LengthMap delay(g);
2.65 + for(EdgeIt e(g);e!=INVALID;++e)
2.66 + {
2.67 + cost[e]=0.01+rnd(.99);
2.68 + delay[e]=0.01+rnd(.99);
2.69 + }
2.70 +
2.71 + ConstrainedShortestPath<Graph,LengthMap,LengthMap> csp(g,cost,delay);
2.72 + for(double d=0;d<2;d+=.01)
2.73 + {
2.74 + double lo_bo;
2.75 + std::cout << d << ": ";
2.76 + SimplePath<Graph> r = csp.larac(nodes[0],nodes[1],d,lo_bo);
2.77 + if(r.empty()) std::cout << "INFEASIBLE\n";
2.78 + else std::cout << "delay: " << csp.delay(r)
2.79 + << " cost: " << csp.cost(r)
2.80 + << " (lb: " << lo_bo
2.81 + << " gap: " << csp.cost(r)-lo_bo
2.82 + << " , " << (csp.cost(r)-lo_bo)/csp.cost(r)*100
2.83 + << "%)" << std::endl;
2.84 + }
2.85 +
2.86 + return 0;
2.87 +}
3.1 --- a/lemon/Makefile.am Mon Feb 12 10:27:03 2007 +0000
3.2 +++ b/lemon/Makefile.am Mon Feb 12 17:54:36 2007 +0000
3.3 @@ -44,6 +44,7 @@
3.4 lemon/config.h \
3.5 lemon/concept_check.h \
3.6 lemon/counter.h \
3.7 + lemon/csp.h \
3.8 lemon/dag_shortest_path.h \
3.9 lemon/dfs.h \
3.10 lemon/dijkstra.h \
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/lemon/csp.h Mon Feb 12 17:54:36 2007 +0000
4.3 @@ -0,0 +1,172 @@
4.4 +/* -*- C++ -*-
4.5 + *
4.6 + * This file is a part of LEMON, a generic C++ optimization library
4.7 + *
4.8 + * Copyright (C) 2003-2006
4.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
4.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
4.11 + *
4.12 + * Permission to use, modify and distribute this software is granted
4.13 + * provided that this copyright notice appears in all copies. For
4.14 + * precise terms see the accompanying LICENSE file.
4.15 + *
4.16 + * This software is provided "AS IS" with no warranty of any kind,
4.17 + * express or implied, and with no claim as to its suitability for any
4.18 + * purpose.
4.19 + *
4.20 + */
4.21 +
4.22 +#ifndef LEMON_CSP_H
4.23 +#define LEMON_CSP_H
4.24 +
4.25 +///\ingroup flowalgs
4.26 +///\file
4.27 +///\brief Algorithm for the Resource Constrained Shortest Path problem.
4.28 +///
4.29 +///
4.30 +///\todo dijkstraZero() solution should be revised.
4.31 +
4.32 +#include <lemon/list_graph.h>
4.33 +#include <lemon/graph_utils.h>
4.34 +#include <lemon/error.h>
4.35 +#include <lemon/maps.h>
4.36 +#include <lemon/tolerance.h>
4.37 +#include <lemon/dijkstra.h>
4.38 +#include <lemon/path.h>
4.39 +#include <lemon/counter.h>
4.40 +namespace lemon {
4.41 +
4.42 + ///Algorithms for the Resource Constrained Shortest Path Problem
4.43 +
4.44 + ///\e
4.45 + ///
4.46 + template<class Graph,
4.47 + class CM=typename Graph:: template EdgeMap<double>,
4.48 + class DM=CM>
4.49 + class ConstrainedShortestPath
4.50 + {
4.51 + public:
4.52 +
4.53 + GRAPH_TYPEDEFS(typename Graph);
4.54 +
4.55 + typedef SimplePath<Graph> Path;
4.56 +
4.57 + Graph &_g;
4.58 + Tolerance<double> tol;
4.59 +
4.60 + CM &_cost;
4.61 + DM &_delay;
4.62 +
4.63 + class CoMap
4.64 + {
4.65 + CM &_cost;
4.66 + DM &_delay;
4.67 + double _lambda;
4.68 + public:
4.69 + typedef typename CM::Key Key;
4.70 + typedef double Value;
4.71 + CoMap(CM &c,DM &d) :_cost(c), _delay(d), _lambda(0) {}
4.72 + double lambda() const { return _lambda; }
4.73 + void lambda(double l) { _lambda=l; }
4.74 + Value operator[](Key &e) const
4.75 + {
4.76 + return _cost[e]+_lambda*_delay[e];
4.77 + }
4.78 + } _co_map;
4.79 +
4.80 +
4.81 + Dijkstra<Graph, CoMap> _dij;
4.82 + ///\e
4.83 +
4.84 + ///\e
4.85 + ///
4.86 + ConstrainedShortestPath(Graph &g, CM &cost, DM &delay)
4.87 + : _g(g), _cost(cost), _delay(delay),
4.88 + _co_map(cost,delay), _dij(_g,_co_map) {}
4.89 +
4.90 +
4.91 + ///Compute the cost of a path
4.92 + double cost(const Path &p)
4.93 + {
4.94 + double s=0;
4.95 + // Path r;
4.96 + for(typename Path::EdgeIt e(p);e!=INVALID;++e) s+=_cost[e];
4.97 + return s;
4.98 + }
4.99 +
4.100 + ///Compute the delay of a path
4.101 + double delay(const Path &p)
4.102 + {
4.103 + double s=0;
4.104 + for(typename Path::EdgeIt e(p);e!=INVALID;++e) s+=_delay[e];
4.105 + return s;
4.106 + }
4.107 +
4.108 + ///Runs the LARAC algorithm
4.109 +
4.110 + ///This function runs a Lagrange relaxation based heuristic to find
4.111 + ///a delay constrained least cost path.
4.112 + ///\param s source node
4.113 + ///\param t target node
4.114 + ///\retval lo_bo a lower bound on the optimal solution
4.115 + ///\return the found path or an empty
4.116 + Path larac(Node s, Node t, double delta, double &lo_bo)
4.117 + {
4.118 + NoCounter cnt("LARAC iterations: ");
4.119 + double lambda=0;
4.120 + double cp,cq,dp,dq,cr,dr;
4.121 + Path p;
4.122 + Path q;
4.123 + Path r;
4.124 + {
4.125 + Dijkstra<Graph,CM> dij(_g,_cost);
4.126 + dij.run(s,t);
4.127 + cnt++;
4.128 + if(!dij.reached(t)) return Path();
4.129 + p=dij.path(t);
4.130 + cp=cost(p);
4.131 + dp=delay(p);
4.132 + }
4.133 + if(delay(p)<=delta) return p;
4.134 + {
4.135 + Dijkstra<Graph,DM> dij(_g,_delay);
4.136 + dij.run(s,t);
4.137 + cnt++;
4.138 + q=dij.path(t);
4.139 + cq=cost(q);
4.140 + dq=delay(q);
4.141 + }
4.142 + if(delay(q)>delta) return Path();
4.143 + while (true) {
4.144 + lambda=(cp-cq)/(dq-dp);
4.145 + _co_map.lambda(lambda);
4.146 + _dij.run(s,t);
4.147 + cnt++;
4.148 + r=_dij.path(t);
4.149 + cr=cost(r);
4.150 + dr=delay(r);
4.151 + if(!tol.less(cr+lambda*dr,cp+lambda*dp)) {
4.152 + lo_bo=cq+lambda*(dq-delta);
4.153 + return q;
4.154 + }
4.155 + else if(tol.less(dr,delta))
4.156 + {
4.157 + q=r;
4.158 + cq=cr;
4.159 + dq=dr;
4.160 + }
4.161 + else if(tol.less(delta,dr))
4.162 + {
4.163 + p=r;
4.164 + cp=cr;
4.165 + dp=dr;
4.166 + }
4.167 + else return r;
4.168 + }
4.169 + }
4.170 + };
4.171 +
4.172 +
4.173 +} //END OF NAMESPACE LEMON
4.174 +
4.175 +#endif