Dijkstra's Algorithm for computing single source shortest path. More...

#include <JETSCAPE/blob/main/external_packages/gtl/include/GTL/dijkstra.h>

Inheritance diagram for dijkstra:

Collaboration diagram for dijkstra:

Public Types
enum	node_color { white, grey, black }

typedef list< node > ::const_iterator	shortest_path_node_iterator
	Iterator type for traversing nodes on one shortest path.

typedef list< edge > ::const_iterator	shortest_path_edge_iterator
	Iterator type for traversing edges on one shortest path.

Public Types inherited from algorithm
enum	{ GTL_OK = 1, GTL_ERROR = 0 }
	Return values for algorithm::check and algorithm::run. More...

Public Member Functions
	dijkstra ()
	Default constructor.

virtual	~dijkstra ()
	Destructor.

void	source (const node &n)
	Sets source node.

void	target (const node &n)
	Sets target node.

void	weights (const edge_map< double > &weight)
	Sets weights of the edges.

void	store_preds (bool set)
	Enables or disables the storing of predecessors.

virtual int	check (graph &G)
	Checks whether the preconditions for Dijkstra are satisfied.

int	run (graph &G)
	Runs shortest path algorithm on `G`.

node	source () const
	Returns source node.

node	target () const
	Returns target node if set, `node::node()` else.

bool	store_preds () const
	Returns whether the storing of predecessors is enabled.

bool	reached (const node &n) const
	Returns whether `n` is reachable from source node.

double	distance (const node &n) const
	Returns the distance from source node to node `n`.

node	predecessor_node (const node &n) const
	Predecessor node of node `n` on the shortest path from the source node.

edge	predecessor_edge (const node &n) const
	Predecessor edge of node `n` on the shortest path from the source node.

shortest_path_node_iterator	shortest_path_nodes_begin (const node &dest)
	Returns an iterator to the beginning (to the source node) of a shortest node path to node `dest`.

shortest_path_node_iterator	shortest_path_nodes_end (const node &dest)
	Returns an iterator one after the end (one after node `dest`) of a shortest node path to node `dest`.

shortest_path_edge_iterator	shortest_path_edges_begin (const node &dest)
	Returns an iterator to the beginning edge of a shortest edge path to node `dest`.

shortest_path_edge_iterator	shortest_path_edges_end (const node &dest)
	Returns an iterator one after the end of a shortest edge path to node `dest`.

virtual void	reset ()
	Resets Dijkstra's algorithm.

Public Member Functions inherited from algorithm
	algorithm ()
	Creates an algorithm object.

virtual	~algorithm ()
	Destroys the algorithm object.

Private Member Functions
void	reset_algorithm ()

void	init (graph &G)

void	fill_node_list (const node &t)

void	fill_edge_list (const node &t)

Private Attributes
node	s

node	t

bool	weights_set

bool	preds_set

edge_map< double >	weight

node_map< edge >	pred

node_map< int >	mark

node_map< double >	dist

node_map< list< node > >	shortest_path_node_list

node_map< list< edge > >	shortest_path_edge_list

Detailed Description

Dijkstra's Algorithm for computing single source shortest path.

This class implements Dijkstra's algorithm for computing single source shortest path in $\mathcal{O}((|V| + |E|) log |V|)$ worst case.

See Also: bellman_ford

Author: Christian Bachmaier chris.nosp@m.@inf.nosp@m.osun..nosp@m.fmi..nosp@m.uni-p.nosp@m.assa.nosp@m.u.de

Definition at line 30 of file dijkstra.h.

View newest version in sPHENIX GitHub at line 30 of file dijkstra.h

Member Typedef Documentation

typedef list<edge>::const_iterator dijkstra::shortest_path_edge_iterator

Iterator type for traversing edges on one shortest path.

Definition at line 41 of file dijkstra.h.

View newest version in sPHENIX GitHub at line 41 of file dijkstra.h

typedef list<node>::const_iterator dijkstra::shortest_path_node_iterator

Iterator type for traversing nodes on one shortest path.

Definition at line 36 of file dijkstra.h.

View newest version in sPHENIX GitHub at line 36 of file dijkstra.h

Member Enumeration Documentation

enum dijkstra::node_color

Enumerator:

white
grey
black

Definition at line 46 of file dijkstra.h.

View newest version in sPHENIX GitHub at line 46 of file dijkstra.h

Constructor & Destructor Documentation

dijkstra::dijkstra ( )

Default constructor.

Enables only the calculation of shortest paths.

See Also: algorithm::algorithm

Definition at line 82 of file dijkstra.cpp.

View newest version in sPHENIX GitHub at line 82 of file dijkstra.cpp

References reset_algorithm().

Here is the call graph for this function:

dijkstra::~dijkstra ( )

virtual

