PGROUTING  2.4
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
tour.h
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 
3 FILE: tour.h
4 
5 Copyright (c) 2015 pgRouting developers
6 Mail: project@pgrouting.org
7 
8 ------
9 
10 This program is free software; you can redistribute it and/or modify
11 it under the terms of the GNU General Public License as published by
12 the Free Software Foundation; either version 2 of the License, or
13 (at your option) any later version.
14 
15 This program is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU General Public License for more details.
19 
20 You should have received a copy of the GNU General Public License
21 along with this program; if not, write to the Free Software
22 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
23 
24  ********************************************************************PGR-GNU*/
25 
26 #ifndef SRC_TSP_SRC_TOUR_H_
27 #define SRC_TSP_SRC_TOUR_H_
28 #pragma once
29 
30 #include <stdlib.h>
31 #include <algorithm>
32 #include <numeric>
33 #include <vector>
34 
35 #include "./Dmatrix.h"
36 
37 
38 namespace pgrouting {
39 namespace tsp {
40 
41 
42 class Tour {
43  public:
44  Tour(const Tour &) = default;
45 
46  explicit Tour(const std::vector<size_t> &cities_order) :
47  cities(cities_order) {
48  }
49 
50  explicit Tour(size_t n) {
51  cities.resize(n);
52  std::iota(std::begin(cities), std::end(cities), 0);
53  }
54 
55  inline size_t size() const {return cities.size();}
56 
57  friend std::ostream& operator<<(
58  std::ostream &log,
59  const Tour &tour);
60 
61 
62  friend double Dmatrix::tourCost(const Tour &tour) const;
63 
64 
65  /* @brief slides range [first + 1, last + 1) into place + 1
66  *
67  * 0 1 2 3 4 5 6 7 8 9
68  * p f l
69  * slides [4,5,6] to position p
70  *
71  * 0 1 4 5 6 2 3 7 8 9
72  *
73  *
74  * 0 1 2 3 4 5 6 7 8 9
75  * f l p
76  * slides [2,3,4] to position p
77  *
78  * 0 1 6 7 2 3 4 5 8 9
79  *
80  * uses std::reverse
81  *
82  * http://en.cppreference.com/w/cpp/algorithm/rotate
83  *
84  * first - the beginning of the original range
85  * last - the end of the original range
86  * place - location where to slide
87  *
88  *
89  *
90  * @params[IN] place index of place
91  * @params[IN] first - index of first
92  * @params[IN] last - index of last
93  *
94  * precondition:
95  * pgassert(first < cities.size();
96  * pgassert(last < cities.size();
97  * pgassert(place < cities.size();
98  *
99  */
100 
101  void slide(
102  size_t place,
103  size_t first,
104  size_t last);
105 
106 
107  /* @brief std::reverse on the cities
108  *
109  * http://en.cppreference.com/w/cpp/algorithm/reverse
110  *
111  * first - the beginning of the original range
112  * last - the end of the original range
113  *
114  * @params[IN] c1 - index of first
115  * @params[IN] c2 - index of lasst
116  *
117  * precondition:
118  * pgassert(c1 < c2);
119  *
120  */
121 
122  void reverse(
123  size_t c1,
124  size_t c2);
125 
126 
127  /* @brief std::rotate on the cities
128  *
129  * http://en.cppreference.com/w/cpp/algorithm/rotate
130  *
131  * first - the beginning of the original range
132  * n_first - the element that should appear at the beginning of the rotated range
133  * last - the end of the original range
134  *
135  * @params[IN] c1 - index of first
136  * @params[IN] c2 - index of n_first
137  * @params[IN] c3 - index of last
138  *
139  * precondition:
140  * pgassert(c2 && c2 < c3 && c3 < n);
141  *
142  */
143  void rotate(
144  size_t c1,
145  size_t c2,
146  size_t c3);
147 
148 
149  void swap(
150  size_t c1,
151  size_t c2);
152 
153  public:
154  std::vector<size_t> cities;
155 };
156 
157 } // namespace tsp
158 } // namespace pgrouting
159 
160 #endif // SRC_TSP_SRC_TOUR_H_
size_t size() const
Definition: tour.h:55
void rotate(size_t c1, size_t c2, size_t c3)
Definition: tour.cpp:77
Tour(size_t n)
Definition: tour.h:50
std::vector< size_t > cities
Definition: tour.h:154
double tourCost(const Tour &tour) const
tour evaluation
Definition: Dmatrix.cpp:43
void reverse(size_t c1, size_t c2)
Definition: tour.cpp:47
void swap(size_t c1, size_t c2)
Definition: tour.cpp:90
friend std::ostream & operator<<(std::ostream &log, const Tour &tour)
Definition: tour.cpp:36
Tour(const Tour &)=default
void slide(size_t place, size_t first, size_t last)
Definition: tour.cpp:56
Tour(const std::vector< size_t > &cities_order)
Definition: tour.h:46