vrprouting::problem::Matrix Class Reference

#include "matrix.h"

Inheritance diagram for vrprouting::problem::Matrix:

Collaboration diagram for vrprouting::problem::Matrix:

Public Member Functions
	Matrix ()=default
	Matrix (const std::map< std::pair< Coordinate, Coordinate >, Id > &, Multiplier=1.0)
	brief constructor for euclidean version default multipliers More...
	Matrix (const std::map< std::pair< Coordinate, Coordinate >, Id > &, Time_multipliers_t *, size_t, Multiplier=1.0)
	brief constructor for euclidean version with time dependant multipliers More...
	Matrix (Matrix_cell_t *, size_t, const Identifiers< Id > &, Multiplier=1.0)
	brief constructor for matrix version default multipliers More...
	Matrix (Matrix_cell_t *, size_t, Time_multipliers_t *, size_t, const Identifiers< Id > &, Multiplier=1.0)
	brief constructor for matrix version with time dependant multipliers More...
TInterval	at (Idx i, Idx j) const
Idx	get_index (Id) const
	original id -> idx More...
Id	get_original_id (Idx) const
	original id -> idx More...
bool	has_id (Id) const
	has identifier More...
std::string	multipliers_str () const
TInterval	travel_time (Id, Id) const
	retrun the travel time times from the matrix More...
TInterval	travel_time (Id, Id, TTimestamp) const
	retrun the travel time times when using the time dependant multipliers More...
status of the matrix
bool	has_no_infinity () const
	does the matrix values not given by the user? More...
vroom::Matrix< vroom::Duration >	get_vroom_duration_matrix () const
	Get VROOM duration matrix from vrprouting Base Matrix. More...
vroom::Matrix< vroom::Cost >	get_vroom_cost_matrix () const
	Get VROOM cost matrix from vrprouting Base Matrix. More...
bool	obeys_triangle_inequality () const
	does the matrix obeys the triangle inequality? More...
size_t	fix_triangle_inequality (size_t depth=0)
	Fix Triangle Inequality Theorem. More...
bool	empty () const
	is the matrix empty? More...
size_t	size () const
	|idx| More...
bool	is_symmetric () const
	is the matrix symetric? More...
status of the matrix
bool	has_no_infinity () const
	does the matrix values not given by the user? More...
vroom::Matrix< vroom::Duration >	get_vroom_duration_matrix () const
	Get VROOM duration matrix from vrprouting Base Matrix. More...
vroom::Matrix< vroom::Cost >	get_vroom_cost_matrix () const
	Get VROOM cost matrix from vrprouting Base Matrix. More...
bool	obeys_triangle_inequality () const
	does the matrix obeys the triangle inequality? More...
size_t	fix_triangle_inequality (size_t depth=0)
	Fix Triangle Inequality Theorem. More...
bool	empty () const
	is the matrix empty? More...
size_t	size () const
	|idx| More...
bool	is_symmetric () const
	is the matrix symetric? More...

Private Member Functions
void	set_ids (const std::vector< Matrix_cell_t > &)
	Traverses the matrix information to set the ids of the nodes. More...

Private Attributes
std::vector< std::vector< TravelCost > >	m_cost_matrix
	the cost matrix for vroom More...
std::vector< Id >	m_ids
	DATA. More...
std::vector< std::tuple< TTimestamp, Multiplier > >	m_multipliers
	time dependant multiplier More...
std::vector< std::vector< TInterval > >	m_time_matrix
	the actual time matrix More...

Detailed Description

Definition at line 46 of file matrix.h.

Constructor & Destructor Documentation

Matrix() [1/5]

vrprouting::problem::Matrix::Matrix ( )

default

Matrix() [2/5]

vrprouting::problem::Matrix::Matrix	(	Matrix_cell_t *	matrix,
		size_t	size_matrix,
		Time_multipliers_t *	multipliers,
		size_t	size_multipliers,
		const Identifiers< Id > &	node_ids,
		Multiplier	multiplier = 1.0
	)

