Algorithms.h

Go to the documentation of this file.

/*
        This file is part of the EnergyOptimizatorOfRoboticCells program.

        EnergyOptimizatorOfRoboticCells 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 3 of the License, or
        (at your option) any later version.

        EnergyOptimizatorOfRoboticCells 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 EnergyOptimizatorOfRoboticCells. If not, see <http://www.gnu.org/licenses/>.
*/

#ifndef HLIDAC_PES_ALGORITHMS_H
#define HLIDAC_PES_ALGORITHMS_H

#include <algorithm>
#include <cmath>
#include <cassert>
#include <functional>
#include <vector>
#include <utility>

template <class T>
using DistanceMatrix = std::vector<std::vector<T>>;

template <class T, class C = std::greater<T>>
DistanceMatrix<T> floyd(DistanceMatrix<T> m, const C& cmp = std::greater<T>())  {
        size_t matrixSize = m.size();
        for (size_t k = 0; k < matrixSize; ++k) {
                for (size_t i = 0; i < matrixSize; ++i) {
                        for (size_t j = 0; j < matrixSize; ++j) {
                                assert(i < m.size() && j < m[i].size() && k < m[i].size() && k < m.size() && j < m[k].size() && "Floyd needs square matrix!");
                                if (cmp(m[i][j], m[i][k]+m[k][j]))
                                        m[i][j] = m[i][k]+m[k][j];
                        }
                }
        }

        return m;
}

template <class T>
std::pair<double, double> goldenSearch(const T& unimodalFce)    {
        const double tol = unimodalFce.tolerance();
        const static double phi = (std::sqrt(5.0)-1.0)/2.0;

        double a = 0.0, b = 1.0, c = 1.0-phi, d;
        double fxC = unimodalFce.functionValue(c), fxD;
        while (b-a > tol)       {
                if (c-a < b-c)  {
                        d = phi*(b-a)+a;
                        fxD = unimodalFce.functionValue(d);
                        if (fxC <= fxD) {
                                b = d;
                        } else {
                                a = c; c = d;
                                fxC = fxD;
                        }
                } else {
                        d = (1-phi)*(b-a)+a;
                        fxD = unimodalFce.functionValue(d);
                        if (fxD <= fxC) {
                                b = c; c = d;
                                fxC = fxD;
                        } else {
                                a = d;
                        }
                }
        }

        return { c, fxC };
}

#endif