pgRouting  2.2
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Functions Variables Pages
shooting_star_relax.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 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
25 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek,
26 //
27 // Copyright 2007 Orkney, Inc.
28 // Author: Anton A. Patrushev
29 //
30 // Distributed under the Boost Software License, Version 1.0. (See
31 // accompanying file LICENSE_1_0.txt or copy at
32 // http://www.boost.org/LICENSE_1_0.txt)
33 //=======================================================================
34 #ifndef BOOST_GRAPH_SHOOTING_STAR_RELAX_HPP
35 #define BOOST_GRAPH_SHOOTING_STAR_RELAX_HPP
36 
37 #include <boost/version.hpp>
38 #include <functional>
39 #include <boost/limits.hpp> // for numeric limits
40 #include <boost/graph/graph_traits.hpp>
41 #if BOOST_VERSION > 103900
42 #include <boost/property_map/property_map.hpp>
43 #else
44 #include <boost/property_map.hpp>
45 #endif
46 
47 #include <postgres.h>
48 
49 #define U_TURN_COST 100000
50 
51 bool is_equal ( int a[], int b[], int size )
52 {
53  for ( int i = 0; i < size; i++ )
54  {
55  if ( a[i] != b[i] )
56  return false;
57  }
58 
59  return true;
60 }
61 
62 namespace boost {
63 
64  // The following version of the plus functor prevents
65  // problems due to overflow at positive infinity.
66 
67  template <class T>
68  struct closed_plus
69  {
70  // std::abs just isn't portable :(
71  template <class X>
72  inline X my_abs(const X& x) const { return x < 0 ? -x : x; }
73 
74  T operator()(const T& a, const T& b) const {
75  using namespace std;
76  T inf = (numeric_limits<T>::max)();
77  if (b > 0 && my_abs(inf - a) < b)
78  return inf;
79  return a + b;
80  }
81  };
82 
83  template <class Edge, class Graph, class WeightMap, class EdgeMap,
84  class PredecessorMap, class DistanceMap, class CostMap,
85  class BinaryFunction, class BinaryPredicate>
86  bool relax(Edge e,
87  Edge pe,
88  Edge s,
89  const Graph& g, const WeightMap& w, const EdgeMap& em,
90  PredecessorMap& p, DistanceMap& d, CostMap& c,
91  const BinaryFunction& combine, const BinaryPredicate& compare,
92  int e_max_id)
93  {
94  typedef typename graph_traits<Graph>::directed_category DirCat;
95  bool is_undirected = is_same<DirCat, undirected_tag>::value;
96 
97  typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
98 
99  Vertex u = source(e, g), v = target(e, g), pu = source(pe, g);
100 
101  typedef typename property_traits<DistanceMap>::value_type D;
102  typedef typename property_traits<WeightMap>::value_type W;
103 
104  typedef typename property_traits<EdgeMap>::value_type E;
105 
106  D d_e = get(d, e);
107  D d_pe = get(d, pe);
108 
109  W w_e = get(w, e);
110 
111  //edge where we came from
112  bool edge_exists;
113 
114  W w_pe_e;
115 
116  E w_pe = get(em, e);
117 
118  int contains = -1;
119 
120  Edge ce = pe;
121  int e_id;
122 
123  std::vector<Edge> edge_h;
124  typedef typename std::vector<Edge>::iterator It;
125 
126  for(int i=0; i< w_pe[g[e].id].size(); ++i)
127 
128  if(w_pe[g[e].id].at(i).second.size() < 1 || w_pe[g[e].id].at(i).second.back() > 0)
129  {
130 
131  for(int j=0; j<w_pe[g[e].id].at(i).second.size(); ++j)
132  {
133  e_id = g[ce].id;
134 
135  if(w_pe[g[e].id].at(i).second.at(j) == -1)
136  continue;
137 
138  if(w_pe[g[e].id].at(i).second.at(j) == e_id || w_pe[g[e].id].at(i).second.at(j)+e_max_id == e_id||
139  w_pe[g[e].id].at(i).second.at(j) == e_id+e_max_id || w_pe[g[e].id].at(i).second.at(j)+e_max_id == e_id+e_max_id)
140  {
141  contains = i;
142  edge_h.push_back(ce);
143  }
144  else if(i == contains)
145  {
146  contains = -1;
147  }
148 
149  ce = p[g[ce].id];
150  }
151 
152  }
153 
154  //calculate w_pe_e
155  if(contains >= 0)
156  {
157  w_pe_e = w_pe[g[e].id].at(contains).first;
158  }
159  //Check if it is a u-turn not in the beginning of route
160  else if( abs(g[e].id-g[pe].id) == e_max_id && g[e].id != g[s].id && g[pe].id != g[s].id )
161  {
162  w_pe_e = U_TURN_COST;
163  }
164  else
165  {
166  w_pe_e = 0;
167  }
168 
169  //Ugly combination with w_e_pe.
170 
171  if ( compare(combine(combine(d_pe, get(w, pe)), w_pe_e), d_e))
172  {
173  put(d, e, combine(combine(d_pe, get(w, pe)), w_pe_e));
174  p[g[e].id] = pe;
175 
176  return true;
177  }
178  else
179  {
180  return false;
181  }
182  }
183 
184  template <class Graph, class WeightMap, class EdgeMap,
185  class PredecessorMap, class DistanceMap>
186  bool relax(typename graph_traits<Graph>::edge_descriptor e,
187  const Graph& g, WeightMap w, EdgeMap em, PredecessorMap p, DistanceMap d)
188  {
189  typedef typename property_traits<DistanceMap>::value_type D;
190  typedef closed_plus<D> Combine;
191  typedef std::less<D> Compare;
192  return relax(e, g, w, em, p, d, Combine(), Compare());
193  }
194 
195 } // namespace boost
196 
197 #endif