Destructor.

See Also: algorithm::~algorithm

Definition at line 88 of file dijkstra.cpp.

View newest version in sPHENIX GitHub at line 88 of file dijkstra.cpp

Member Function Documentation

int dijkstra::check ( graph & G )

virtual

Checks whether the preconditions for Dijkstra are satisfied.

Necessary preconditions are:

the weights of the edges are set
the graph G has at least one node
all edge weights must be $\ge 0$
the source node and (if set) target node must be found in G

Parameters

G graph

Return values

algorithm::GTL_OK	if algorithm can be applied
algorithm::GTL_ERROR	otherwise

See Also: dijkstra::source; dijkstra::weights; algorithm::check

Implements algorithm.

Definition at line 118 of file dijkstra.cpp.

View newest version in sPHENIX GitHub at line 118 of file dijkstra.cpp

References graph::edges_begin(), graph::edges_end(), algorithm::GTL_ERROR, algorithm::GTL_OK, graph::nodes_begin(), graph::nodes_end(), s, weight, and weights_set.

Here is the call graph for this function:

double dijkstra::distance ( const node & n ) const

Returns the distance from source node to node n.

Parameters

n node

Returns: distance if n is dijkstra::reached, -1.0 else

Definition at line 256 of file dijkstra.cpp.

View newest version in sPHENIX GitHub at line 256 of file dijkstra.cpp

References dist, and n.

void dijkstra::fill_edge_list ( const node & t )

private

Definition at line 386 of file dijkstra.cpp.

View newest version in sPHENIX GitHub at line 386 of file dijkstra.cpp

References upload::dest, predecessor_edge(), predecessor_node(), reached(), s, and shortest_path_edge_list.

Referenced by shortest_path_edges_begin(), and shortest_path_edges_end().

Here is the call graph for this function:

Here is the caller graph for this function:

void dijkstra::fill_node_list ( const node & t )

private

Definition at line 370 of file dijkstra.cpp.

View newest version in sPHENIX GitHub at line 370 of file dijkstra.cpp

References upload::dest, predecessor_node(), reached(), s, and shortest_path_node_list.

Referenced by shortest_path_nodes_begin(), and shortest_path_nodes_end().

Here is the call graph for this function:

Here is the caller graph for this function:

void dijkstra::init ( graph & G )

private

Definition at line 351 of file dijkstra.cpp.

View newest version in sPHENIX GitHub at line 351 of file dijkstra.cpp

References black, ne_map< Key, Value, Graph, Alloc >::clear(), dist, ne_map< Key, Value, Graph, Alloc >::init(), mark, graph::nodes_begin(), graph::nodes_end(), pred, preds_set, shortest_path_edge_list, and shortest_path_node_list.

Referenced by run().

Here is the call graph for this function:

Here is the caller graph for this function:

edge dijkstra::predecessor_edge ( const node & n ) const

Predecessor edge of node n on the shortest path from the source node.

If n is a root or wasn't reached the return value is the invalid edge edge::edge().

Parameters

n node

Returns: predecessor edge of n

See Also: dijkstra::store_preds; dijkstra::predecessor_node

Note: The method requires that predecessor calculation option was enabled during last run.

Definition at line 273 of file dijkstra.cpp.

View newest version in sPHENIX GitHub at line 273 of file dijkstra.cpp

References assert, n, pred, and preds_set.

Referenced by fill_edge_list().

Here is the caller graph for this function:

node dijkstra::predecessor_node ( const node & n ) const

Predecessor node of node n on the shortest path from the source node.

If n is a root or wasn't reached the return value is the invalid node node::node().

Parameters

n node

Returns: predecessor node of n

See Also: dijkstra::store_preds; dijkstra::predecessor_edge

Note: The method requires that predecessor calculation option was enabled during last run.

Definition at line 262 of file dijkstra.cpp.

View newest version in sPHENIX GitHub at line 262 of file dijkstra.cpp

References assert, n, pred, preds_set, reached(), and s.

Referenced by fill_edge_list(), and fill_node_list().

Here is the call graph for this function:

Here is the caller graph for this function:

bool dijkstra::reached ( const node & n ) const

Returns whether n is reachable from source node.

Parameters

n node

Returns: true iff n was reached from source

Definition at line 250 of file dijkstra.cpp.

View newest version in sPHENIX GitHub at line 250 of file dijkstra.cpp

References black, mark, and n.

Referenced by fill_edge_list(), fill_node_list(), predecessor_node(), shortest_path_edges_begin(), shortest_path_edges_end(), shortest_path_nodes_begin(), and shortest_path_nodes_end().

Here is the caller graph for this function:

void dijkstra::reset ( )

virtual

Resets Dijkstra's algorithm.

It prepares the algorithm to be applied again, possibly to another graph.

