#include "Dmatrix.h"

Collaboration diagram for pgrouting::tsp::Dmatrix:

Public Member Functions
	Dmatrix ()=default

	Dmatrix (const std::map< std::pair< double, double >, int64_t > &euclidean_data)

	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

bool	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 43 of file Dmatrix.h.

Member Typedef Documentation

◆ Costs

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

private

Definition at line 127 of file Dmatrix.h.

Constructor & Destructor Documentation

◆ Dmatrix() [1/3]

pgrouting::tsp::Dmatrix::Dmatrix ( )

default

◆ Dmatrix() [2/3]

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

explicit

Definition at line 108 of file Dmatrix.cpp.

                                                               {
     set_ids(data_costs);
     costs.resize(
             ids.size(),
             std::vector<double>(
                 ids.size(),
                 (std::numeric_limits<double>::max)()));
  
     for (const auto &data : data_costs) {
         costs[get_index(data.from_vid)][get_index(data.to_vid)] = data.cost;
     }
  
     for (size_t i = 0; i < costs.size(); ++i) {
         costs[i][i] = 0;
     }
 }

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

◆ Dmatrix() [3/3]

pgrouting::tsp::Dmatrix::Dmatrix ( const std::map< std::pair< double, double >, int64_t > & euclidean_data )

explicit

Definition at line 136 of file Dmatrix.cpp.

                                                                                {
     ids.reserve(euclidean_data.size());
     for (const auto &e: euclidean_data) {
         ids.push_back(e.second);
     }
     costs.resize(
             ids.size(),
             std::vector<double>(
                 ids.size(),
                 (std::numeric_limits<double>::max)()));
  
     for (const auto &from : euclidean_data) {
         for (const auto &to : euclidean_data) {
             auto from_id = get_index(from.second);
             auto to_id = get_index(to.second);
             costs[from_id][to_id] = get_distance(from.first, to.first);
             costs[to_id][from_id] = costs[from_id][to_id];
         }
     }
  
     for (size_t i = 0; i < costs.size(); ++i) {
         costs[i][i] = 0;
     }
 }

References costs, pgrouting::tsp::get_distance(), get_index(), and ids.

Member Function Documentation

◆ comparable_distance()

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

inline

Definition at line 105 of file Dmatrix.h.

105 {

106 return distance(i, j);}

References distance().

◆ distance() [1/2]

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

inline

Definition at line 108 of file Dmatrix.h.

108 {

109 return distance(get_index(i), get_index(j));}

References get_index().

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

◆ distance() [2/2]

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

inline

Definition at line 111 of file Dmatrix.h.

111 {

112 return costs[i][j];}

References costs.

◆ empty()

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

inline

Definition at line 118 of file Dmatrix.h.

                        {
         return ids.empty();
     }

References ids.

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

◆ get_id()

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 101 of file Dmatrix.cpp.

                                {
     return ids[id];
 }

References ids.

Referenced by do_pgr_tsp().

◆ get_index()

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 93 of file Dmatrix.cpp.

                                    {
     for (size_t pos = 0; pos < ids.size(); ++pos) {
         if (ids[pos] == id) return pos;
     }
     throw std::make_pair(std::string("(INTERNAL) Dmatrix: Unable to find node on matrix"), id);
 }

References ids.

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

◆ get_row()

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 102 of file Dmatrix.h.

102 {

103 return costs[idx];}

References costs.

◆ has_id()

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 79 of file Dmatrix.cpp.

                                 {
     for (const auto &i : ids) {
         if (i == id) return true;
     }
     return false;
 }

References ids.

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

◆ has_no_infinity()

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

Definition at line 162 of file Dmatrix.cpp.

                                {
     for (const auto &row : costs) {
         for (const auto &val : row) {
             if (val == (std::numeric_limits<double>::infinity)()) return false;
             if (val == (std::numeric_limits<double>::max)()) return false;
         }
     }
     return true;
 }

References costs.

Referenced by do_pgr_pickDeliver(), and do_pgr_tsp().

◆ is_symmetric()

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

Definition at line 193 of file Dmatrix.cpp.

                             {
     for (size_t i = 0; i < costs.size(); ++i) {
         for (size_t j = 0; j < costs.size(); ++j) {
             if (0.000001 < std::fabs(costs[i][j] - costs[j][i])) {
                 std::ostringstream log;
                 log << "i \t" << i
                     << "j \t" << j
                     << "costs[i][j] \t" << costs[i][j]
                     << "costs[j][i] \t" << costs[j][i]
                     << "\n";
                 log << (*this);
                 pgassertwm(false, log.str());
                 return false;
             }
         }
     }
     return true;
 }

References costs, and pgassertwm.

Referenced by do_pgr_tsp().

◆ obeys_triangle_inequality()

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 181 of file Dmatrix.cpp.

                                          {
     for (size_t i = 0; i < costs.size(); ++i) {
         for (size_t j = 0; j < costs.size(); ++j) {
             for (size_t k = 0; k < costs.size(); ++k) {
                 if (!(costs[i][k] <= (costs[i][j] + costs[j][k]))) return false;
             }
         }
     }
     return true;
 }

References costs.

◆ operator[]() [1/2]

std::vector< double >& pgrouting::tsp::Dmatrix::operator[] ( size_t i )

inlineprivate

Definition at line 129 of file Dmatrix.h.

129 {return costs[i];}

References costs.

◆ operator[]() [2/2]

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

inlineprivate

Definition at line 130 of file Dmatrix.h.

130 {return costs[i];}

References costs.

◆ set()

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 60 of file Dmatrix.h.

60 {

61 costs[i][j] = costs[j][i] = dist;}

References costs.

Referenced by do_pgr_tsp().

◆ set_ids()

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

protected

Definition at line 64 of file Dmatrix.cpp.

                                                               {
     ids.reserve(data_costs.size() * 2);
     for (const auto &cost : data_costs) {
         ids.push_back(cost.from_vid);
         ids.push_back(cost.to_vid);
     }
     std::sort(ids.begin(), ids.end());
     ids.erase(std::unique(ids.begin(), ids.end()), ids.end());
     /*
      * freeing up unused space
      */
     ids.shrink_to_fit();
 }

References ids.

Referenced by Dmatrix().

◆ size()

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

inline

|idx|

Returns: the total number of coordinates

Definition at line 88 of file Dmatrix.h.

88 {return ids.size();}

References ids.

Referenced by do_pgr_tsp().

◆ tourCost()

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

tour evaluation

Parameters

[in] tour

Returns: total cost of traversing the tour

Definition at line 44 of file Dmatrix.cpp.

                                         {
     double total_cost(0);
     if (tour.cities.empty()) return total_cost;
  
     auto prev_id = tour.cities.front();
     for (const auto &id : tour.cities) {
         if (id == tour.cities.front()) continue;
  
         pgassert(distance(prev_id, id) != (std::numeric_limits<double>::max)());
  
         total_cost += costs[prev_id][id];
         prev_id = id;
     }
     total_cost += costs[prev_id][tour.cities.front()];
     return total_cost;
 }

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

Referenced by do_pgr_tsp().

Friends And Related Function Documentation

◆ operator<<

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

friend

Definition at line 216 of file Dmatrix.cpp.

                                                                {
     for (const auto id : matrix.ids) {
         log << "\t" << id;
     }
     log << "\n";
     size_t i = 0;
     for (const auto &row : matrix.costs) {
         size_t j = 0;
         for (const auto cost : row) {
             log << "Internal(" << i << "," << j << ")"
                 << "\tUsers(" << matrix.ids[i] << "," << matrix.ids[j] << ")"
                 << "\t = " << cost
 #if 0
                 << "\t(" << matrix.get_index(matrix.ids[i])
                 << "," << matrix.get_index(matrix.ids[j]) << ")"
                 << "\t = " << matrix.costs[i][j]
                 << "\t = " << matrix.costs[j][i]
                 << "=inf:"
                 <<  (matrix.costs[i][j] ==
                         (std::numeric_limits<double>::infinity)())
                 << "=inf:"
                 <<  (matrix.costs[j][i] ==
                         (std::numeric_limits<double>::infinity)())
 #endif
                 << "\n";
             ++j;
         }
         ++i;
     }
 #if 0
     for (size_t i = 0; i < matrix.costs.size(); ++i) {
         for (size_t j = 0; j < matrix.costs.size(); ++j) {
             for (size_t k = 0; k < matrix.costs.size(); ++k) {
                 log << matrix.costs[i][k] << " <= ("
                     << matrix.costs[i][j] << " + "  << matrix.costs[j][k] << ")"
                     << (matrix.costs[i][k]
                             <= (matrix.costs[i][j] + matrix.costs[j][k]))
                     << "\n";
             }
         }
     }
 #endif
     return log;
 }

Member Data Documentation

◆ costs

Costs pgrouting::tsp::Dmatrix::costs

private

Definition at line 128 of file Dmatrix.h.

Referenced by distance(), Dmatrix(), get_row(), has_no_infinity(), is_symmetric(), obeys_triangle_inequality(), pgrouting::tsp::operator<<(), operator[](), set(), and tourCost().

◆ ids

std::vector<int64_t> pgrouting::tsp::Dmatrix::ids

protected

Definition at line 124 of file Dmatrix.h.

Referenced by Dmatrix(), empty(), get_id(), get_index(), has_id(), pgrouting::tsp::operator<<(), set_ids(), and size().

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

Public Member Functions

Protected Member Functions

Protected Attributes

Private Types

Private Member Functions

Private Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ Costs

Constructor & Destructor Documentation

◆ Dmatrix() [1/3]

◆ Dmatrix() [2/3]

◆ Dmatrix() [3/3]

Member Function Documentation

◆ comparable_distance()

◆ distance() [1/2]

◆ distance() [2/2]

◆ empty()

◆ get_id()

◆ get_index()

◆ get_row()

◆ has_id()

◆ has_no_infinity()

◆ is_symmetric()

◆ obeys_triangle_inequality()

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ set()

◆ set_ids()

◆ size()

◆ tourCost()

Friends And Related Function Documentation

◆ operator<<

Member Data Documentation

◆ costs

◆ ids