brief constructor for matrix version with time dependant multipliers

Definition at line 167 of file matrix.cpp.

                               :
    Base_Matrix(matrix, size_matrix, node_ids, multiplier),
    m_multipliers(set_tdm(multipliers, size_multipliers)) { }

Matrix() [3/5]

vrprouting::problem::Matrix::Matrix	(	const std::map< std::pair< Coordinate, Coordinate >, Id > &	euclidean_data,
		Time_multipliers_t *	multipliers,
		size_t	size_multipliers,
		Multiplier	multiplier = 1.0
	)

brief constructor for euclidean version with time dependant multipliers

Definition at line 178 of file matrix.cpp.

                               :
    Base_Matrix(euclidean_data, multiplier),
    m_multipliers(set_tdm(multipliers, size_multipliers)) { }

Matrix() [4/5]

vrprouting::problem::Matrix::Matrix	(	Matrix_cell_t *	matrix,
		size_t	size_matrix,
		const Identifiers< Id > &	node_ids,
		Multiplier	multiplier = 1.0
	)

brief constructor for matrix version default multipliers

Definition at line 188 of file matrix.cpp.

                               :
    Base_Matrix(matrix, size_matrix, node_ids, multiplier),
    m_multipliers{{0, 1}} { }

Matrix() [5/5]

vrprouting::problem::Matrix::Matrix ( const std::map< std::pair< Coordinate, Coordinate >, Id > &  euclidean_data, Multiplier  multiplier = 1.0  )

explicit

brief constructor for euclidean version default multipliers

Definition at line 198 of file matrix.cpp.

                               :
    Base_Matrix(euclidean_data, multiplier),
    m_multipliers{{0, 1}} { }

Member Function Documentation

at()

TInterval vrprouting::base::Base_Matrix::at ( Idx  i, Idx  j  ) const

inlineinherited

Definition at line 97 of file base_matrix.h.

{return m_time_matrix[i][j];}

References vrprouting::base::Base_Matrix::m_time_matrix.

Referenced by travel_time().

empty()

bool vrprouting::base::Base_Matrix::empty ( ) const

inlineinherited

is the matrix empty?

Definition at line 84 of file base_matrix.h.

{return m_ids.empty();}

References vrprouting::base::Base_Matrix::m_ids.

fix_triangle_inequality()

size_t vrprouting::base::Base_Matrix::fix_triangle_inequality ( size_t  depth = 0 )

inherited

Fix 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 508 of file base_matrix.cpp.

                                                 {
  if (depth > m_time_matrix.size()) return depth;
  for (auto & i : m_time_matrix) {
    for (size_t j = 0; j < m_time_matrix.size(); ++j) {
      for (size_t k = 0; k < m_time_matrix.size(); ++k) {
        if (i[k] > (i[j] + m_time_matrix[j][k])) {
          i[k] = i[j] + m_time_matrix[j][k];
          return fix_triangle_inequality(++depth);
        }
      }
    }
  }
  return depth;
}

References vrprouting::base::Base_Matrix::m_time_matrix.

Referenced by do_compatibleVehicles(), do_optimize(), and do_pickDeliver().

get_index()

Idx vrprouting::base::Base_Matrix::get_index ( Id  id ) const

inherited

original id -> idx

Given an original node identifier returns the internal index.

Parameters

[in]

id

Returns

the position of the identifier

Definition at line 161 of file base_matrix.cpp.

                                  {
  /*
   * binary search the stored identifiers
   */
  auto pos = std::lower_bound(m_ids.begin(), m_ids.end(), id);
  if (pos == m_ids.end()) {
    std::ostringstream msg;
    msg << *this << "\nNot found" << id;
    pgassertwm(false, msg.str());
    throw std::make_pair(std::string("(INTERNAL) Base_Matrix: Unable to find node on matrix"), msg.str());
  }
  pgassert(pos != m_ids.end());
 
  /*
   * return the index found
   */
  return static_cast<Idx>(pos - m_ids.begin());
}

