COIN-OR::LEMON - Graph Library

source: lemon-0.x/demo/min_route.cc @ 2310:96cca167430a

Last change on this file since 2310:96cca167430a was 2207:75a29ac69c19, checked in by Alpar Juttner, 18 years ago

xy -> dim2::Point

File size: 3.5 KB
RevLine 
[1636]1/* -*- C++ -*-
2 *
[1956]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
[1636]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
[1358]19#include <iostream>
20#include <fstream>
21
[1342]22#include <lemon/smart_graph.h>
23#include <lemon/dijkstra.h>
24#include <lemon/maps.h>
[2207]25#include <lemon/dim2.h>
[1342]26#include <lemon/graph_reader.h>
27
28#include <lemon/time_measure.h>
29
30#include <cmath>
31
[1775]32/// \ingroup demos
33/// \file
[1959]34/// \brief Minimal route on a planar graph with eucledian distances.
[1775]35///
[1959]36/// Minimal route on a planar graph with eucledian distances.
[1775]37///
38/// \include min_route.cc
39
[1358]40
[1342]41using namespace lemon;
42
43template <typename CoordMap>
44class PotentialMap {
45public:
46  typedef double Value;
47  typedef typename CoordMap::Key Key;
48
[2207]49  PotentialMap(const CoordMap& _coord, const dim2::Point<double>& _target)
[1342]50    : coord(_coord), target(_target) {}
51
52  double operator[](const Key& node) const {
53    return std::sqrt((coord[node].x - target.x) * (coord[node].x - target.x) +
54                     (coord[node].y - target.y) * (coord[node].y - target.y));
55  }
56private:
[1358]57  const CoordMap& coord;
[2207]58  dim2::Point<double> target;
[1342]59};
60
61template <typename Graph, typename LengthMap, typename PotentialMap>
62class ReducedLengthMap {
63public:
64  typedef double Value;
65  typedef typename LengthMap::Key Key;
66
67  ReducedLengthMap(const Graph& _graph, const LengthMap& _length,
68                   const PotentialMap& _pot)
69    : graph(_graph), length(_length), pot(_pot) {}
70
71  Value operator[](const Key& edge) const {
72    return length[edge] - (pot[graph.source(edge)] - pot[graph.target(edge)]);
73  }
74
75private:
76  const Graph& graph;
77  const LengthMap& length;
78  const PotentialMap& pot;
79};
80
81int main() {
82  typedef SmartGraph Graph;
83
84  typedef Graph::Edge Edge;
85  typedef Graph::Node Node;
86  typedef Graph::EdgeIt EdgeIt;
87  typedef Graph::NodeIt NodeIt;
88  typedef Graph::EdgeMap<double> LengthMap;
[2207]89  typedef Graph::NodeMap<dim2::Point<double> > CoordMap;
[1342]90
91  SmartGraph graph;
92
[1358]93  std::ifstream is("route.lgf");
94  GraphReader<Graph> reader(is, graph);
[1342]95 
96  CoordMap coord(graph);
[2207]97  dim2::XMap<CoordMap> xcoord = xMap(coord);
[1394]98  reader.readNodeMap("coordinates_x", xcoord);
[2207]99  dim2::YMap<CoordMap> ycoord = yMap(coord);
[1394]100  reader.readNodeMap("coordinates_y", ycoord);
[1342]101
102  LengthMap length(graph);
[1394]103  reader.readEdgeMap("length", length);
[1342]104
105  Node source, target;
[1394]106  reader.readNode("source", source);
107  reader.readNode("target", target);
[1342]108
109  reader.run();
110
111  {
112    Timer timer;
113    Dijkstra<Graph, LengthMap> dijkstra(graph, length);
114    dijkstra.init();
115    dijkstra.addSource(source);
116    dijkstra.start(target);
117
118    std::cout << dijkstra.dist(target) << std::endl;
119    std::cout << timer << std::endl;
120  }
121  {
122    Timer timer;
123    typedef PotentialMap<CoordMap> Potential;
124    Potential potential(coord, coord[target]);
125
126    typedef ReducedLengthMap<Graph, LengthMap, Potential> ReducedLength;
127    ReducedLength reduced(graph, length, potential);
128
129    Dijkstra<Graph, ReducedLength> dijkstra(graph, reduced);
130
131    dijkstra.init();
132    dijkstra.addSource(source);
133    dijkstra.start(target);
134 
135    std::cout << dijkstra.dist(target) + potential[source] << std::endl;
136    std::cout << timer << std::endl;
137  }
138
139  return 0;
140}
Note: See TracBrowser for help on using the repository browser.