Dijkstra's Algorithm for computing a shortest path from a single source to a single target. More...

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

Inheritance diagram for bid_dijkstra:

Collaboration diagram for bid_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
	bid_dijkstra ()
	Default constructor.

virtual	~bid_dijkstra ()
	Destructor.

void	source_target (const node &s, const node &t)
	Sets source and target node.

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

void	store_path (bool set)
	Enables or disables the storing of the shortest path.

virtual int	check (graph &G)
	Checks whether the preconditions for bidirectional 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_path () const
	Returns whether the storing of the shortest path is enabled.

bool	reached () const
	Returns whether target is reachable from source.

double	distance () const
	Returns the distance from source node to target node.

shortest_path_node_iterator	shortest_path_nodes_begin ()
	Returns an iterator to the beginning (to the source node) of the shortest node path to target node.

shortest_path_node_iterator	shortest_path_nodes_end ()
	Returns an iterator one after the end (one after target node) of the shortest node path to target node.

shortest_path_edge_iterator	shortest_path_edges_begin ()
	Returns an iterator to the beginning edge of the shortest edge path to target node.

shortest_path_edge_iterator	shortest_path_edges_end ()
	Returns an iterator one after the end of a shortest edge path to target node.

virtual void	reset ()
	Resets Dijkstra's bidirectional 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_edge_lists (const node &n)

Private Attributes
node	s

node	t

bool	weights_set

bool	path_set

edge_map< double >	weight

double	dist

bool	reached_t

node_map< edge >	pred

node_map< edge >	succ

node_map< int >	source_mark

node_map< int >	target_mark

node_map< double >	source_dist

node_map< double >	target_dist

list< node >	shortest_path_node_list

list< edge >	shortest_path_edge_list

Detailed Description

Dijkstra's Algorithm for computing a shortest path from a single source to a single target.

Date:: 2003/03/24 15:58:54

Revision:: 1.3

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

See Also: dijkstra; 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 36 of file bid_dijkstra.h.

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

Member Typedef Documentation

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

Iterator type for traversing edges on one shortest path.

Definition at line 47 of file bid_dijkstra.h.

View newest version in sPHENIX GitHub at line 47 of file bid_dijkstra.h

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

Iterator type for traversing nodes on one shortest path.

Definition at line 42 of file bid_dijkstra.h.

View newest version in sPHENIX GitHub at line 42 of file bid_dijkstra.h

Member Enumeration Documentation

enum bid_dijkstra::node_color

Enumerator:

white
grey
black

Definition at line 52 of file bid_dijkstra.h.

View newest version in sPHENIX GitHub at line 52 of file bid_dijkstra.h

Constructor & Destructor Documentation

bid_dijkstra::bid_dijkstra ( )

Default constructor.

Enables only the calculation of shortest paths.

See Also: algorithm::algorithm

Definition at line 82 of file bid_dijkstra.cpp.

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

References reset_algorithm().

Here is the call graph for this function:

bid_dijkstra::~bid_dijkstra ( )

virtual

Destructor.

See Also: algorithm::~algorithm

Definition at line 88 of file bid_dijkstra.cpp.

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

Member Function Documentation

int bid_dijkstra::check ( graph & G )

virtual

Checks whether the preconditions for bidirectional Dijkstra are satisfied.

The Precondition are that the weights of the edges have been set and that the graph has at least one node. Additionally all edge weights must be $\ge 0$ and and source and target nodes 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::weigths; algorithm::check

Implements algorithm.

Definition at line 113 of file bid_dijkstra.cpp.

View newest version in sPHENIX GitHub at line 113 of file bid_dijkstra.cpp

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

Here is the call graph for this function:

double bid_dijkstra::distance ( ) const

Returns the distance from source node to target node.

Returns: distance if target is bid_dijkstra::reached, -1.0 else

Definition at line 480 of file bid_dijkstra.cpp.

View newest version in sPHENIX GitHub at line 480 of file bid_dijkstra.cpp

References dist.

void bid_dijkstra::fill_node_edge_lists ( const node & n )

private

Definition at line 552 of file bid_dijkstra.cpp.

View newest version in sPHENIX GitHub at line 552 of file bid_dijkstra.cpp

References dist, n, edge::opposite(), path_set, pred, reached_t, s, shortest_path_edge_list, shortest_path_node_list, source_dist, succ, t, and target_dist.

Referenced by run().

Here is the call graph for this function:

Here is the caller graph for this function:

void bid_dijkstra::init ( graph & G )

private

Definition at line 535 of file bid_dijkstra.cpp.

View newest version in sPHENIX GitHub at line 535 of file bid_dijkstra.cpp

References black, ne_map< Key, Value, Graph, Alloc >::init(), path_set, pred, shortest_path_edge_list, shortest_path_node_list, source_dist, source_mark, succ, target_dist, and target_mark.

Referenced by run().

Here is the call graph for this function:

Here is the caller graph for this function:

bool bid_dijkstra::reached ( ) const

Returns whether target is reachable from source.

Returns: true iff target was reached from source

Definition at line 474 of file bid_dijkstra.cpp.

View newest version in sPHENIX GitHub at line 474 of file bid_dijkstra.cpp

References reached_t.

void bid_dijkstra::reset ( )

virtual

Resets Dijkstra's bidirectional 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 518 of file bid_dijkstra.cpp.

View newest version in sPHENIX GitHub at line 518 of file bid_dijkstra.cpp

References reset_algorithm().

Here is the call graph for this function:

void bid_dijkstra::reset_algorithm ( )

private

Definition at line 524 of file bid_dijkstra.cpp.

View newest version in sPHENIX GitHub at line 524 of file bid_dijkstra.cpp

References dist, path_set, reached_t, s, t, and weights_set.

Referenced by bid_dijkstra(), and reset().

Here is the caller graph for this function:

int bid_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 162 of file bid_dijkstra.cpp.

View newest version in sPHENIX GitHub at line 162 of file bid_dijkstra.cpp

References node::adj_edges_iterator(), black, graph::edges_begin(), graph::edges_end(), fill_node_edge_lists(), grey, algorithm::GTL_OK, init(), graph::is_directed(), graph::number_of_nodes(), node::opposite(), path_set, pred, s, source_dist, source_mark, succ, t, target_dist, target_mark, weight, and white.

Here is the call graph for this function:

bid_dijkstra::shortest_path_edge_iterator bid_dijkstra::shortest_path_edges_begin ( )

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

See Also: bid_dijkstra::store_path

Returns: beginning edge iterator of the shortest path

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

Definition at line 503 of file bid_dijkstra.cpp.

View newest version in sPHENIX GitHub at line 503 of file bid_dijkstra.cpp

References assert, path_set, and shortest_path_edge_list.

bid_dijkstra::shortest_path_edge_iterator bid_dijkstra::shortest_path_edges_end ( )

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

See Also: bid_dijkstra::store_path

Returns: shortest path end edge iterator

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

Definition at line 511 of file bid_dijkstra.cpp.

View newest version in sPHENIX GitHub at line 511 of file bid_dijkstra.cpp

References assert, path_set, and shortest_path_edge_list.

bid_dijkstra::shortest_path_node_iterator bid_dijkstra::shortest_path_nodes_begin ( )

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

Returns: beginning node iterator of the shortest path

See Also: bid_dijkstra::store_path

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

Definition at line 487 of file bid_dijkstra.cpp.

View newest version in sPHENIX GitHub at line 487 of file bid_dijkstra.cpp

References assert, path_set, and shortest_path_node_list.

bid_dijkstra::shortest_path_node_iterator bid_dijkstra::shortest_path_nodes_end ( )

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

Returns: shortest path end node iterator

See Also: bid_dijkstra::store_path

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

Definition at line 495 of file bid_dijkstra.cpp.

View newest version in sPHENIX GitHub at line 495 of file bid_dijkstra.cpp

References assert, path_set, and shortest_path_node_list.

node bid_dijkstra::source ( ) const

Returns source node.

Returns: source node

Definition at line 456 of file bid_dijkstra.cpp.

View newest version in sPHENIX GitHub at line 456 of file bid_dijkstra.cpp

References s.

void bid_dijkstra::source_target	(	const node &	s,
		const node &	t
	)

Sets source and target node.

Must be executed every time before check and run of this algorithm.

Parameters

s	source node
t	target node

Definition at line 93 of file bid_dijkstra.cpp.

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

References s, and t.

void bid_dijkstra::store_path ( bool set )

Enables or disables the storing of the shortest path.

If enabled for every node and edge on the shortest path from source to target will be stored.

Parameters

set	true if path should be stored

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

Definition at line 107 of file bid_dijkstra.cpp.

View newest version in sPHENIX GitHub at line 107 of file bid_dijkstra.cpp