References vrprouting::base::Base_Matrix::m_ids, pgassert, and pgassertwm.

Referenced by vrprouting::base::Base_Matrix::Base_Matrix(), vrprouting::Vrp_vroom_problem::get_vroom_job(), vrprouting::Vrp_vroom_problem::get_vroom_shipment(), vrprouting::Vrp_vroom_problem::get_vroom_vehicle(), and travel_time().

get_original_id()

Id vrprouting::base::Base_Matrix::get_original_id ( Idx  index ) const

inherited

original id -> idx

Given the internal index, returns the original node identifier.

Parameters

[in]

id

Returns

the original node identifier

Definition at line 202 of file base_matrix.cpp.

                                            {
  /*
   * Go to the index in the identifiers vector
   */
 
  if (index >= m_ids.size()) {
    std::ostringstream msg;
    msg << *this << "\nOut of range" << index;
    pgassertwm(false, msg.str());
    throw std::make_pair(std::string("(INTERNAL) Base_Matrix: The given index is out of range"), msg.str());
  }
  pgassert(index < m_ids.size());
 
  /*
   * return the original id found
   */
  return static_cast<Id>(m_ids[index]);
}

References vrprouting::base::Base_Matrix::m_ids, pgassert, and pgassertwm.

Referenced by vrprouting::Vrp_vroom_problem::get_results().

get_vroom_cost_matrix()

vroom::Matrix< vroom::Cost > vrprouting::base::Base_Matrix::get_vroom_cost_matrix ( ) const

inherited

Get VROOM cost matrix from vrprouting Base Matrix.

Returns

vroom::Matrix<vroom::Cost> The vroom cost matrix

Definition at line 421 of file base_matrix.cpp.

                                         {
  size_t matrix_size = m_ids.size();
  vroom::Matrix<vroom::Cost> vroom_matrix(matrix_size);
  for (size_t i = 0; i < matrix_size; i++) {
    for (size_t j = 0; j < matrix_size; j++) {
      vroom_matrix[i][j] = static_cast<vroom::Cost>(m_cost_matrix[i][j]);
    }
  }
  return vroom_matrix;
}

References vrprouting::base::Base_Matrix::m_cost_matrix, and vrprouting::base::Base_Matrix::m_ids.

Referenced by vrprouting::Vrp_vroom_problem::solve().

get_vroom_duration_matrix()

vroom::Matrix< vroom::Duration > vrprouting::base::Base_Matrix::get_vroom_duration_matrix ( ) const

inherited

Get VROOM duration matrix from vrprouting Base Matrix.

Returns

vroom::Matrix<vroom::Duration> The vroom cost matrix

Definition at line 404 of file base_matrix.cpp.

                                             {
  size_t matrix_size = m_ids.size();
  vroom::Matrix<vroom::Cost> vroom_matrix(matrix_size);
  for (size_t i = 0; i < matrix_size; i++) {
    for (size_t j = 0; j < matrix_size; j++) {
      vroom_matrix[i][j] = static_cast<vroom::Duration>(m_time_matrix[i][j]);
    }
  }
  return vroom_matrix;
}

References vrprouting::base::Base_Matrix::m_ids, and vrprouting::base::Base_Matrix::m_time_matrix.

Referenced by vrprouting::Vrp_vroom_problem::solve().

has_id()

bool vrprouting::base::Base_Matrix::has_id ( Id  id ) const

inherited

has identifier

Parameters

[in]

id

original identifier

Returns

true when it exists on the saved ids

Definition at line 126 of file base_matrix.cpp.

                               {
  /*
   * binary search the stored identifiers
   */
  auto pos = std::lower_bound(m_ids.cbegin(), m_ids.cend(), id);
 
  /*
   * Return search results
   */
  return pos != m_ids.end() && *pos == id;
}

References vrprouting::base::Base_Matrix::m_ids.