Note: The weights are not reset. You can apply this algorithms

See Also: algorithm::reset

Implements algorithm.

Definition at line 336 of file dijkstra.cpp.

View newest version in sPHENIX GitHub at line 336 of file dijkstra.cpp

References reset_algorithm().

Here is the call graph for this function:

void dijkstra::reset_algorithm ( )

private

Definition at line 342 of file dijkstra.cpp.

View newest version in sPHENIX GitHub at line 342 of file dijkstra.cpp

References preds_set, s, t, and weights_set.

Referenced by dijkstra(), and reset().

Here is the caller graph for this function:

int dijkstra::run ( graph & G )

virtual

Runs shortest path algorithm on G.

This should return always algorithm::GTL_OK. The return value only tracks errors that might occur. Afterwards the result of the test can be accessed via access methods.

Parameters

G graph

Return values

algorithm::GTL_OK	on success
algorithm::GTL_ERROR	otherwise

See Also: algorithm::run

Implements algorithm.

Definition at line 155 of file dijkstra.cpp.

View newest version in sPHENIX GitHub at line 155 of file dijkstra.cpp

References node::adj_edges_begin(), node::adj_edges_end(), node::adj_edges_iterator(), black, dist, grey, algorithm::GTL_OK, init(), mark, graph::number_of_nodes(), node::opposite(), pred, preds_set, s, t, weight, and white.

Here is the call graph for this function:

dijkstra::shortest_path_edge_iterator dijkstra::shortest_path_edges_begin ( const node & dest )

Returns an iterator to the beginning edge of a shortest edge path to node dest.

Parameters

dest	target node

Returns: beginning edge iterator of a shortest path

Note: The method requires that predecessor calculation option was enabled during last run. If this method is called on the shortest path to dest for the first time (before dijkstra::shortest_path_edges_end) it needs $\mathcal{O}(\mbox{length of this path})$ time.

Definition at line 308 of file dijkstra.cpp.

View newest version in sPHENIX GitHub at line 308 of file dijkstra.cpp

References assert, upload::dest, fill_edge_list(), preds_set, reached(), s, and shortest_path_edge_list.

Here is the call graph for this function:

dijkstra::shortest_path_edge_iterator dijkstra::shortest_path_edges_end ( const node & dest )

Returns an iterator one after the end of a shortest edge path to node dest.

Parameters

dest	target node

Returns: shortest path end edge iterator

Note: The method requires that predecessor calculation option was enabled during last run. If this method is called on the shortest path to dest for the first time (before dijkstra::shortest_path_edges_begin) it needs $\mathcal{O}(\mbox{length of this path})$ time.

Definition at line 322 of file dijkstra.cpp.

View newest version in sPHENIX GitHub at line 322 of file dijkstra.cpp

References assert, upload::dest, fill_edge_list(), preds_set, reached(), s, and shortest_path_edge_list.

Here is the call graph for this function:

dijkstra::shortest_path_node_iterator dijkstra::shortest_path_nodes_begin ( const node & dest )

Returns an iterator to the beginning (to the source node) of a shortest node path to node dest.

Parameters

dest	target node

Returns: beginning node iterator of a shortest path

Note: The method requires that predecessor calculation option was enabled during last run. If this method is called on the shortest path to dest for the first time (before dijkstra::shortest_path_nodes_end) it needs $\mathcal{O}(\mbox{length of this path})$ time.

Definition at line 280 of file dijkstra.cpp.

View newest version in sPHENIX GitHub at line 280 of file dijkstra.cpp

References assert, upload::dest, fill_node_list(), preds_set, reached(), s, and shortest_path_node_list.

Here is the call graph for this function:

dijkstra::shortest_path_node_iterator dijkstra::shortest_path_nodes_end ( const node & dest )

Returns an iterator one after the end (one after node dest) of a shortest node path to node dest.

Parameters

dest	target node

Returns: shortest path end node iterator

Note: The method requires that predecessor calculation option was enabled during last run. If this method is called on the shortest path to dest for the first time (before dijkstra::shortest_path_nodes_begin) it needs $\mathcal{O}(\mbox{length of this path})$ time.

Definition at line 294 of file dijkstra.cpp.

View newest version in sPHENIX GitHub at line 294 of file dijkstra.cpp

References assert, upload::dest, fill_node_list(), preds_set, reached(), s, and shortest_path_node_list.

Here is the call graph for this function:

void dijkstra::source ( const node & n )

Sets source node.

The default source is the invalid node (node::node()), in this case an arbitrary node is chosen and stored when this algorithm is run.

Parameters

n	source node

Definition at line 93 of file dijkstra.cpp.

View newest version in sPHENIX GitHub at line 93 of file dijkstra.cpp

References n, and s.

node dijkstra::source ( ) const