References path_set.

bool bid_dijkstra::store_path ( ) const

Returns whether the storing of the shortest path is enabled.

Returns: true iff the storing of path is enabled.

See Also: dijkstra::predecessor

Definition at line 468 of file bid_dijkstra.cpp.

View newest version in sPHENIX GitHub at line 468 of file bid_dijkstra.cpp

References path_set.

node bid_dijkstra::target ( ) const

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

Returns: target node

Definition at line 462 of file bid_dijkstra.cpp.

View newest version in sPHENIX GitHub at line 462 of file bid_dijkstra.cpp

References t.

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

Sets weights of the edges.

This method must be called before check and run.

Parameters

weight weights of the edges

Definition at line 100 of file bid_dijkstra.cpp.

View newest version in sPHENIX GitHub at line 100 of file bid_dijkstra.cpp

References weight, and weights_set.

Member Data Documentation

double bid_dijkstra::dist

private

Definition at line 285 of file bid_dijkstra.h.

View newest version in sPHENIX GitHub at line 285 of file bid_dijkstra.h

Referenced by distance(), fill_node_edge_lists(), and reset_algorithm().

bool bid_dijkstra::path_set

private

Definition at line 270 of file bid_dijkstra.h.

View newest version in sPHENIX GitHub at line 270 of file bid_dijkstra.h

Referenced by fill_node_edge_lists(), init(), reset_algorithm(), run(), shortest_path_edges_begin(), shortest_path_edges_end(), shortest_path_nodes_begin(), shortest_path_nodes_end(), and store_path().

node_map<edge> bid_dijkstra::pred

private

Definition at line 299 of file bid_dijkstra.h.

View newest version in sPHENIX GitHub at line 299 of file bid_dijkstra.h

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

bool bid_dijkstra::reached_t

private

Definition at line 292 of file bid_dijkstra.h.

View newest version in sPHENIX GitHub at line 292 of file bid_dijkstra.h

Referenced by fill_node_edge_lists(), reached(), and reset_algorithm().

node bid_dijkstra::s

private

Definition at line 246 of file bid_dijkstra.h.

View newest version in sPHENIX GitHub at line 246 of file bid_dijkstra.h

Referenced by check(), fill_node_edge_lists(), reset_algorithm(), run(), source(), and source_target().

list<edge> bid_dijkstra::shortest_path_edge_list

private

Definition at line 356 of file bid_dijkstra.h.

View newest version in sPHENIX GitHub at line 356 of file bid_dijkstra.h

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

list<node> bid_dijkstra::shortest_path_node_list

private

Definition at line 345 of file bid_dijkstra.h.

View newest version in sPHENIX GitHub at line 345 of file bid_dijkstra.h

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

node_map<double> bid_dijkstra::source_dist

private

Definition at line 327 of file bid_dijkstra.h.

View newest version in sPHENIX GitHub at line 327 of file bid_dijkstra.h

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

node_map<int> bid_dijkstra::source_mark

private

Definition at line 313 of file bid_dijkstra.h.

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

Referenced by init(), and run().

node_map<edge> bid_dijkstra::succ

private

Definition at line 306 of file bid_dijkstra.h.

View newest version in sPHENIX GitHub at line 306 of file bid_dijkstra.h

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

node bid_dijkstra::t

private

Definition at line 254 of file bid_dijkstra.h.

View newest version in sPHENIX GitHub at line 254 of file bid_dijkstra.h

Referenced by check(), fill_node_edge_lists(), reset_algorithm(), run(), source_target(), and target().

node_map<double> bid_dijkstra::target_dist

private

Definition at line 334 of file bid_dijkstra.h.

View newest version in sPHENIX GitHub at line 334 of file bid_dijkstra.h

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

node_map<int> bid_dijkstra::target_mark

private

Definition at line 320 of file bid_dijkstra.h.

View newest version in sPHENIX GitHub at line 320 of file bid_dijkstra.h

Referenced by init(), and run().

edge_map<double> bid_dijkstra::weight

private

Definition at line 278 of file bid_dijkstra.h.

View newest version in sPHENIX GitHub at line 278 of file bid_dijkstra.h

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

bool bid_dijkstra::weights_set

private

Definition at line 262 of file bid_dijkstra.h.

View newest version in sPHENIX GitHub at line 262 of file bid_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/bid_dijkstra.h
JETSCAPE/blob/main/external_packages/gtl/src/bid_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