Referenced by vrprouting::base::Base_Matrix::Base_Matrix(), and travel_time().

has_no_infinity()

bool vrprouting::base::Base_Matrix::has_no_infinity ( ) const

inherited

does the matrix values not given by the user?

Returns

false at the moment it finds an infinity value

true otherwise

Definition at line 459 of file base_matrix.cpp.

                                   {
  /*
   * Cycle the matrix
   */
  for (const auto &row : m_time_matrix) {
    for (const auto &val : row) {
      /*
       * found infinity?
       *
       * yes -> return false
       */
      if (val == (std::numeric_limits<TInterval>::max)()) return false;
    }
  }
  /*
   * return true
   */
  return true;
}

References vrprouting::base::Base_Matrix::m_time_matrix.

Referenced by do_compatibleVehicles(), do_optimize(), do_pgr_pickDeliver(), do_pickDeliver(), and do_vrp_vroom().

is_symmetric()

bool vrprouting::base::Base_Matrix::is_symmetric ( ) const

inherited

is the matrix symetric?

Definition at line 524 of file base_matrix.cpp.

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

References vrprouting::base::Base_Matrix::m_time_matrix, and pgassertwm.

multipliers_str()

std::string vrprouting::problem::Matrix::multipliers_str

(

)

const

Definition at line 256 of file matrix.cpp.

                              {
    std::ostringstream log;
    log << std::fixed << std::setprecision(2);
    for (const auto &e : m_multipliers) {
        log << "\n" << std::get<0>(e) << "\t" << std::get<1>(e);
    }
    return log.str();
}

References m_multipliers.

obeys_triangle_inequality()

bool vrprouting::base::Base_Matrix::obeys_triangle_inequality ( ) const

inherited

does the matrix obeys the triangle inequality?

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 m_time_matrix[i][k] != inf m_time_matrix[i][k] <= m_time_matrix[i][j] + m_time_matrix[j][k]

Definition at line 487 of file base_matrix.cpp.

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

References vrprouting::base::Base_Matrix::m_time_matrix.

Referenced by do_compatibleVehicles(), do_optimize(), and do_pickDeliver().

set_ids()

void vrprouting::base::Base_Matrix::set_ids ( const std::vector< Matrix_cell_t > &  data )

privateinherited

Traverses the matrix information to set the ids of the nodes.

Traverses the matrix information to get the ids of the nodes.

Parameters

[in]

data

Base_Matrix information

Postcondition

m_ids contains all the nodes original ids

Definition at line 85 of file base_matrix.cpp.

                                                         {
  pgassert(m_ids.empty());
  Identifiers<Id> node_ids;
  /*
   * Cycle the information
   */
  for (const auto &cost : data) {
    /*
     * extract the original identifiers
     */
    node_ids += cost.from_vid;
    node_ids += cost.to_vid;
  }
  /*
   * Save the extracted information
   */
  m_ids.insert(m_ids.begin(), node_ids.begin(), node_ids.end());
}

References Identifiers< T >::begin(), Identifiers< T >::end(), vrprouting::base::Base_Matrix::m_ids, and pgassert.

size()

size_t vrprouting::base::Base_Matrix::size ( ) const

inlineinherited

|idx|

Returns

the size of the matrix

Definition at line 90 of file base_matrix.h.

{return m_ids.size();}

References vrprouting::base::Base_Matrix::m_ids.

Referenced by do_vrp_vroom().

travel_time() [1/2]

TInterval vrprouting::problem::Matrix::travel_time	(	Id	,
		Id
	)		const

retrun the travel time times from the matrix

travel_time() [2/2]

TInterval vrprouting::problem::Matrix::travel_time	(	Id	i,
		Id	j,
		TTimestamp	date_time_of_departure_from_i
	)		const

retrun the travel time times when using the time dependant multipliers

Parameters

[in]	i,j	original identifiers
[in]	date_time_of_departure_from_i	time of departure from i

Returns

infinity When the original identifiers do not exist on the matrix

