#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <memory>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <vector>

Include dependency graph for SSSP.h:

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

Go to the source code of this file.

Data Structures
struct	SSSPOutput< GraphType >
	The output of an SSSP run. More...

struct	TwoVariableSSSPNode

Typedefs
template<typename GraphType >
using	SSSPAdjacencyMap = std::unordered_map< typename GraphType::vertex_descriptor, std::vector< typename GraphType::vertex_descriptor > >

template<typename GraphType >
using	SSSPTerminationCriterion = std::function< SSSPTermination(typename GraphType::vertex_iterator &, const SSSPOutput< GraphType > &_sssp)>

template<typename GraphType >
using	SSSPPathWeightFunction = std::function< double(typename GraphType::adj_edge_iterator &, const double, const double)>

template<typename GraphType >
using	SSSPHeuristicFunction = std::function< double(const GraphType *g, typename GraphType::vertex_descriptor source, typename GraphType::vertex_descriptor target)>

template<typename GraphType >
using	SSSPNeighborsFunction = std::function< void(GraphType *g, typename GraphType::vertex_descriptor vd)>

Enumerations
enum class	SSSPTermination { Continue , EndBranch , EndSearch }
	The possible early-termination conditions for an SSSP run. More...

Functions
std::ostream &	operator<< (std::ostream &_os, const SSSPTermination &_t)
	Debug output for termination criteria. More...

template<typename GraphType >
SSSPTerminationCriterion< GraphType >	SSSPDefaultTermination ()

template<typename GraphType >
SSSPPathWeightFunction< GraphType >	SSSPDefaultPathWeight ()

template<typename GraphType >
SSSPHeuristicFunction< GraphType >	SSSPDefaultHeuristic ()

template<typename GraphType >
SSSPNeighborsFunction< GraphType >	SSSPDefaultNeighbors ()

template<typename GraphType >
SSSPOutput< GraphType >	AStarSSSP (GraphType *const _g, const std::vector< typename GraphType::vertex_descriptor > &_starts, std::vector< typename GraphType::vertex_descriptor > &_goals, SSSPPathWeightFunction< GraphType > &_weight, SSSPHeuristicFunction< GraphType > &_heuristic, SSSPNeighborsFunction< GraphType > &_neighbors, SSSPTerminationCriterion< GraphType > &_earlyStop, const double _startDistance=0)

template<typename GraphType >
SSSPOutput< GraphType >	AStarSSSP (GraphType *const _g, const std::vector< typename GraphType::vertex_descriptor > &_starts, std::vector< typename GraphType::vertex_descriptor > &_goals, SSSPPathWeightFunction< GraphType > &_weight, SSSPTerminationCriterion< GraphType > &_earlyStop)

template<typename GraphType >
SSSPOutput< GraphType >	DijkstraSSSP (GraphType *const _g, const std::vector< typename GraphType::vertex_descriptor > &_starts, SSSPPathWeightFunction< GraphType > &_weight, SSSPTerminationCriterion< GraphType > &_earlyStop, const SSSPAdjacencyMap< GraphType > &_adjacencyMap={}, const double _startDistance=0)

template<typename GraphType >
SSSPOutput< GraphType >	DijkstraSSSP (GraphType *const _g, const std::vector< typename GraphType::vertex_descriptor > &_starts, SSSPPathWeightFunction< GraphType > &_weight, const SSSPAdjacencyMap< GraphType > &_adjacencyMap={})

template<typename GraphType >
SSSPOutput< GraphType >	DijkstraSSSP (GraphType *const _g, const std::vector< typename GraphType::vertex_descriptor > &_starts, SSSPTerminationCriterion< GraphType > &_stop, const SSSPAdjacencyMap< GraphType > &_adjacencyMap={})

template<typename GraphType >
SSSPOutput< GraphType >	DijkstraSSSP (GraphType *const _g, const std::vector< typename GraphType::vertex_descriptor > &_starts, const SSSPAdjacencyMap< GraphType > &_adjacencyMap={})

template<typename GraphType >
std::shared_ptr< TwoVariableSSSPNode >	TwoVariableDijkstraSSSP (GraphType *const _g, const std::vector< typename GraphType::vertex_descriptor > &_starts, std::unordered_set< size_t > _goals, const double _startTime, const double _minEndTime, const double _lastConstraint, const double _lastGoalConstraint, SSSPPathWeightFunction< GraphType > &_weight)

Typedef Documentation

◆ SSSPAdjacencyMap

template<typename GraphType >

using SSSPAdjacencyMap = std::unordered_map<typename GraphType::vertex_descriptor, std::vector<typename GraphType::vertex_descriptor> >

A descriptor-based adjacency map. Can model alternative adjacency mappings and successors from an SSSP run.

◆ SSSPHeuristicFunction

template<typename GraphType >

