vrprouting::base::Base_Matrix Class Reference

N x N matrix. More...

#include "base_matrix.h"

Inheritance diagram for vrprouting::base::Base_Matrix:

Collaboration diagram for vrprouting::base::Base_Matrix:

Public Member Functions
	Base_Matrix ()=default
	Constructs an emtpy matrix. More...
	Base_Matrix (const std::map< std::pair< Coordinate, Coordinate >, Id > &, Multiplier)
	Base_Matrix (Matrix_cell_t *, size_t, const Identifiers< Id > &, Multiplier)
	Constructs a matrix for only specific identifiers. More...
	Base_Matrix (Vroom_matrix_t *, size_t, const Identifiers< Id > &, double)
	Constructor for VROOM matrix input. 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...

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::vector< TInterval > >	m_time_matrix
	the actual time matrix More...

Friends
std::ostream &	operator<< (std::ostream &log, const Base_Matrix &matrix)
	print matrix (row per cell) More...

Detailed Description

N x N matrix.

• The internal data interpretation is done by the user of this class
• Once created can not be modified

Definition at line 61 of file base_matrix.h.

Constructor & Destructor Documentation

Base_Matrix() [1/4]

vrprouting::base::Base_Matrix::Base_Matrix ( )

default

Constructs an emtpy matrix.

Base_Matrix() [2/4]

vrprouting::base::Base_Matrix::Base_Matrix	(	Matrix_cell_t *	data_costs,
		size_t	size_matrix,
		const Identifiers< Id > &	node_ids,
		Multiplier	multiplier
	)

Constructs a matrix for only specific identifiers.

Parameters

[in]	data_costs	The set of costs
[in]	size_matrix	The size of the set of costs
[in]	node_ids	The selected node identifiers to be added
[in]	multiplier	All times are multiplied by this value

Precondition

data_costs is not empty

Postcondition

ids has all the ids of node_ids

data_costs[from_vid, to_vid] is ignored when from_vid is not in node_ids or to_vid is not in node_ids

costs[from_vid, to_vid] is not has the cell cost when from_vid, to_vid are in node_ids

costs[from_vid, to_vid] = inf when cell from_vid, to_vid does not exist

costs[from_vid, to_vid] = 0 when from_vid = to_vid

Definition at line 235 of file base_matrix.cpp.

                           {
  /*
   * Sets the selected nodes identifiers
   */
  m_ids.insert(m_ids.begin(), node_ids.begin(), node_ids.end());
 
  /*
   * Create matrix
   */
  m_time_matrix.resize(
      m_ids.size(),
      std::vector<TInterval>(
        m_ids.size(),
        /*
         * Set initial values to infinity
         */
        (std::numeric_limits<TInterval>::max)()));
 
  Identifiers<Idx> inserted;
  /*
   * Cycle the matrix data
   */
  for (size_t i = 0; i < size_matrix; ++i) {
    auto data = data_costs[i];
    /*
     * skip if row is not from selected nodes
     */
    if (!(has_id(data.from_vid) && has_id(data.to_vid))) continue;
 
    /*
     * Save the information
     */
    m_time_matrix[get_index(data.from_vid)][get_index(data.to_vid)] =
      static_cast<TInterval>(static_cast<Multiplier>(data.cost) * multiplier);
 
    /*
     * If the opposite direction is infinity insert the same cost
     */
    if (m_time_matrix[get_index(data.to_vid)][get_index(data.from_vid)] == (std::numeric_limits<TInterval>::max)()) {
      m_time_matrix[get_index(data.to_vid)][get_index(data.from_vid)] =
        m_time_matrix[get_index(data.from_vid)][get_index(data.to_vid)];
    }
  }
 
  /*
   * Set the diagonal values to 0
   */
  for (size_t i = 0; i < m_time_matrix.size(); ++i) {
    m_time_matrix[i][i] = 0;
  }
}

References Identifiers< T >::begin(), Identifiers< T >::end(), get_index(), has_id(), m_ids, and m_time_matrix.

Base_Matrix() [3/4]

vrprouting::base::Base_Matrix::Base_Matrix	(	Vroom_matrix_t *	matrix_rows,
		size_t	total_matrix_rows,
		const Identifiers< Id > &	location_ids,
		double	scaling_factor
	)

Constructor for VROOM matrix input.

Parameters

[in]	data_costs	The set of costs
[in]	size_matrix	The size of the set of costs
[in]	location_ids	The location identifiers

Precondition

data_costs is not empty

Postcondition

ids has all the ids of node_ids

data_costs[from_vid, to_vid] is ignored when from_vid is not in node_ids or to_vid is not in node_ids

costs[from_vid, to_vid] is not has the cell cost when from_vid, to_vid are in node_ids

costs[from_vid, to_vid] = inf when cell from_vid, to_vid does not exist

costs[from_vid, to_vid] = 0 when from_vid = to_vid