Returns source node.

Returns: source node

Definition at line 232 of file dijkstra.cpp.

View newest version in sPHENIX GitHub at line 232 of file dijkstra.cpp

References s.

void dijkstra::store_preds ( bool set )

Enables or disables the storing of predecessors.

If enabled for every node the predecessor on the shortest path from will be stored.

Parameters

set	`true` if predecessors should be stored

See Also: dijkstra::predecessor_node; dijkstra::predecessor_edge

Definition at line 112 of file dijkstra.cpp.

View newest version in sPHENIX GitHub at line 112 of file dijkstra.cpp

References preds_set.

bool dijkstra::store_preds ( ) const

Returns whether the storing of predecessors is enabled.

Returns: true iff the storing of predecessors is enabled

See Also: dijkstra::predecessor

Definition at line 244 of file dijkstra.cpp.

View newest version in sPHENIX GitHub at line 244 of file dijkstra.cpp

References preds_set.

void dijkstra::target ( const node & n )

Sets target node.

If a target is set with this method the algorithm stops if a shortest distance to n is found. Ohterwise shortest paths are computed from source to any node in the graph.

Parameters

n	target node

Definition at line 99 of file dijkstra.cpp.

View newest version in sPHENIX GitHub at line 99 of file dijkstra.cpp

References n, and t.

node dijkstra::target ( ) const

Returns target node if set, node::node() else.

Returns: target node

Definition at line 238 of file dijkstra.cpp.

View newest version in sPHENIX GitHub at line 238 of file dijkstra.cpp

References t.

void dijkstra::weights ( const edge_map< double > & weight )

Sets weights of the edges.

This method must be called before check run.

Parameters

weight weights of the edges

Definition at line 105 of file dijkstra.cpp.

View newest version in sPHENIX GitHub at line 105 of file dijkstra.cpp

References weight, and weights_set.

Member Data Documentation

node_map<double> dijkstra::dist

private

Definition at line 362 of file dijkstra.h.

View newest version in sPHENIX GitHub at line 362 of file dijkstra.h

Referenced by distance(), init(), and run().

node_map<int> dijkstra::mark

private

Definition at line 353 of file dijkstra.h.

View newest version in sPHENIX GitHub at line 353 of file dijkstra.h

Referenced by init(), reached(), and run().

node_map<edge> dijkstra::pred

private

Definition at line 346 of file dijkstra.h.

View newest version in sPHENIX GitHub at line 346 of file dijkstra.h

Referenced by init(), predecessor_edge(), predecessor_node(), and run().

bool dijkstra::preds_set

private

Definition at line 329 of file dijkstra.h.

View newest version in sPHENIX GitHub at line 329 of file dijkstra.h

Referenced by init(), predecessor_edge(), predecessor_node(), reset_algorithm(), run(), shortest_path_edges_begin(), shortest_path_edges_end(), shortest_path_nodes_begin(), shortest_path_nodes_end(), and store_preds().

node dijkstra::s

private

Definition at line 305 of file dijkstra.h.

View newest version in sPHENIX GitHub at line 305 of file dijkstra.h

Referenced by check(), fill_edge_list(), fill_node_list(), predecessor_node(), reset_algorithm(), run(), shortest_path_edges_begin(), shortest_path_edges_end(), shortest_path_nodes_begin(), shortest_path_nodes_end(), and source().

node_map<list<edge> > dijkstra::shortest_path_edge_list

private

Definition at line 386 of file dijkstra.h.

View newest version in sPHENIX GitHub at line 386 of file dijkstra.h

Referenced by fill_edge_list(), init(), shortest_path_edges_begin(), and shortest_path_edges_end().

node_map<list<node> > dijkstra::shortest_path_node_list

private

Definition at line 374 of file dijkstra.h.

View newest version in sPHENIX GitHub at line 374 of file dijkstra.h

Referenced by fill_node_list(), init(), shortest_path_nodes_begin(), and shortest_path_nodes_end().

node dijkstra::t

private

Definition at line 313 of file dijkstra.h.

View newest version in sPHENIX GitHub at line 313 of file dijkstra.h

Referenced by reset_algorithm(), run(), and target().

edge_map<double> dijkstra::weight

private

Definition at line 337 of file dijkstra.h.

View newest version in sPHENIX GitHub at line 337 of file dijkstra.h

Referenced by check(), run(), and weights().

bool dijkstra::weights_set

private

Definition at line 321 of file dijkstra.h.

View newest version in sPHENIX GitHub at line 321 of file dijkstra.h

Referenced by check(), reset_algorithm(), and weights().

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

JETSCAPE/blob/main/external_packages/gtl/include/GTL/dijkstra.h
JETSCAPE/blob/main/external_packages/gtl/src/dijkstra.cpp

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation