Algorithms.h File Reference

Universal algorithms like Floyd-Warshall, Golden Search, etc. More...

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

Include dependency graph for Algorithms.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Typedefs
template<class T >
using	DistanceMatrix = std::vector< std::vector< T >>
	Definition of the matrix data type. More...

Functions
template<class T , class C = std::greater<T>>
DistanceMatrix< T >	floyd (DistanceMatrix< T > m, const C &cmp=std::greater< T >())
	It calculates all-to-all shortest paths and returns the matrix with their lengths. More...
template<class T >
std::pair< double, double >	goldenSearch (const T &unimodalFce)
	It finds the minimal function value of a unimodal convex function. More...

Detailed Description

Universal algorithms like Floyd-Warshall, Golden Search, etc.

Author

Libor Bukata

Definition in file Algorithms.h.

Typedef Documentation

template<class T >

using DistanceMatrix = std::vector<std::vector<T>>

Definition of the matrix data type.

Template Parameters

T	A numerical type.

Definition at line 39 of file Algorithms.h.

Function Documentation

template<class T , class C = std::greater<T>>

DistanceMatrix<T> floyd	(	DistanceMatrix< T >	m,
		const C &	cmp = std::greater<T>()
	)

It calculates all-to-all shortest paths and returns the matrix with their lengths.

Parameters

m	Distance matrix of the graph without negative cycles.
cmp	Operator of the comparison, typically '>'.

Template Parameters

T	A numerical type.
C	A comparison function of distances.

Returns

Updated distance matrix containing the lengths of all-to-all shortest paths.

Definition at line 50 of file Algorithms.h.

template<class T >

std::pair<double, double> goldenSearch

(

const T &

unimodalFce

)

It finds the minimal function value of a unimodal convex function.

Parameters

unimodalFce

A convex unimodal function depending on one variable.

Template Parameters

T	A class encapsulating the convex function, T::tolerance(), T::functionValue() methods have to be defined.

Returns

The optimal value of the variable and the related minimal function value.

Definition at line 72 of file Algorithms.h.