COIN-OR::LEMON - Graph Library

source: lemon-0.x/demo/min_route.cc @ 1955:daca31868d70

Last change on this file since 1955:daca31868d70 was 1875:98698b69a902, checked in by Alpar Juttner, 18 years ago

Happy new year to LEMON

File size: 3.5 KB
Line 
1/* -*- C++ -*-
2 * demo/min_route.cc - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
16
17#include <iostream>
18#include <fstream>
19
20#include <lemon/smart_graph.h>
21#include <lemon/dijkstra.h>
22#include <lemon/maps.h>
23#include <lemon/xy.h>
24#include <lemon/graph_reader.h>
25
26#include <lemon/time_measure.h>
27
28#include <cmath>
29
30/// \ingroup demos
31/// \file
32/// \brief Minimal route on a plan graph with eucledian distances.
33///
34/// Minimal route on a plan graph with eucledian distances.
35///
36/// \include min_route.cc
37
38
39using namespace lemon;
40
41template <typename CoordMap>
42class PotentialMap {
43public:
44  typedef double Value;
45  typedef typename CoordMap::Key Key;
46
47  PotentialMap(const CoordMap& _coord, const xy<double>& _target)
48    : coord(_coord), target(_target) {}
49
50  double operator[](const Key& node) const {
51    return std::sqrt((coord[node].x - target.x) * (coord[node].x - target.x) +
52                     (coord[node].y - target.y) * (coord[node].y - target.y));
53  }
54private:
55  const CoordMap& coord;
56  xy<double> target;
57};
58
59template <typename Graph, typename LengthMap, typename PotentialMap>
60class ReducedLengthMap {
61public:
62  typedef double Value;
63  typedef typename LengthMap::Key Key;
64
65  ReducedLengthMap(const Graph& _graph, const LengthMap& _length,
66                   const PotentialMap& _pot)
67    : graph(_graph), length(_length), pot(_pot) {}
68
69  Value operator[](const Key& edge) const {
70    return length[edge] - (pot[graph.source(edge)] - pot[graph.target(edge)]);
71  }
72
73private:
74  const Graph& graph;
75  const LengthMap& length;
76  const PotentialMap& pot;
77};
78
79int main() {
80  typedef SmartGraph Graph;
81
82  typedef Graph::Edge Edge;
83  typedef Graph::Node Node;
84  typedef Graph::EdgeIt EdgeIt;
85  typedef Graph::NodeIt NodeIt;
86  typedef Graph::EdgeMap<double> LengthMap;
87  typedef Graph::NodeMap<xy<double> > CoordMap;
88
89  SmartGraph graph;
90
91  std::ifstream is("route.lgf");
92  GraphReader<Graph> reader(is, graph);
93 
94  CoordMap coord(graph);
95  XMap<CoordMap> xcoord = xMap(coord);
96  reader.readNodeMap("coordinates_x", xcoord);
97  YMap<CoordMap> ycoord = yMap(coord);
98  reader.readNodeMap("coordinates_y", ycoord);
99
100  LengthMap length(graph);
101  reader.readEdgeMap("length", length);
102
103  Node source, target;
104  reader.readNode("source", source);
105  reader.readNode("target", target);
106
107  reader.run();
108
109  {
110    Timer timer;
111    Dijkstra<Graph, LengthMap> dijkstra(graph, length);
112    dijkstra.init();
113    dijkstra.addSource(source);
114    dijkstra.start(target);
115
116    std::cout << dijkstra.dist(target) << std::endl;
117    std::cout << timer << std::endl;
118  }
119  {
120    Timer timer;
121    typedef PotentialMap<CoordMap> Potential;
122    Potential potential(coord, coord[target]);
123
124    typedef ReducedLengthMap<Graph, LengthMap, Potential> ReducedLength;
125    ReducedLength reduced(graph, length, potential);
126
127    Dijkstra<Graph, ReducedLength> dijkstra(graph, reduced);
128
129    dijkstra.init();
130    dijkstra.addSource(source);
131    dijkstra.start(target);
132 
133    std::cout << dijkstra.dist(target) + potential[source] << std::endl;
134    std::cout << timer << std::endl;
135  }
136
137  return 0;
138}
Note: See TracBrowser for help on using the repository browser.