pgRouting  2.2
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Functions Variables Pages
pgr_tsp.hpp
1 /*PGR-GNU*****************************************************************
2  * File: tsp_driver.cpp
3  *
4  * Generated with Template by:
5  * Copyright (c) 2015 pgRouting developers
6  * Mail: project@pgrouting.org
7  *
8  * Function's developer:
9  * Copyright (c) 2015 Celia Virginia Vergara Castillo
10  * Mail: vicky_vergara@hotmail.com
11  *
12  * ------
13  *
14  * This program is free software; you can redistribute it and/or modify
15  * it under the terms of the GNU General Public License as published by
16  * the Free Software Foundation; either version 2 of the License, or
17  * (at your option) any later version.
18  *
19  * This program is distributed in the hope that it will be useful,
20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22  * GNU General Public License for more details.
23  *
24  * You should have received a copy of the GNU General Public License
25  * along with this program; if not, write to the Free Software
26  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
27  *
28  * ********************************************************************PGR-GNU*/
29 
30 #include <vector>
31 
32 #include "../../common/src/pgr_types.h"
33 #include "./Dmatrix.hpp"
34 
35 class TSP {
36  public:
37 /*
38  * Defs
39  */
40 typedef size_t Path[3]; /* specify how to change path */
41 
42 typedef std::vector< std::vector < double > > Costs;
43 typedef std::vector< int64_t > Ids;
44 
45  Dmatrix dist;
46  size_t n;
47  double maxd;
48  size_t bestlen;
49  double bestCost;
50  Ids iorder;
51  /*
52  * std::vector< bool > visited;
53  */
54  Ids jorder;
55  Ids border;
56  double b[4];
57 
58 
59  /*
60  * function members
61  */
62  TSP(Dmatrix _costs)
63  : dist(_costs),
64  n(_costs.size()) {
65  iorder.resize(n);
66  jorder.resize(n);
67  maxd = dist.max();
68 
69  /*
70  * identity_permutations
71  */
72  std::iota(std::begin(iorder), std::end(iorder), 0);
73 #if 0
74  for (auto &e : iorder) {
75  e = i;
76  }
77 #endif
78  /*
79  * best order
80  */
81  border = iorder;
82  bestCost = dist.pathCost(border);
83  }
84  void update(Ids new_order);
85  bool findEulerianPath();
86  void annealing();
87  void doThreeWay(Path p);
88  double getThreeWayCost (Path p);
89  double getReverseCost(Path p);
90  void doReverse(Path p);
91  double D(size_t, size_t);
92 };
93 
Definition: pgr_tsp.hpp:35