pgrouting::tsp::EuclideanDmatrix Class Reference

#include "euclideanDmatrix.h"

Collaboration diagram for pgrouting::tsp::EuclideanDmatrix:

Public Member Functions
	EuclideanDmatrix ()=default
	EuclideanDmatrix (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_t >	coordinates
size_t	row
double	special_distance

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

Detailed Description

Definition at line 40 of file euclideanDmatrix.h.

Constructor & Destructor Documentation

EuclideanDmatrix() [1/2]

pgrouting::tsp::EuclideanDmatrix::EuclideanDmatrix ( )

default

EuclideanDmatrix() [2/2]

pgrouting::tsp::EuclideanDmatrix::EuclideanDmatrix ( const std::vector< Coordinate_t > &  data_coordinates )

explicit

Definition at line 119 of file euclideanDmatrix.cpp.

    : coordinates(data_coordinates) {
        set_ids();
        std::sort(coordinates.begin(), coordinates.end(),
                [](const Coordinate_t &lhs, const Coordinate_t &rhs)
                {return lhs.id < rhs.id;});
    }

References coordinates, and set_ids().

Member Function Documentation

comparable_distance()

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

Definition at line 55 of file euclideanDmatrix.cpp.

                                                              {
    if (special_distance >= 0 &&
            ((row == i && column == j)
             ||(row == j && column == i))) {
        return special_distance * special_distance;
    }
    auto dx = coordinates[i].x - coordinates[j].x;
    auto dy = coordinates[i].y - coordinates[j].y;
    return dx * dx + dy * dy;
}

References column, coordinates, row, and special_distance.

Referenced by distance().

distance()

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

Definition at line 67 of file euclideanDmatrix.cpp.

                                                   {
    if (special_distance >= 0 &&
            ((row == i && column == j)
             ||(row == j && column == i))) {
        return special_distance;
    }
    if (i == j) return 0;
    return std::sqrt(comparable_distance(i, j));
}

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

Referenced by do_pgr_euclideanTSP(), get_row(), and tourCost().

get_id()

int64_t pgrouting::tsp::EuclideanDmatrix::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 112 of file euclideanDmatrix.cpp.

                                        {
    return ids[id];
}

References ids.

Referenced by do_pgr_euclideanTSP().

get_index()

size_t pgrouting::tsp::EuclideanDmatrix::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 104 of file euclideanDmatrix.cpp.

                                            {
    for (size_t pos = 0; pos < ids.size(); ++pos) {
        if (ids[pos] == id) return pos;
    }
    return ids.size() + 1;
}

References ids.

Referenced by do_pgr_euclideanTSP().

get_row()

const std::vector< double > pgrouting::tsp::EuclideanDmatrix::get_row

(

size_t

idx

)

const

returns a row of distances

Parameters

[in]

idx

row index

Returns

distances from idx to all other coordinates

Definition at line 42 of file euclideanDmatrix.cpp.

                                        {
    std::vector<double> result;
 
    for (size_t j = 0; j < ids.size(); ++j) {
        result.push_back(distance(i, j));
    }
 
    pgassert(result.size() == ids.size());
    return result;
}

References distance(), ids, and pgassert.

has_id()

bool pgrouting::tsp::EuclideanDmatrix::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 96 of file euclideanDmatrix.cpp.

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

References ids.

Referenced by do_pgr_euclideanTSP().

has_no_infinity()

bool pgrouting::tsp::EuclideanDmatrix::has_no_infinity

(

)

const

Definition at line 143 of file euclideanDmatrix.cpp.

                                        {
    return true;
}

is_symmetric()

bool pgrouting::tsp::EuclideanDmatrix::is_symmetric

(

)

const

Definition at line 153 of file euclideanDmatrix.cpp.

                                     {
    return true;
}

obeys_triangle_inequality()

bool pgrouting::tsp::EuclideanDmatrix::obeys_triangle_inequality

(

)

const

Definition at line 148 of file euclideanDmatrix.cpp.

                                                  {
    return true;
}

set()

void pgrouting::tsp::EuclideanDmatrix::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 euclideanDmatrix.h.

                                              {
        row = i; column = j; special_distance = dist;}

References column, row, and special_distance.

Referenced by do_pgr_euclideanTSP().

set_ids()

void pgrouting::tsp::EuclideanDmatrix::set_ids ( )

protected

Definition at line 129 of file euclideanDmatrix.cpp.

                          {
    ids.reserve(coordinates.size());
    for (const auto &data : coordinates) {
        ids.push_back(data.id);
    }
    std::sort(ids.begin(), ids.end());
#ifndef NDEBUG
    auto total = ids.size();
#endif
    ids.erase(std::unique(ids.begin(), ids.end()), ids.end());
    pgassertwm(total == ids.size(), "Duplicated id found");
}

References coordinates, ids, and pgassertwm.

Referenced by EuclideanDmatrix().

size()

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

inline

|idx|

Returns

the total number of coordinates

Definition at line 86 of file euclideanDmatrix.h.

{return ids.size();}

References ids.

Referenced by do_pgr_euclideanTSP().

tourCost()

double pgrouting::tsp::EuclideanDmatrix::tourCost

(

const Tour &

tour

)

const

tour evaluation

Parameters

[in]

tour

Returns

total cost of traversing the tour

Definition at line 78 of file euclideanDmatrix.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;
 
        total_cost += distance(prev_id, id);
        prev_id = id;
    }
    total_cost += distance(prev_id, tour.cities.front());
    return total_cost;
}

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

Referenced by do_pgr_euclideanTSP().

Friends And Related Function Documentation

operator<<

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

friend

Definition at line 157 of file euclideanDmatrix.cpp.

                                                                        {
    for (const auto id : matrix.ids) {
        log << "\t" << id;
    }
    log << "\n";
    for (const auto row : matrix.coordinates) {
        log << row.id << "(" << row.x << "," << row.y << ")\n";
    }
    return log;
}

Member Data Documentation

column

size_t pgrouting::tsp::EuclideanDmatrix::column

private

Definition at line 117 of file euclideanDmatrix.h.

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

coordinates

std::vector< Coordinate_t > pgrouting::tsp::EuclideanDmatrix::coordinates

private

Definition at line 115 of file euclideanDmatrix.h.

Referenced by comparable_distance(), EuclideanDmatrix(), pgrouting::tsp::operator<<(), and set_ids().

ids

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

protected

Definition at line 112 of file euclideanDmatrix.h.

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

row

size_t pgrouting::tsp::EuclideanDmatrix::row

private

Definition at line 116 of file euclideanDmatrix.h.

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

special_distance

double pgrouting::tsp::EuclideanDmatrix::special_distance

private

Definition at line 118 of file euclideanDmatrix.h.

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

---

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

• euclideanDmatrix.h
• euclideanDmatrix.cpp