using SSSPHeuristicFunction = std::function<double( const GraphType* g, typename GraphType::vertex_descriptor source, typename GraphType::vertex_descriptor target)>

Define heuristic function for SSSP. This takes the graph, source node and target node. It should return a value representing some estimate of the cost left to finish the search.

◆ SSSPNeighborsFunction

template<typename GraphType >

using SSSPNeighborsFunction = std::function<void( GraphType* g, typename GraphType::vertex_descriptor vd)>

Define neighbors function for SSSP. This takes in the graph and the current node to get the neighbors of. This should return a vertex iterator of the neighbors.

◆ SSSPPathWeightFunction

template<typename GraphType >

using SSSPPathWeightFunction = std::function<double(typename GraphType::adj_edge_iterator&, const double, const double)>

Define a path weight function for SSSP. This takes an edge iterator and the best path distances to the source and target nodes found so far. It should return the new target path distance that would be achieved by using this edge instead of the previous best. Use infinity to represent an untraversable edge or max double to represent a worst-case (but still traversable) edge.

◆ SSSPTerminationCriterion

template<typename GraphType >

using SSSPTerminationCriterion = std::function<SSSPTermination(typename GraphType::vertex_iterator&, const SSSPOutput<GraphType>& _sssp)>

Define an early termination criterion as a function which takes a vertex iterator and the current output object.

Enumeration Type Documentation

◆ SSSPTermination

enum SSSPTermination

strong

The possible early-termination conditions for an SSSP run.

Enumerator
Continue	Proceed as usual.
EndBranch	End the branch at this vertex and do not relax its neighbors.
EndSearch	End the entire search process.

Function Documentation

◆ AStarSSSP() [1/2]

template<typename GraphType >

SSSPOutput<GraphType> AStarSSSP	(	GraphType *const	_g,
		const std::vector< typename GraphType::vertex_descriptor > &	_starts,
		std::vector< typename GraphType::vertex_descriptor > &	_goals,
		SSSPPathWeightFunction< GraphType > &	_weight,
		SSSPHeuristicFunction< GraphType > &	_heuristic,
		SSSPNeighborsFunction< GraphType > &	_neighbors,
		SSSPTerminationCriterion< GraphType > &	_earlyStop,
		const double	_startDistance = `0`
	)

Compute the SSSP through a graph from a start node to a goal node with A* algorithm

Parameters

_g	The graph pointer.
_starts	The vertex descriptors to start from.
_goals	The vertex descriptors to find shortest path to.
_weight	The function for determining total path weight.
_heuristic	The function for determining heuristic cost.
_neighbors	The function for getting neighbors of a given node.

Returns: An output object which contains discovered information.

An element in the priority queue for A*, representing one instance of discovering a cell. Cells may be discovered multiple times from different, parents with different distances.

< The parent cell descriptor.

< This cell descriptor.

< Computed distance to this cell at time of insertion.

< Computed heuristic at time of insertion.

Construct an element for the search queue.

Parameters

_parent	The parent node descriptor.
_target	The target node descriptor.
_g	The distance from starting node to this node.
_h	The heuristic value for this node.

Total ordering by decreasing f = g + h

◆ AStarSSSP() [2/2]

template<typename GraphType >

SSSPOutput<GraphType> AStarSSSP	(	GraphType *const	_g,
		const std::vector< typename GraphType::vertex_descriptor > &	_starts,
		std::vector< typename GraphType::vertex_descriptor > &	_goals,
		SSSPPathWeightFunction< GraphType > &	_weight,
		SSSPTerminationCriterion< GraphType > &	_earlyStop
	)

Compute the SSSP through a graph from a start node to a goal node with A* algorithm

Parameters

_g	The graph pointer.
_starts	The vertex descriptors to start from.
_goals	The vertex descriptors to find shortest path to.
_weight	The function for determining total path weight.
_heuristic	The function for determining heuristic cost.
_neighbors	The function for getting neighbors of a given node.

Returns: An output object which contains discovered information.

◆ DijkstraSSSP() [1/4]

template<typename GraphType >

SSSPOutput<GraphType> DijkstraSSSP	(	GraphType *const	_g,
		const std::vector< typename GraphType::vertex_descriptor > &	_starts,
		const SSSPAdjacencyMap< GraphType > &	_adjacencyMap = `{}`
	)

Compute the SSSP through a graph from a start node with Dijkstra's algorithm. Use the standard path weight and termination criterion.

Parameters

_g	The graph pointer.
_starts	The vertex descriptors to start from.

Returns: An output object which contains the discovered information.

◆ DijkstraSSSP() [2/4]

template<typename GraphType >

SSSPOutput<GraphType> DijkstraSSSP	(	GraphType *const	_g,
		const std::vector< typename GraphType::vertex_descriptor > &	_starts,
		SSSPPathWeightFunction< GraphType > &	_weight,
		const SSSPAdjacencyMap< GraphType > &	_adjacencyMap = `{}`
	)

