matrix.cpp

Go to the documentation of this file.

/*PGR-GNU*****************************************************************
 
FILE: Matrix.cpp
 
Copyright (c) 2015 pgRouting developers
Mail: [email protected]
 
------
 
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
 
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
 
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 
 ********************************************************************PGR-GNU*/
 
#include "problem/matrix.h"
 
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <vector>
#include <map>
#include <cmath>
#include <utility>
#include <iomanip>
#include <tuple>
 
 
#include "cpp_common/pgr_assert.h"
#include "c_types/matrix_cell_t.h"
#include "c_types/time_multipliers_t.h"
 
 
namespace vrprouting {
namespace problem {
 
namespace {
 
std::vector<std::tuple<TTimestamp, Multiplier>>
set_tdm(Time_multipliers_t *p_multipliers, size_t size_multipliers) {
    pgassert(size_multipliers > 1);
    std::vector<std::tuple<TTimestamp, Multiplier>> tdm;
    /*
     * Sort the multipliers info
     */
    std::sort(p_multipliers, p_multipliers + size_multipliers,
            [] (const Time_multipliers_t &lhs, const Time_multipliers_t &rhs) {
                return lhs.start_time < rhs.start_time;
            });
    for (size_t i = 0; i < size_multipliers; ++i) {
        tdm.emplace_back(p_multipliers[i].start_time, p_multipliers[i].multiplier);
    }
    return tdm;
}
 
Multiplier
get_tdm(const std::vector<std::tuple<TTimestamp, Multiplier>> &tdm, TTimestamp time) {
    pgassert(time >= 0);
    Multiplier coeff(1);
    for (const auto &e : tdm) {
        if (time < std::get<0>(e)) break;
        coeff = std::get<1>(e);
    }
    return coeff;
}
 
Multiplier
next_tdm(const std::vector<std::tuple<TTimestamp, Multiplier>> &tdm, TTimestamp time) {
    Multiplier coeff(1);
    for (const auto &e : tdm) {
        coeff = std::get<1>(e);
        if (std::get<0>(e) >= time) break;
    }
    return coeff;
}
 
TTimestamp
time_change(const std::vector<std::tuple<TTimestamp, Multiplier>> &tdm, TTimestamp time) {
    TTimestamp t_change(0);
    for (const auto &e : tdm) {
        t_change = std::get<0>(e);
        if (time <= t_change) break;
    }
    pgassert((time <= t_change)
             || (t_change == std::get<0>(tdm[tdm.size() - 1 ])));
    return t_change;
}
 
}  // namespace
 
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) :
    Base_Matrix(matrix, size_matrix, node_ids, multiplier),
    m_multipliers(set_tdm(multipliers, size_multipliers)) { }
 
/*
 * constructor for euclidean with time dependant multipliers
 */
Matrix::Matrix(
        const std::map<std::pair<Coordinate, Coordinate>, Id> &euclidean_data,
        Time_multipliers_t *multipliers, size_t size_multipliers,
        Multiplier multiplier) :
    Base_Matrix(euclidean_data, multiplier),
    m_multipliers(set_tdm(multipliers, size_multipliers)) { }
 
/*
 * constructor for euclidean default multipliers
 */
Matrix::Matrix(
        Matrix_cell_t *matrix, size_t size_matrix,
        const Identifiers<Id>& node_ids,
        Multiplier multiplier) :
    Base_Matrix(matrix, size_matrix, node_ids, multiplier),
    m_multipliers{{0, 1}} { }
 
/*
 * constructor for euclidean default multipliers
 */
Matrix::Matrix(
        const std::map<std::pair<Coordinate, Coordinate>, Id> &euclidean_data,
        Multiplier multiplier) :
    Base_Matrix(euclidean_data, multiplier),
    m_multipliers{{0, 1}} { }
 
 
TInterval
Matrix::travel_time(Id i, Id j, TTimestamp date_time_of_departure_from_i) const {
    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));
}
 
std::string
Matrix::multipliers_str() const {
    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();
}
 
}  // namespace problem
}  // namespace vrprouting