PGROUTING  2.6
pgrouting::tsp::Dmatrix Class Reference

#include "Dmatrix.h"

Collaboration diagram for pgrouting::tsp::Dmatrix:

Public Member Functions

 Dmatrix ()=default
 
 Dmatrix (const std::vector< Matrix_cell_t > &data_costs)
 
double comparable_distance (size_t i, size_t j) const
 
double distance (int64_t i, int64_t j) const
 
double distance (size_t i, size_t j) const
 
double empty () const
 
int64_t get_id (size_t idx) const
 idx -> original id More...
 
size_t get_index (int64_t id) const
 original id -> idx More...
 
const std::vector< double > & get_row (size_t idx) const
 returns a row of distances More...
 
bool has_id (int64_t id) const
 original id -> true More...
 
bool has_no_infinity () const
 
bool is_symmetric () const
 
bool obeys_triangle_inequality () const
 Triangle Inequality Theorem. More...
 
void set (size_t i, size_t j, double dist)
 sets a special value for the distance(i,j) More...
 
size_t size () const
 |idx| More...
 
double tourCost (const Tour &tour) const
 tour evaluation More...
 

Protected Member Functions

void set_ids (const std::vector< matrix_cell > &data_costs)
 

Protected Attributes

std::vector< int64_t > ids
 

Private Types

typedef std::vector< std::vector< double > > Costs
 

Private Member Functions

std::vector< double > & operator[] (size_t i)
 
const std::vector< double > & operator[] (size_t i) const
 

Private Attributes

Costs costs
 

Friends

std::ostream & operator<< (std::ostream &log, const Dmatrix &matrix)
 

Detailed Description

Definition at line 42 of file Dmatrix.h.

Member Typedef Documentation

typedef std::vector< std::vector < double > > pgrouting::tsp::Dmatrix::Costs
private

Definition at line 125 of file Dmatrix.h.

Constructor & Destructor Documentation

pgrouting::tsp::Dmatrix::Dmatrix ( )
default
pgrouting::tsp::Dmatrix::Dmatrix ( const std::vector< Matrix_cell_t > &  data_costs)
explicit

Definition at line 103 of file Dmatrix.cpp.

References costs, get_index(), ids, and set_ids().

103  {
104  set_ids(data_costs);
105  costs.resize(
106  ids.size(),
107  std::vector<double>(
108  ids.size(),
109  (std::numeric_limits<double>::max)()));
110 
111  for (const auto &data : data_costs) {
112  costs[get_index(data.from_vid)][get_index(data.to_vid)] = data.cost;
113  }
114 
115  for (size_t i = 0; i < costs.size(); ++i) {
116  costs[i][i] = 0;
117  }
118 }
void set_ids(const std::vector< matrix_cell > &data_costs)
Definition: Dmatrix.cpp:63
std::vector< int64_t > ids
Definition: Dmatrix.h:122
size_t get_index(int64_t id) const
original id -> idx
Definition: Dmatrix.cpp:90

Here is the call graph for this function:

Member Function Documentation

double pgrouting::tsp::Dmatrix::comparable_distance ( size_t  i,
size_t  j 
) const
inline

Definition at line 103 of file Dmatrix.h.

References distance().

103  {
104  return distance(i, j);}
double distance(int64_t i, int64_t j) const
Definition: Dmatrix.h:106

Here is the call graph for this function:

double pgrouting::tsp::Dmatrix::distance ( int64_t  i,
int64_t  j 
) const
inline

Definition at line 106 of file Dmatrix.h.

References get_index().

Referenced by comparable_distance(), pgrouting::vrp::Dnode::distance(), do_pgr_tsp(), and tourCost().

106  {
107  return distance(get_index(i), get_index(j));}
double distance(int64_t i, int64_t j) const
Definition: Dmatrix.h:106
size_t get_index(int64_t id) const
original id -> idx
Definition: Dmatrix.cpp:90

Here is the call graph for this function:

Here is the caller graph for this function:

double pgrouting::tsp::Dmatrix::distance ( size_t  i,
size_t  j 
) const
inline

Definition at line 109 of file Dmatrix.h.

References costs, and operator<<.

109  {
110  return costs[i][j];}
double pgrouting::tsp::Dmatrix::empty ( ) const
inline

Definition at line 116 of file Dmatrix.h.

References ids, and set_ids().

Referenced by pgrouting::vrp::Fleet::build_fleet(), pgrouting::vrp::PD_Orders::build_orders(), and pgrouting::vrp::Pgr_pickDeliver::Pgr_pickDeliver().

116  {
117  return ids.empty();
118  }
std::vector< int64_t > ids
Definition: Dmatrix.h:122

Here is the call graph for this function:

Here is the caller graph for this function:

int64_t pgrouting::tsp::Dmatrix::get_id ( size_t  idx) const

idx -> original id

Parameters
[in]idx- index (i-th coordinate)
Returns
the original id corresponding to idx

Definition at line 96 of file Dmatrix.cpp.

References ids.

Referenced by do_pgr_tsp(), and set().

96  {
97  return ids[id];
98 }
std::vector< int64_t > ids
Definition: Dmatrix.h:122

Here is the caller graph for this function:

size_t pgrouting::tsp::Dmatrix::get_index ( int64_t  id) const

original id -> idx

given a users id returns the internal index

Parameters
[in]id- original id
Returns
idx index of the id in the distance table

in[] id returns index

Definition at line 90 of file Dmatrix.cpp.

References ids.

Referenced by pgrouting::vrp::Dnode::distance(), distance(), Dmatrix(), do_pgr_tsp(), pgrouting::tsp::operator<<(), and set().

90  {
91  auto pos = std::lower_bound(ids.begin(), ids.end(), id);
92  return pos - ids.begin();
93 }
std::vector< int64_t > ids
Definition: Dmatrix.h:122

Here is the caller graph for this function:

const std::vector<double>& pgrouting::tsp::Dmatrix::get_row ( size_t  idx) const
inline

returns a row of distances

Parameters
[in]idx- row index
Returns
distances from idx to all other coordinates

Definition at line 100 of file Dmatrix.h.

References costs.

100  {
101  return costs[idx];}
bool pgrouting::tsp::Dmatrix::has_id ( int64_t  id) const

original id -> true

Parameters
[in]id- original id
Returns
true if id is in the distance table

Definition at line 78 of file Dmatrix.cpp.

References ids.

Referenced by do_pgr_tsp(), and set().

78  {
79  auto pos = std::lower_bound(ids.begin(), ids.end(), id);
80  return *pos == id;
81 }
std::vector< int64_t > ids
Definition: Dmatrix.h:122

Here is the caller graph for this function:

bool pgrouting::tsp::Dmatrix::has_no_infinity ( ) const

Definition at line 121 of file Dmatrix.cpp.

References costs.

Referenced by do_pgr_pickDeliver(), and do_pgr_tsp().

121  {
122  for (const auto &row : costs) {
123  for (const auto &val : row) {
124  if (val == (std::numeric_limits<double>::infinity)()) return false;
125  if (val == (std::numeric_limits<double>::max)()) return false;
126  }
127  }
128  return true;
129 }

Here is the caller graph for this function:

bool pgrouting::tsp::Dmatrix::is_symmetric ( ) const

Definition at line 152 of file Dmatrix.cpp.

References costs, and pgassertwm.

Referenced by do_pgr_tsp().

152  {
153  for (size_t i = 0; i < costs.size(); ++i) {
154  for (size_t j = 0; j < costs.size(); ++j) {
155  if (0.000001 < std::fabs(costs[i][j] - costs[j][i])) {
156  std::ostringstream log;
157  log << "i \t" << i
158  << "j \t" << j
159  << "costs[i][j] \t" << costs[i][j]
160  << "costs[j][i] \t" << costs[j][i]
161  << "\n";
162  log << (*this);
163  pgassertwm(false, log.str());
164  return false;
165  }
166  }
167  }
168  return true;
169 }
#define pgassertwm(expr, msg)
Adds a message to the assertion.
Definition: pgr_assert.h:104

Here is the caller graph for this function:

bool pgrouting::tsp::Dmatrix::obeys_triangle_inequality ( ) const

Triangle Inequality Theorem.

The sum of the lengths of any two sides of a triangle is greater than the length of the third side. NOTE: can also be equal for streets costs[i][k] != inf costs[i][k] <= costs[i][j] + costs[j][k]

Definition at line 140 of file Dmatrix.cpp.

References costs.

140  {
141  for (size_t i = 0; i < costs.size(); ++i) {
142  for (size_t j = 0; j < costs.size(); ++j) {
143  for (size_t k = 0; k < costs.size(); ++k) {
144  if (!(costs[i][k] <= (costs[i][j] + costs[j][k]))) return false;
145  }
146  }
147  }
148  return true;
149 }
std::vector< double >& pgrouting::tsp::Dmatrix::operator[] ( size_t  i)
inlineprivate

Definition at line 127 of file Dmatrix.h.

127 {return costs[i];}
const std::vector< double >& pgrouting::tsp::Dmatrix::operator[] ( size_t  i) const
inlineprivate

Definition at line 128 of file Dmatrix.h.

128 {return costs[i];}
void pgrouting::tsp::Dmatrix::set ( size_t  i,
size_t  j,
double  dist 
)
inline

