COIN-OR::LEMON - Graph Library

source: lemon-0.x/demo/min_route.cc @ 1641:77f6ab7ad66f

Last change on this file since 1641:77f6ab7ad66f was 1636:260ac104190f, checked in by Akos Ladanyi, 19 years ago

Added missing copyright headers, and corrected the file names in some of them.

File size: 3.3 KB
Line 
1/* -*- C++ -*-
2 * demo/min_route.cc - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2005 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
31using namespace lemon;
32
33template <typename CoordMap>
34class PotentialMap {
35public:
36  typedef double Value;
37  typedef typename CoordMap::Key Key;
38
39  PotentialMap(const CoordMap& _coord, const xy<double>& _target)
40    : coord(_coord), target(_target) {}
41
42  double operator[](const Key& node) const {
43    return std::sqrt((coord[node].x - target.x) * (coord[node].x - target.x) +
44                     (coord[node].y - target.y) * (coord[node].y - target.y));
45  }
46private:
47  const CoordMap& coord;
48  xy<double> target;
49};
50
51template <typename Graph, typename LengthMap, typename PotentialMap>
52class ReducedLengthMap {
53public:
54  typedef double Value;
55  typedef typename LengthMap::Key Key;
56
57  ReducedLengthMap(const Graph& _graph, const LengthMap& _length,
58                   const PotentialMap& _pot)
59    : graph(_graph), length(_length), pot(_pot) {}
60
61  Value operator[](const Key& edge) const {
62    return length[edge] - (pot[graph.source(edge)] - pot[graph.target(edge)]);
63  }
64
65private:
66  const Graph& graph;
67  const LengthMap& length;
68  const PotentialMap& pot;
69};
70
71int main() {
72  typedef SmartGraph Graph;
73
74  typedef Graph::Edge Edge;
75  typedef Graph::Node Node;
76  typedef Graph::EdgeIt EdgeIt;
77  typedef Graph::NodeIt NodeIt;
78  typedef Graph::EdgeMap<double> LengthMap;
79  typedef Graph::NodeMap<xy<double> > CoordMap;
80
81  SmartGraph graph;
82
83  std::ifstream is("route.lgf");
84  GraphReader<Graph> reader(is, graph);
85 
86  CoordMap coord(graph);
87  XMap<CoordMap> xcoord = xMap(coord);
88  reader.readNodeMap("coordinates_x", xcoord);
89  YMap<CoordMap> ycoord = yMap(coord);
90  reader.readNodeMap("coordinates_y", ycoord);
91
92  LengthMap length(graph);
93  reader.readEdgeMap("length", length);
94
95  Node source, target;
96  reader.readNode("source", source);
97  reader.readNode("target", target);
98
99  reader.run();
100
101  {
102    Timer timer;
103    Dijkstra<Graph, LengthMap> dijkstra(graph, length);
104    dijkstra.init();
105    dijkstra.addSource(source);
106    dijkstra.start(target);
107
108    std::cout << dijkstra.dist(target) << std::endl;
109    std::cout << timer << std::endl;
110  }
111  {
112    Timer timer;
113    typedef PotentialMap<CoordMap> Potential;
114    Potential potential(coord, coord[target]);
115
116    typedef ReducedLengthMap<Graph, LengthMap, Potential> ReducedLength;
117    ReducedLength reduced(graph, length, potential);
118
119    Dijkstra<Graph, ReducedLength> dijkstra(graph, reduced);
120
121    dijkstra.init();
122    dijkstra.addSource(source);
123    dijkstra.start(target);
124 
125    std::cout << dijkstra.dist(target) + potential[source] << std::endl;
126    std::cout << timer << std::endl;
127  }
128
129  return 0;
130}
Note: See TracBrowser for help on using the repository browser.