the cell content

Definition at line 233 of file matrix.cpp.

                                                                              {
    if (m_multipliers.size() == 1) return at(get_index(i), get_index(j));
 
    /*
     * are ids valid?
     *
     * no -> return infinity
     */
    if (!has_id(i) || !has_id(j)) return (std::numeric_limits<TInterval>::max)();
 
    /* data */
    double tt_i_j {static_cast<double>(at(get_index(i), get_index(j)))};
    double c1(get_tdm(m_multipliers, date_time_of_departure_from_i));
    double c2(next_tdm(m_multipliers, date_time_of_departure_from_i));
    auto t_change(time_change(m_multipliers, date_time_of_departure_from_i));
    auto adjusted_value = static_cast<TInterval>(tt_i_j * c1);
 
    if (t_change >= (date_time_of_departure_from_i + adjusted_value) || c1 == c2) return adjusted_value;
 
    return static_cast<TInterval>(tt_i_j * std::min(c1, c2));
}

References vrprouting::base::Base_Matrix::at(), vrprouting::base::Base_Matrix::get_index(), vrprouting::problem::anonymous_namespace{matrix.cpp}::get_tdm(), vrprouting::base::Base_Matrix::has_id(), m_multipliers, vrprouting::problem::anonymous_namespace{matrix.cpp}::next_tdm(), and vrprouting::problem::anonymous_namespace{matrix.cpp}::time_change().

Referenced by vrprouting::problem::Tw_node::travel_time_to().

Member Data Documentation

m_cost_matrix

std::vector<std::vector<TravelCost> > vrprouting::base::Base_Matrix::m_cost_matrix

privateinherited

the cost matrix for vroom

m_cost_matrix[i][j] i and j are index from the ids

Definition at line 132 of file base_matrix.h.

Referenced by vrprouting::base::Base_Matrix::Base_Matrix(), and vrprouting::base::Base_Matrix::get_vroom_cost_matrix().

m_ids

std::vector<Id> vrprouting::base::Base_Matrix::m_ids

privateinherited

DATA.

ordered list of user identifiers

Definition at line 120 of file base_matrix.h.

Referenced by vrprouting::base::Base_Matrix::Base_Matrix(), vrprouting::base::Base_Matrix::empty(), vrprouting::base::Base_Matrix::get_index(), vrprouting::base::Base_Matrix::get_original_id(), vrprouting::base::Base_Matrix::get_vroom_cost_matrix(), vrprouting::base::Base_Matrix::get_vroom_duration_matrix(), vrprouting::base::Base_Matrix::has_id(), vrprouting::base::operator<<(), vrprouting::base::Base_Matrix::set_ids(), and vrprouting::base::Base_Matrix::size().

m_multipliers

std::vector<std::tuple<TTimestamp, Multiplier> > vrprouting::problem::Matrix::m_multipliers

private

time dependant multiplier

m_multipliers[i] ith time dependant multiplier double = time when the multipliers starts to be valid double = multiplier The multiplier ends its validity at the time of the (i+1)th value

Definition at line 78 of file matrix.h.

Referenced by multipliers_str(), and travel_time().

m_time_matrix

std::vector<std::vector<TInterval> > vrprouting::base::Base_Matrix::m_time_matrix

privateinherited

the actual time matrix

m_time_matrix[i][j] i and j are index from the ids

Definition at line 126 of file base_matrix.h.

Referenced by vrprouting::base::Base_Matrix::at(), vrprouting::base::Base_Matrix::Base_Matrix(), vrprouting::base::Base_Matrix::fix_triangle_inequality(), vrprouting::base::Base_Matrix::get_vroom_duration_matrix(), vrprouting::base::Base_Matrix::has_no_infinity(), vrprouting::base::Base_Matrix::is_symmetric(), vrprouting::base::Base_Matrix::obeys_triangle_inequality(), and vrprouting::base::operator<<().

---

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

• matrix.h
• matrix.cpp