sets a special value for the distance(i,j)

Parameters
[in]i- index in matrix
[in]j- index in matrix
[in]dist- distance from i to j & from j to i

Definition at line 58 of file Dmatrix.h.

References costs, get_id(), get_index(), and has_id().

Referenced by do_pgr_tsp().

58  {
59  costs[i][j] = costs[j][i] = dist;}

Here is the call graph for this function:

Here is the caller graph for this function:

void pgrouting::tsp::Dmatrix::set_ids ( const std::vector< matrix_cell > &  data_costs)
protected

Definition at line 63 of file Dmatrix.cpp.

References ids.

Referenced by Dmatrix(), and empty().

63  {
64  ids.reserve(data_costs.size() * 2);
65  for (const auto &cost : data_costs) {
66  ids.push_back(cost.from_vid);
67  ids.push_back(cost.to_vid);
68  }
69  std::sort(ids.begin(), ids.end());
70  ids.erase(std::unique(ids.begin(), ids.end()), ids.end());
71  /*
72  * freeing up unused space
73  */
74  ids.shrink_to_fit();
75 }
std::vector< int64_t > ids
Definition: Dmatrix.h:122

Here is the caller graph for this function:

size_t pgrouting::tsp::Dmatrix::size ( ) const
inline

|idx|

Returns
the total number of coordinates

Definition at line 86 of file Dmatrix.h.

References ids, and tourCost().

Referenced by do_pgr_tsp().

86 {return ids.size();}
std::vector< int64_t > ids
Definition: Dmatrix.h:122

Here is the call graph for this function:

Here is the caller graph for this function:

double pgrouting::tsp::Dmatrix::tourCost ( const Tour tour) const

tour evaluation

Parameters
[in]tour
Returns
total cost of traversing the tour

Definition at line 43 of file Dmatrix.cpp.

References pgrouting::tsp::Tour::cities, costs, distance(), and pgassert.

Referenced by do_pgr_tsp(), pgrouting::tsp::Tour::size(), and size().

43  {
44  double total_cost(0);
45  if (tour.cities.empty()) return total_cost;
46 
47  auto prev_id = tour.cities.front();
48  for (const auto &id : tour.cities) {
49  if (id == tour.cities.front()) continue;
50 
51  pgassert(distance(prev_id, id) != (std::numeric_limits<double>::max)());
52 
53  total_cost += costs[prev_id][id];
54  prev_id = id;
55  }
56  total_cost += costs[prev_id][tour.cities.front()];
57  return total_cost;
58 }
double distance(int64_t i, int64_t j) const
Definition: Dmatrix.h:106
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81

Here is the call graph for this function:

Here is the caller graph for this function:

Friends And Related Function Documentation

std::ostream& operator<< ( std::ostream &  log,
const Dmatrix matrix 
)
friend

Definition at line 175 of file Dmatrix.cpp.

Referenced by distance().

175  {
176  for (const auto id : matrix.ids) {
177  log << "\t" << id;
178  }
179  log << "\n";
180  size_t i = 0;
181  for (const auto row : matrix.costs) {
182  size_t j = 0;
183  for (const auto cost : row) {
184  log << "Internal(" << i << "," << j << ")"
185  << "\tUsers(" << matrix.ids[i] << "," << matrix.ids[j] << ")"
186  << "\t = " << cost
187 #if 0
188  << "\t(" << matrix.get_index(matrix.ids[i])
189  << "," << matrix.get_index(matrix.ids[j]) << ")"
190  << "\t = " << matrix.costs[i][j]
191  << "\t = " << matrix.costs[j][i]
192  << "=inf:"
193  << (matrix.costs[i][j] ==
194  (std::numeric_limits<double>::infinity)())
195  << "=inf:"
196  << (matrix.costs[j][i] ==
197  (std::numeric_limits<double>::infinity)())
198 #endif
199  << "\n";
200  ++j;
201  }
202  ++i;
203  }
204 #if 0
205  for (size_t i = 0; i < matrix.costs.size(); ++i) {
206  for (size_t j = 0; j < matrix.costs.size(); ++j) {
207  for (size_t k = 0; k < matrix.costs.size(); ++k) {
208  log << matrix.costs[i][k] << " <= ("
209  << matrix.costs[i][j] << " + " << matrix.costs[j][k] << ")"
210  << (matrix.costs[i][k]
211  <= (matrix.costs[i][j] + matrix.costs[j][k]))
212  << "\n";
213  }
214  }
215  }
216 #endif
217  return log;
218 }

Member Data Documentation

Costs pgrouting::tsp::Dmatrix::costs
private
std::vector<int64_t> pgrouting::tsp::Dmatrix::ids
protected

The documentation for this class was generated from the following files: