PGROUTING  2.5
pgr_dijkstraTRSP.hpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 File: pgr_dijkstraTRSP.hpp
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) 2017 Vidhan Jain
10 Mail: vidhanj1307@gmail.com
11 
12 ------
13 This program is free software; you can redistribute it and/or modify
14 it under the terms of the GNU General Public License as published by
15 the Free Software Foundation; either version 2 of the License, or
16 (at your option) any later version.
17 This program is distributed in the hope that it will be useful,
18 but WITHOUT ANY WARRANTY; without even the implied warranty of
19 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 GNU General Public License for more details.
21 You should have received a copy of the GNU General Public License
22 along with this program; if not, write to the Free Software
23 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
24 ********************************************************************PGR-GNU*/
25 #ifndef INCLUDE_DIJKSTRATRSP_PGR_DIJKSTRATRSP_HPP_
26 #define INCLUDE_DIJKSTRATRSP_PGR_DIJKSTRATRSP_HPP_
27 #pragma once
28 
30 #include "c_types/line_graph_rt.h"
31 
33 
34 #include <sstream>
35 #include <deque>
36 #include <vector>
37 #include <set>
38 #include <limits>
39 
40 #include "cpp_common/pgr_assert.h"
42 
43 
44 template < class G >
46  public:
48  G& graph,
49  const std::vector< Restriction >& restrictions,
50  const std::vector< pgr_edge_t >& edges,
51  int64_t source,
52  int64_t target,
53  bool only_cost,
54  bool strict);
55  void clear();
56  private:
57  void executeDijkstraTRSP(G& graph);
58  void getDijkstraSolution(G& graph);
59  bool has_restriction();
60  bool has_a_restriction(int64_t edge, int64_t index);
61  private:
62  typedef typename G::V V;
65  int64_t m_start;
66  int64_t m_end;
67  std::vector< Restriction > m_restrictions;
68  std::vector< int64_t > m_edges_in_path;
70  bool m_strict;
71 
73 
74  public:
75  std::ostringstream log;
76 };
77 
78 template < class G >
80 }
81 
82 template < class G >
83 Path
85  G& graph,
86  const std::vector< Restriction >& restrictions,
87  const std::vector< pgr_edge_t >& edges,
88  int64_t start_vertex,
89  int64_t end_vertex,
90  bool only_cost,
91  bool strict) {
92  if (start_vertex == end_vertex)
93  return Path();
94  if (!graph.has_vertex(start_vertex) || !graph.has_vertex(end_vertex))
95  return Path();
96 
97  m_only_cost = only_cost;
98  v_source = graph.get_V(start_vertex);
99  v_target = graph.get_V(end_vertex);
100  m_start = start_vertex;
101  m_end = end_vertex;
102  m_restrictions = restrictions;
103  m_strict = strict;
104  executeDijkstraTRSP(graph);
105  if (curr_result_path.size() or graph.m_gType == UNDIRECTED)
106  return curr_result_path;
107 
108 #if 0
110  line.insert_vertices(edges);
111  auto line_graph_edges = line.transform(graph);
112  log << "\nGraph before removing restrictions\n" << line << "\n";
113  auto remaining_restrictions = line.remove_restricted_edges(m_restrictions);
114  log << "\n Graph after removing restrictions\n" << line << "\n";
115 
116  log << line.log.str().c_str() << "\n\n\n";
117 
118  line.create_virtual_vertices();
119  log << line << "\n";
120 #endif
121 
122  return curr_result_path;
123 }
124 
125 template < class G >
127  Path path;
128 
129  Pgr_dijkstra< G > fn_dijkstra;
130  path = fn_dijkstra.dijkstra(graph, m_start, m_end);
131 
132  if (path.empty()) return;
133  curr_result_path = path;
134 }
135 
136 template < class G >
137 bool Pgr_dijkstraTRSP< G >::has_a_restriction(int64_t edge, int64_t index) {
138  auto lower_bound_cmp = [](const Restriction& r, const int64_t& target) {
139  return r.restrict_edges()[0] < target;
140  };
141  auto edge_index = std::lower_bound(m_restrictions.begin(),
142  m_restrictions.end(), edge, lower_bound_cmp) - m_restrictions.begin();
143  log << "\nResult generated from lower_bound\n";
144  while (edge_index < (int64_t)m_restrictions.size()) {
145  auto r_edges = m_restrictions[edge_index].restrict_edges();
146  if (r_edges[0] != edge) break;
147  log << m_restrictions[edge_index] << "\n";
148  bool okay = true;
149  size_t temp_edge_index = index;
150 
151  for (auto &edge_id: r_edges) {
152  if (temp_edge_index >= m_edges_in_path.size() or
153  m_edges_in_path[temp_edge_index] != edge_id) {
154  okay = false;
155  break;
156  }
157  temp_edge_index++;
158  }
159  log << "\nokay value = " << okay <<"\n";
160  if (okay) return true;
161  edge_index++;
162  }
163  log << "Ends Here\n";
164  return false;
165 }
166 
167 template < class G >
169  auto sort_cmp = [](const Restriction& left,
170  const Restriction& right) -> bool {
171  return left.restrict_edges()[0] <= right.restrict_edges()[0];
172  };
173  std::stable_sort(m_restrictions.begin(), m_restrictions.end(),
174  sort_cmp);
175  log << "\nRestriction array after sorting.\n";
176  for (auto &it: m_restrictions) log << it << "\n";
177  log << "\nEnd\n";
178  size_t index = 0;
179  for (auto &edge: m_edges_in_path) {
180  if (has_a_restriction(edge, index))
181  return true;
182  index++;
183  }
184  return false;
185 }
186 
187 template < class G >
189  clear();
190  getDijkstraSolution(graph);
192 
193  for (auto &path: curr_result_path) {
194  m_edges_in_path.push_back(path.edge);
195  }
196  while (m_edges_in_path.size() and m_edges_in_path.back() == -1) {
197  m_edges_in_path.pop_back();
198  }
199 
200  log << "Edges in m_edges_in_path:-------------------\n";
201  for(auto &it: m_edges_in_path) log << it << "\n";
202  log << "---------------------------------------------\n";
203  bool sol = has_restriction();
204  log << "Result of valid solution: " << sol << "\n";
205  if (sol) curr_result_path = Path();
206 }
207 
208 #endif // INCLUDE_DIJKSTRATRSP_PGR_DIJKSTRATRSP_HPP_
Path dijkstraTRSP(G &graph, const std::vector< Restriction > &restrictions, const std::vector< pgr_edge_t > &edges, int64_t source, int64_t target, bool only_cost, bool strict)
static edge_t edges[22573]
std::vector< Restriction > m_restrictions
Definition: trsp.h:31
void transform(pgrouting::DirectedGraph &digraph)
void insert_vertices(const T *edges, int64_t count)
void getDijkstraSolution(G &graph)
Path dijkstra(G &graph, int64_t start_vertex, int64_t end_vertex, bool only_cost=false)
Dijkstra 1 to 1.
std::vector< int64_t > m_edges_in_path
bool empty() const
void executeDijkstraTRSP(G &graph)
Assertions Handling.
bool has_a_restriction(int64_t edge, int64_t index)
size_t size() const
std::ostringstream log
std::vector< int64_t > restrict_edges() const
Definition: restriction.h:54