Definition at line 305 of file base_matrix.cpp.

                                                                                     {
  /*
   * Sets the selected nodes identifiers
   */
  m_ids.insert(m_ids.begin(), location_ids.begin(), location_ids.end());
 
  /*
   * Create matrix
   */
  m_time_matrix.resize(
      m_ids.size(),
      std::vector<TInterval>(m_ids.size(),
                             /*
                              * Set initial values to infinity
                              */
                             (std::numeric_limits<TInterval>::max)()));
  m_cost_matrix.resize(
      m_ids.size(),
      std::vector<TravelCost>(m_ids.size(), (std::numeric_limits<TravelCost>::max)()));
 
  Identifiers<Idx> inserted;
  /*
   * Cycle the matrix data
   */
  for (size_t i = 0; i < total_matrix_rows; ++i) {
    auto cell = matrix_rows[i];
    /*
     * skip if row is not from selected nodes
     */
    if (!(has_id(cell.start_id) && has_id(cell.end_id))) continue;
 
    /*
     * Save the information. Scale the time matrix according to scaling_factor
     */
    m_time_matrix[get_index(cell.start_id)][get_index(cell.end_id)] =
      static_cast<Duration>(std::round(cell.duration / scaling_factor));
    m_cost_matrix[get_index(cell.start_id)][get_index(cell.end_id)] =
      static_cast<Duration>(cell.cost);
 
    /*
     * If the opposite direction is infinity insert the same cost
     */
    if (m_time_matrix[get_index(cell.end_id)][get_index(cell.start_id)] ==
        (std::numeric_limits<TInterval>::max)()) {
      m_time_matrix[get_index(cell.end_id)][get_index(cell.start_id)] =
        m_time_matrix[get_index(cell.start_id)][get_index(cell.end_id)];
    }
    if (m_cost_matrix[get_index(cell.end_id)][get_index(cell.start_id)] ==
        (std::numeric_limits<TravelCost>::max)()) {
      m_cost_matrix[get_index(cell.end_id)][get_index(cell.start_id)] =
          m_cost_matrix[get_index(cell.start_id)][get_index(cell.end_id)];
    }
  }
 
  /*
   * Set the diagonal values to 0
   */
  for (size_t i = 0; i < m_time_matrix.size(); ++i) {
    m_time_matrix[i][i] = 0;
    m_cost_matrix[i][i] = 0;
  }
}

References Identifiers< T >::begin(), Identifiers< T >::end(), get_index(), has_id(), m_cost_matrix, m_ids, and m_time_matrix.

Base_Matrix() [4/4]

vrprouting::base::Base_Matrix::Base_Matrix ( const std::map< std::pair< Coordinate, Coordinate >, Id > &  euclidean_data, Multiplier  multiplier  )

explicit

Definition at line 372 of file base_matrix.cpp.

                                                                                                                 {
  m_ids.reserve(euclidean_data.size());
  for (const auto &e : euclidean_data) {
    m_ids.push_back(e.second);
  }
  m_time_matrix.resize(
      m_ids.size(),
      std::vector<TInterval>(
        m_ids.size(),
        (std::numeric_limits<TInterval>::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);
      m_time_matrix[from_id][to_id] =
        static_cast<TInterval>(static_cast<Multiplier>(detail::get_distance(from.first, to.first)) * multiplier);
      m_time_matrix[to_id][from_id] = m_time_matrix[from_id][to_id];
    }
  }
 
  for (size_t i = 0; i < m_time_matrix.size(); ++i) {
    m_time_matrix[i][i] = 0;
  }
}

References vrprouting::base::detail::get_distance(), get_index(), m_ids, and m_time_matrix.

Member Function Documentation

at()

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

inline

Definition at line 97 of file base_matrix.h.

{return m_time_matrix[i][j];}

References m_time_matrix.

Referenced by vrprouting::problem::Matrix::travel_time().

empty()

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

inline

is the matrix empty?

Definition at line 84 of file base_matrix.h.

{return m_ids.empty();}

References m_ids.

fix_triangle_inequality()

size_t vrprouting::base::Base_Matrix::fix_triangle_inequality

(

size_t

depth = 0

)

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 m_time_matrix.

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

get_index()

Idx vrprouting::base::Base_Matrix::get_index

(

Id

id

)

const

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 m_ids, pgassert, and pgassertwm.

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

get_original_id()

Id vrprouting::base::Base_Matrix::get_original_id

(

Idx

index

)

const

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 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

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 m_cost_matrix, and 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

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 m_ids, and m_time_matrix.

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

has_id()

bool vrprouting::base::Base_Matrix::has_id

(

Id

id

)

const

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 m_ids.

Referenced by Base_Matrix(), and vrprouting::problem::Matrix::travel_time().

has_no_infinity()

bool vrprouting::base::Base_Matrix::has_no_infinity

(

)

const

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 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

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 m_time_matrix, and pgassertwm.

obeys_triangle_inequality()

bool vrprouting::base::Base_Matrix::obeys_triangle_inequality

(

)

const

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 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 )

private

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(), m_ids, and pgassert.

size()

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

inline

|idx|

Returns

the size of the matrix

Definition at line 90 of file base_matrix.h.

{return m_ids.size();}

References m_ids.

Referenced by do_vrp_vroom().

Friends And Related Function Documentation

operator<<

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

friend

print matrix (row per cell)

Parameters

[in,out]	log	stream variable where to print
[in]	matrix	The matrix

Definition at line 567 of file base_matrix.cpp.

                                                                   {
  /*
   * print the identifiers
   */
  for (const auto id : matrix.m_ids) {
    log << "\t" << id;
  }
  log << "\n";
  size_t i = 0;
 
  /*
   * Cycle the cells
   */
  for (const auto &row : matrix.m_time_matrix) {
    size_t j = 0;
    for (const auto cost : row) {
      /*
       * print the information
       */
      log << "Internal(" << i << "," << j << ")"
        << "\tOriginal(" << matrix.m_ids[i] << "," << matrix.m_ids[j] << ")"
        << "\t = " << cost
        << "\n";
      ++j;
    }
    ++i;
  }
  return log;
}

Member Data Documentation

m_cost_matrix

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

private

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 Base_Matrix(), and get_vroom_cost_matrix().

m_ids

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

private

DATA.

ordered list of user identifiers

Definition at line 120 of file base_matrix.h.

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

m_time_matrix

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

private

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 at(), Base_Matrix(), fix_triangle_inequality(), get_vroom_duration_matrix(), has_no_infinity(), is_symmetric(), obeys_triangle_inequality(), and vrprouting::base::operator<<().

---

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

• base_matrix.h
• base_matrix.cpp