pgRouting  2.2
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Functions Variables Pages
performance/dijkstra/dijkstra.hpp
1 /*PGR-GNU*****************************************************************
2 
3 Copyright (c) 2015 pgRouting developers
4 Mail: project@pgrouting.org
5 
6 ------
7 
8 This program is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2 of the License, or
11 (at your option) any later version.
12 
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
17 
18 You should have received a copy of the GNU General Public License
19 along with this program; if not, write to the Free Software
20 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
21 
22 ********************************************************************PGR-GNU*/
23 
24 #include <ctime>
25 #include <chrono>
26 
27 
28 template <typename G>
29 void process_dijkstra(G &graph, const std::vector<std::string> &tokens) {
30 
31  std::string::size_type sz;
32  if (tokens[1].compare("from") != 0) {
33  std::cout << "missing 'from' kewyword\n";
34  return;
35  }
36 
37  std::vector< int64_t > sources;
38  unsigned int i_ptr = 2;
39 
40  for ( ; i_ptr < tokens.size(); ++i_ptr) {
41  if (tokens[i_ptr].compare("to") == 0) break;
42  try {
43  uint64_t start_vertex(stol(tokens[i_ptr], &sz));
44  sources.push_back(start_vertex);
45  } catch(...) {
46  break;
47  }
48  }
49 
50  if (i_ptr == tokens.size() || tokens[i_ptr].compare("to") != 0) {
51  std::cout << "dijkstra: 'dist' kewyword not found\n";
52  return;
53  }
54 
55  if (sources.size() == 0) {
56  std::cout << "dijkstra: No start value found\n";
57  return;
58  }
59 
60  ++i_ptr;
61  if (i_ptr == tokens.size()) {
62  std::cout << "dijkstra: No 'to' values found\n";
63  return;
64  }
65 
66  std::vector< int64_t > targets;
67  for ( ; i_ptr < tokens.size(); ++i_ptr) {
68  auto end_vertex(stol(tokens[i_ptr], &sz));
69  targets.push_back(end_vertex);
70  }
71 
72 
73  if (sources.size() == 1 && targets.size() == 1) {
74  // one to one
75  Path path;
76 
77  // TIMING DIJKSTRA
78  std::cout << "**************\n\n";
79  clock_t begin = clock();
80  std::time_t start_t = std::time(NULL);
81  std::cout << "Execution starts at: " << std::ctime(&start_t) << "\n";
82  std::chrono::steady_clock::time_point begin_elapsed = std::chrono::steady_clock::now();
83 
84 
85  pgr_dijkstra(graph, path, sources[0], targets[0]);
86  clock_t end = clock();
87  double elapsed_secs = double(end - begin) / static_cast<double>(CLOCKS_PER_SEC);
88 
89  std::time_t end_t = std::time(NULL);
90  std::chrono::steady_clock::time_point end_elapsed = std::chrono::steady_clock::now();
91 
92  typedef std::chrono::duration<int,std::milli> millisecs_t ;
93  millisecs_t duration = std::chrono::duration_cast<millisecs_t>(end_elapsed - begin_elapsed);
94 
95  std::cout << "Execution started at: " << std::ctime(&start_t);
96  std::cout << "Execution ended at: " << std::ctime(&end_t);
97  std::cout << "Elapsed time: " << (double)duration.count()/(double)1000 << " Seconds.\n" ;
98  std::cout << "User CPU time: -> " << elapsed_secs << " seconds\n";
99  std::cout << "**************\n\n";
100  // END TIMING DIJKSTRA
101 
102  std::cout << "THE OPUTPUT ----> total cost: " << path.tot_cost() << "\n"
103  << path;
104  } else if (sources.size() == 1 && targets.size() > 1){
105  std::deque<Path> paths;
106  // one to many
107  pgr_dijkstra(graph, paths, sources[0], targets);
108 
109  std::cout << "THE OPUTPUTS ----> total outputs: " << paths.size() << "\n";
110  for (unsigned int i = 0; i < paths.size(); ++i) {
111  if (sizeof(paths[i]) == 0) continue; //no solution found
112  std::cout << "Path #" << i << " cost: " << paths[i].tot_cost() << "\n"
113  << paths[i];
114  }
115  } else if (sources.size() > 1 && targets.size() == 1){
116  // many to 1
117  std::deque<Path> paths;
118  pgr_dijkstra(graph, paths, sources, targets[0]);
119 
120 
121  std::cout << "THE OPUTPUTS ----> total outputs: " << paths.size() << "\n";
122  for (unsigned int i = 0; i < paths.size(); ++i) {
123  if (sizeof(paths[i]) == 0) continue; //no solution found
124  std::cout << "Path #" << i << " cost: " << paths[i].tot_cost() << "\n"
125  << paths[i];
126  }
127  } else {
128  //many to many
129  std::deque<Path> paths;
130  pgr_dijkstra(graph, paths, sources, targets);
131 
132  std::cout << "THE OPUTPUTS ----> total outputs: " << paths.size() << "\n";
133  for (unsigned int i = 0; i < paths.size(); ++i) {
134  if (sizeof(paths[i]) == 0) continue; //no solution found
135  std::cout << "Path #" << i << " cost: " << paths[i].tot_cost() << "\n"
136  << paths[i];
137  }
138  }
139 }