Compute the SSSP through a graph from a start node with Dijkstra's algorithm. Use the standard termination criterion.

Parameters

_g	The graph pointer.
_starts	The vertex descriptors to start from.
_weight	The function for determining total path weight.

Returns: An output object which contains the discovered information.

◆ DijkstraSSSP() [3/4]

template<typename GraphType >

SSSPOutput<GraphType> DijkstraSSSP	(	GraphType *const	_g,
		const std::vector< typename GraphType::vertex_descriptor > &	_starts,
		SSSPPathWeightFunction< GraphType > &	_weight,
		SSSPTerminationCriterion< GraphType > &	_earlyStop,
		const SSSPAdjacencyMap< GraphType > &	_adjacencyMap = `{}`,
		const double	_startDistance = `0`
	)

Compute the SSSP through a graph from a start node with Dijkstra's algorithm.

Parameters

_g	The graph pointer.
_starts	The vertex descriptors to start from.
_weight	The function for determining total path weight.
_earlyStop	The early termination criterion.

Returns: An output object which contains the discovered information.

An element in the PQ for dijkstra's, representing one instance of discovering a cell. Cells may be discovered multiple times from different parents with different distances.

< The parent cell descriptor.

< This cell descriptor.

< Computed distance at the time of insertion.

Construct an element for the search queue.

Parameters

_parent	The parent node descriptor.
_target	The target node descriptor.
_distance	The distance from parent to target.

Total ordering by decreasing distance.

◆ DijkstraSSSP() [4/4]

template<typename GraphType >

SSSPOutput<GraphType> DijkstraSSSP	(	GraphType *const	_g,
		const std::vector< typename GraphType::vertex_descriptor > &	_starts,
		SSSPTerminationCriterion< GraphType > &	_stop,
		const SSSPAdjacencyMap< GraphType > &	_adjacencyMap = `{}`
	)

Compute the SSSP through a graph from a start node with Dijkstra's algorithm. Use the standard path weight.

Parameters

_g	The graph pointer.
_starts	The vertex descriptors to start from.
_stop	The termination criterion.

Returns: An output object which contains the discovered information.

◆ operator<<()

std::ostream& operator<<	(	std::ostream &	_os,
		const SSSPTermination &	_t
	)

Debug output for termination criteria.

◆ SSSPDefaultHeuristic()

template<typename GraphType >

SSSPHeuristicFunction<GraphType> SSSPDefaultHeuristic ( )

Create a standard SSSP heuristic function.

Returns: A heuristic function of 0 for every node

◆ SSSPDefaultNeighbors()

template<typename GraphType >

SSSPNeighborsFunction<GraphType> SSSPDefaultNeighbors ( )

Create a standard SSSP neighbors function.

Returns

◆ SSSPDefaultPathWeight()

template<typename GraphType >

SSSPPathWeightFunction<GraphType> SSSPDefaultPathWeight ( )

Create a standard SSSP weight function.

Returns: A path weight function which adds the edge property weight to the source distance.

◆ SSSPDefaultTermination()

template<typename GraphType >

SSSPTerminationCriterion<GraphType> SSSPDefaultTermination ( )

Create a standard SSSP stop criterion.

Returns: A termination criterion which never stops early.

◆ TwoVariableDijkstraSSSP()

template<typename GraphType >

std::shared_ptr<TwoVariableSSSPNode> TwoVariableDijkstraSSSP	(	GraphType *const	_g,
		const std::vector< typename GraphType::vertex_descriptor > &	_starts,
		std::unordered_set< size_t >	_goals,
		const double	_startTime,
		const double	_minEndTime,
		const double	_lastConstraint,
		const double	_lastGoalConstraint,
		SSSPPathWeightFunction< GraphType > &	_weight
	)

Todo:: If we want to add waiting, it should be added as a self edge here

Data Structures

Typedefs

Enumerations

Functions

Typedef Documentation

◆ SSSPAdjacencyMap

◆ SSSPHeuristicFunction

◆ SSSPNeighborsFunction

◆ SSSPPathWeightFunction

◆ SSSPTerminationCriterion

Enumeration Type Documentation

◆ SSSPTermination

Function Documentation

◆ AStarSSSP() [1/2]

◆ AStarSSSP() [2/2]

◆ DijkstraSSSP() [1/4]

◆ DijkstraSSSP() [2/4]

◆ DijkstraSSSP() [3/4]

◆ DijkstraSSSP() [4/4]

◆ operator<<()

◆ SSSPDefaultHeuristic()

◆ SSSPDefaultNeighbors()

◆ SSSPDefaultPathWeight()

◆ SSSPDefaultTermination()

◆ TwoVariableDijkstraSSSP()