PGROUTING  2.6
pgrouting::tsp::eucledianDmatrix Class Reference

#include "eucledianDmatrix.h"

Collaboration diagram for pgrouting::tsp::eucledianDmatrix:

Public Member Functions

 eucledianDmatrix ()=default
 
 eucledianDmatrix (const std::vector< Coordinate_t > &data_coordinates)
 
double comparable_distance (size_t i, size_t j) const
 
double distance (size_t i, size_t j) 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
 
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 ()
 

Protected Attributes

std::vector< int64_t > ids
 

Private Attributes

size_t column
 
std::vector< Coordinate_tcoordinates
 
size_t row
 
double special_distance
 

Friends

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

Detailed Description

Definition at line 40 of file eucledianDmatrix.h.

Constructor & Destructor Documentation

pgrouting::tsp::eucledianDmatrix::eucledianDmatrix ( )
default
pgrouting::tsp::eucledianDmatrix::eucledianDmatrix ( const std::vector< Coordinate_t > &  data_coordinates)
explicit

Definition at line 115 of file eucledianDmatrix.cpp.

References coordinates, Coordinate_t::id, and set_ids().

117  : coordinates(data_coordinates) {
118  set_ids();
119  std::sort(coordinates.begin(), coordinates.end(),
120  [](const Coordinate_t &lhs, const Coordinate_t &rhs)
121  {return lhs.id < rhs.id;});
122  }
std::vector< Coordinate_t > coordinates
int64_t id
Definition: coordinate_t.h:58

Here is the call graph for this function:

Member Function Documentation

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

Definition at line 55 of file eucledianDmatrix.cpp.

References column, coordinates, row, and special_distance.

Referenced by distance(), and size().

55  {
56  if (special_distance >= 0 &&
57  ((row == i && column == j)
58  ||(row == j && column == i))) {
60  }
61  auto dx = coordinates[i].x - coordinates[j].x;
62  auto dy = coordinates[i].y - coordinates[j].y;
63  return dx * dx + dy * dy;
64 }
std::vector< Coordinate_t > coordinates

Here is the caller graph for this function:

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

Definition at line 67 of file eucledianDmatrix.cpp.

References column, comparable_distance(), row, and special_distance.

Referenced by do_pgr_eucledianTSP(), get_row(), size(), and tourCost().

67  {
68  if (special_distance >= 0 &&
69  ((row == i && column == j)
70  ||(row == j && column == i))) {
71  return special_distance;
72  }
73  if (i == j) return 0;
74  return std::sqrt(comparable_distance(i, j));
75 }
double comparable_distance(size_t i, size_t j) const

Here is the call graph for this function:

Here is the caller graph for this function:

int64_t pgrouting::tsp::eucledianDmatrix::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 108 of file eucledianDmatrix.cpp.

References ids.

Referenced by do_pgr_eucledianTSP(), and set().

108  {
109  return ids[id];
110 }

Here is the caller graph for this function:

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

original id -> idx

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

Definition at line 102 of file eucledianDmatrix.cpp.

References ids.

Referenced by do_pgr_eucledianTSP(), and set().

102  {
103  auto pos = std::lower_bound(ids.begin(), ids.end(), id);
104  return pos - ids.begin();
105 }

Here is the caller graph for this function:

const std::vector< double > pgrouting::tsp::eucledianDmatrix::get_row ( size_t  idx) const

returns a row of distances

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

Definition at line 42 of file eucledianDmatrix.cpp.

References distance(), ids, and pgassert.

Referenced by size().

42  {
43  std::vector<double> result;
44 
45  for (size_t j = 0; j < ids.size(); ++j) {
46  result.push_back(distance(i, j));
47  }
48 
49  pgassert(result.size() == ids.size());
50  return result;
51 }
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
double distance(size_t i, size_t j) const

Here is the call graph for this function:

Here is the caller graph for this function:

bool pgrouting::tsp::eucledianDmatrix::has_id ( int64_t  id) const

original id -> true

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

Definition at line 96 of file eucledianDmatrix.cpp.

References ids.

Referenced by do_pgr_eucledianTSP(), and set().

96  {
97  auto pos = std::lower_bound(ids.begin(), ids.end(), id);
98  return *pos == id;
99 }

Here is the caller graph for this function:

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

Definition at line 139 of file eucledianDmatrix.cpp.

139  {
140  return true;
141 }
bool pgrouting::tsp::eucledianDmatrix::is_symmetric ( ) const

Definition at line 149 of file eucledianDmatrix.cpp.

149  {
150  return true;
151 }
bool pgrouting::tsp::eucledianDmatrix::obeys_triangle_inequality ( ) const

Definition at line 144 of file eucledianDmatrix.cpp.

144  {
145  return true;
146 }
void pgrouting::tsp::eucledianDmatrix::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 57 of file eucledianDmatrix.h.

References column, get_id(), get_index(), has_id(), row, and special_distance.

Referenced by do_pgr_eucledianTSP().

Here is the call graph for this function:

Here is the caller graph for this function:

void pgrouting::tsp::eucledianDmatrix::set_ids ( )
protected

Definition at line 125 of file eucledianDmatrix.cpp.

References coordinates, ids, and pgassertwm.

Referenced by eucledianDmatrix(), and size().

125  {
126  ids.reserve(coordinates.size());
127  for (const auto &data : coordinates) {
128  ids.push_back(data.id);
129  }
130  std::sort(ids.begin(), ids.end());
131 #ifndef NDEBUG
132  auto total = ids.size();
133 #endif
134  ids.erase(std::unique(ids.begin(), ids.end()), ids.end());
135  pgassertwm(total == ids.size(), "Duplicated id found");
136 }
#define pgassertwm(expr, msg)
Adds a message to the assertion.
Definition: pgr_assert.h:104
std::vector< Coordinate_t > coordinates

Here is the caller graph for this function:

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

|idx|

Returns
the total number of coordinates

Definition at line 86 of file eucledianDmatrix.h.

References comparable_distance(), distance(), get_row(), ids, operator<<, set_ids(), and tourCost().

Referenced by do_pgr_eucledianTSP().

86 {return ids.size();}

Here is the call graph for this function:

Here is the caller graph for this function:

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

tour evaluation

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

Definition at line 78 of file eucledianDmatrix.cpp.

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

Referenced by do_pgr_eucledianTSP(), and size().

78  {
79  double total_cost(0);
80  if (tour.cities.empty()) return total_cost;
81 
82  auto prev_id = tour.cities.front();
83  for (const auto &id : tour.cities) {
84  if (id == tour.cities.front()) continue;
85 
86  total_cost += distance(prev_id, id);
87  prev_id = id;
88  }
89  total_cost += distance(prev_id, tour.cities.front());
90  return total_cost;
91 }
double distance(size_t i, size_t j) const

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 eucledianDmatrix matrix 
)
friend

Definition at line 153 of file eucledianDmatrix.cpp.

Referenced by size().

153  {
154  for (const auto id : matrix.ids) {
155  log << "\t" << id;
156  }
157  log << "\n";
158  for (const auto row : matrix.coordinates) {
159  log << row.id << "(" << row.x << "," << row.y << ")\n";
160  }
161  return log;
162 }

Member Data Documentation

size_t pgrouting::tsp::eucledianDmatrix::column
private

Definition at line 117 of file eucledianDmatrix.h.

Referenced by comparable_distance(), distance(), and set().

std::vector< Coordinate_t > pgrouting::tsp::eucledianDmatrix::coordinates
private
std::vector<int64_t> pgrouting::tsp::eucledianDmatrix::ids
protected
size_t pgrouting::tsp::eucledianDmatrix::row
private

Definition at line 116 of file eucledianDmatrix.h.

Referenced by comparable_distance(), distance(), pgrouting::tsp::operator<<(), and set().

double pgrouting::tsp::eucledianDmatrix::special_distance
private

Definition at line 118 of file eucledianDmatrix.h.

Referenced by comparable_distance(), distance(), and set().


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