PGROUTING  2.6
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 
31 #include <sstream>
32 #include <deque>
33 #include <vector>
34 #include <set>
35 #include <limits>
36 
37 #include "c_types/line_graph_rt.h"
39 #include "cpp_common/pgr_assert.h"
41 
42 
43 template < class G >
45  public:
47  G& graph,
48  const std::vector< Restriction >& restrictions,
49  const std::vector< pgr_edge_t >& edges,
50  int64_t source,
51  int64_t target,
52  bool only_cost,
53  bool strict);
54  void clear();
55 
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 
62  private:
63  typedef typename G::V V;
66  int64_t m_start;
67  int64_t m_end;
68  std::vector< Restriction > m_restrictions;
69  std::vector< int64_t > m_edges_in_path;
71  bool m_strict;
72 
74 
75  public:
76  std::ostringstream log;
77 };
78 
79 template < class G >
81 }
82 
83 template < class G >
84 Path
86  G& graph,
87  const std::vector< Restriction >& restrictions,
88  const std::vector< pgr_edge_t >& edges,
89  int64_t start_vertex,
90  int64_t end_vertex,
91  bool only_cost,
92  bool strict) {
93  if (start_vertex == end_vertex)
94  return Path();
95  if (!graph.has_vertex(start_vertex) || !graph.has_vertex(end_vertex))
96  return Path();
97 
98  m_only_cost = only_cost;
99  v_source = graph.get_V(start_vertex);
100  v_target = graph.get_V(end_vertex);
101  m_start = start_vertex;
102  m_end = end_vertex;
103  m_restrictions = restrictions;
104  m_strict = strict;
105  executeDijkstraTRSP(graph);
106  if (curr_result_path.size() || graph.m_gType == UNDIRECTED)
107  return curr_result_path;
108 
109 #if 0
111  line.insert_vertices(edges);
112  auto line_graph_edges = line.transform(graph);
113  log << "\nGraph before removing restrictions\n" << line << "\n";
114  auto remaining_restrictions = line.remove_restricted_edges(m_restrictions);
115  log << "\n Graph after removing restrictions\n" << line << "\n";
116 
117  log << line.log.str().c_str() << "\n\n\n";
118 
119  line.create_virtual_vertices();
120  log << line << "\n";
121 #endif
122 
123  return curr_result_path;
124 }
125 
126 template < class G >
128  Path path;
129 
130  Pgr_dijkstra< G > fn_dijkstra;
131  path = fn_dijkstra.dijkstra(graph, m_start, m_end);
132 
133  if (path.empty()) return;
134  curr_result_path = path;
135 }
136 
137 template < class G >
138 bool Pgr_dijkstraTRSP< G >::has_a_restriction(int64_t edge, int64_t index) {
139  auto lower_bound_cmp = [](const Restriction& r, const int64_t& target) {
140  return r.restrict_edges()[0] < target;
141  };
142  auto edge_index = std::lower_bound(m_restrictions.begin(),
143  m_restrictions.end(), edge, lower_bound_cmp) - m_restrictions.begin();
144  log << "\nResult generated from lower_bound\n";
145  while (edge_index < (int64_t)m_restrictions.size()) {
146  auto r_edges = m_restrictions[edge_index].restrict_edges();
147  if (r_edges[0] != edge) break;
148  log << m_restrictions[edge_index] << "\n";
149  bool okay = true;
150  size_t temp_edge_index = index;
151 
152  for (auto &edge_id : r_edges) {
153  if (temp_edge_index >= m_edges_in_path.size() ||
154  m_edges_in_path[temp_edge_index] != edge_id) {
155  okay = false;
156  break;
157  }
158  temp_edge_index++;
159  }
160  log << "\nokay value = " << okay <<"\n";
161  if (okay) return true;
162  edge_index++;
163  }
164  log << "Ends Here\n";
165  return false;
166 }
167 
168 template < class G >
170  auto sort_cmp = [](const Restriction& left,
171  const Restriction& right) -> bool {
172  return left.restrict_edges()[0] <= right.restrict_edges()[0];
173  };
174  std::stable_sort(m_restrictions.begin(), m_restrictions.end(),
175  sort_cmp);
176  log << "\nRestriction array after sorting.\n";
177  for (auto &it : m_restrictions) log << it << "\n";
178  log << "\nEnd\n";
179  size_t index = 0;
180  for (auto &edge : m_edges_in_path) {
181  if (has_a_restriction(edge, index))
182  return true;
183  index++;
184  }
185  return false;
186 }
187 
188 template < class G >
190  clear();
191  getDijkstraSolution(graph);
193 
194  for (auto &path : curr_result_path) {
195  m_edges_in_path.push_back(path.edge);
196  }
197  while (m_edges_in_path.size() && m_edges_in_path.back() == -1) {
198  m_edges_in_path.pop_back();
199  }
200 
201  log << "Edges in m_edges_in_path:-------------------\n";
202  for (auto &it : m_edges_in_path) log << it << "\n";
203  log << "---------------------------------------------\n";
204  bool sol = has_restriction();
205  log << "Result of valid solution: " << sol << "\n";
206  if (sol) curr_result_path = Path();
207 }
208 
209 #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)
std::vector< Restriction > m_restrictions
Definition: trsp.h:31
boost::adjacency_list< boost::vecS, boost::vecS, boost::bidirectionalS, Line_vertex, Basic_edge > LinearDirectedGraph
Data type to handle graph -> lineGaph transformation.
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