PGROUTING  2.4
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
ksp.cpp
Go to the documentation of this file.
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 
25 #include <deque>
26 #include <string>
27 #include <vector>
28 
29 template <typename G>
30 void process_ksp(G &graph, const std::vector<std::string> &tokens) {
31  std::string::size_type sz;
32  if (tokens[1].compare("from") != 0) {
33  std::cout << "ksp: 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 << "ksp: 'to' kewyword not found\n";
52  return;
53  }
54 
55  if (sources.size() == 0) {
56  std::cout << "ksp: No start value found\n";
57  return;
58  }
59 
60  ++i_ptr;
61  if (i_ptr == tokens.size()) {
62  std::cout << "ksp: 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  Pgr_ksp< G > ksp;
73 
74  if (sources.size() == 1 && targets.size() == 1) {
75  // one to one
76  std::deque< Path > paths;
77  paths = ksp.Yen(graph, sources[0], targets[0], 3); // TODO(someone) make variable
78  std::cout << "THE OPUTPUT ----" << "\n";
79  for (unsigned int i = 0; i < paths.size(); ++i) {
80  if (sizeof(paths[i]) == 0) continue; // no solution found
81  std::cout << "Path #" << i << " cost: " << paths[i].cost << "\n";
82  paths[i].print_path();
83  }
84  } else {
85  std::cout << "ksp: unknown number of arguments\n";
86  }
87 #if 0
88  // ksp is only one to 1
89  } else if (sources.size() == 1 && targets.size() > 1) {
90  // one to many
91  std::deque<Path> paths;
92  dijkstra.dijkstra(graph, paths, sources[0], targets);
93 
94  std::cout << "THE OPUTPUTS ----> total outputs: " << paths.size() << "\n";
95  for (unsigned int i = 0; i < paths.size(); ++i) {
96  if (sizeof(paths[i]) == 0) continue; // no solution found
97  std::cout << "Path #" << i << " cost: " << paths[i].cost << "\n";
98  paths[i].print_path();
99  }
100  } else if (sources.size() > 1 && targets.size() == 1) {
101  // many to 1
102  std::deque<Path> paths;
103  dijkstra.dijkstra(graph, paths, sources, targets[0]);
104 
105 
106  std::cout << "THE OPUTPUTS ----> total outputs: " << paths.size() << "\n";
107  for (unsigned int i = 0; i < paths.size(); ++i) {
108  if (sizeof(paths[i]) == 0) continue; // no solution found
109  std::cout << "Path #" << i << " cost: " << paths[i].cost << "\n";
110  paths[i].print_path();
111  }
112  } else {
113  // many to many
114  std::deque<Path> paths;
115  dijkstra.dijkstra(graph, paths, sources, targets);
116  std::cout << "THE OPUTPUTS ----> total outputs: " << paths.size() << "\n";
117  for (unsigned int i = 0; i < paths.size(); ++i) {
118  if (sizeof(paths[i]) == 0) continue; // no solution found
119  std::cout << "Path #" << i << " cost: " << paths[i].cost << "\n";
120  paths[i].print_path();
121  }
122  }
123 #endif
124 }
void process_ksp(G &graph, const std::vector< std::string > &tokens)
Definition: ksp.cpp:30
std::deque< Path > Yen(G &graph, int64_t source, int64_t target, int K, bool heap_paths)
Definition: pgr_ksp.cpp:51