GraphLib::Internal::DijkstraIterator< G > Class Template Reference

Iterator that incrementally explores the shortest paths from a start node using Dijkstra's algorithm. More...

#include <dijkstra.h>

Public Types
using	difference_type = std::ptrdiff_t
using	value_type = G::id_type
	Type used to represent node identifiers, as defined by the graph type.

Public Member Functions
	DijkstraIterator (const G &graph, const value_type start)
	Constructs a Dijkstra iterator starting at a given node.
const DijkstraIterator	begin () const
	Returns an iterator at the beginning of the Dijkstra traversal.
const DijkstraIterator	end () const
	Returns an iterator that marks the end of the traversal.
std::pair< value_type, value_type >	operator* () const
	Returns the current node and its predecessor on the shortest path.
DijkstraIterator &	operator++ ()
	Advances the iterator to the next node in the shortest path tree.
bool	operator== (const DijkstraIterator &other) const
bool	operator!= (const DijkstraIterator &other) const
value_type	get_current_pred (const value_type node) const
	Returns the current predecessor of a node in the shortest path tree.
value_type	get_current_cost (const value_type node) const
	Returns the current cost to reach a node from the start.
bool	has_seen (const value_type node) const
	Checks whether a node has been encountered during traversal.

Private Types
using	edge_weight_type = typename G::edge_type::weight_type
using	priority_pair_type = Internal::PriorityPair<edge_weight_type, value_type>
using	priority_queue_type

Private Member Functions
void	perform_update ()
	Performs one iteration of the Dijkstra algorithm, expanding the best node.

Private Attributes
const G &	graph
const value_type	start
bool	done {false}
unsigned long	iterations {0}
std::unordered_map< value_type, std::pair< value_type, edge_weight_type > >	node_lookup {}
std::set< value_type >	closed_nodes {}
priority_queue_type	frontier {}

Detailed Description

template<valid_weighted_graph_type G>
class GraphLib::Internal::DijkstraIterator< G >

Iterator that incrementally explores the shortest paths from a start node using Dijkstra's algorithm.

Template Parameters

G	A graph type that satisfies the valid_weighted_graph_type concept.

Definition at line 25 of file dijkstra.h.

Member Typedef Documentation

difference_type

template<valid_weighted_graph_type G>

using GraphLib::Internal::DijkstraIterator< G >::difference_type = std::ptrdiff_t

Type used to represent differences between iterators (for compliance with standard iterator traits).

Definition at line 29 of file dijkstra.h.

edge_weight_type

template<valid_weighted_graph_type G>

using GraphLib::Internal::DijkstraIterator< G >::edge_weight_type = typename G::edge_type::weight_type

private

Definition at line 129 of file dijkstra.h.

priority_pair_type

template<valid_weighted_graph_type G>

using GraphLib::Internal::DijkstraIterator< G >::priority_pair_type = Internal::PriorityPair<edge_weight_type, value_type>

private

Definition at line 130 of file dijkstra.h.

priority_queue_type

template<valid_weighted_graph_type G>

using GraphLib::Internal::DijkstraIterator< G >::priority_queue_type

private

Initial value:

 
        std::priority_queue<priority_pair_type, std::vector<priority_pair_type>, std::greater<priority_pair_type>>

Definition at line 131 of file dijkstra.h.

value_type

template<valid_weighted_graph_type G>

using GraphLib::Internal::DijkstraIterator< G >::value_type = G::id_type

Type used to represent node identifiers, as defined by the graph type.

Definition at line 31 of file dijkstra.h.

Constructor & Destructor Documentation

DijkstraIterator()

template<valid_weighted_graph_type G>

GraphLib::Internal::DijkstraIterator< G >::DijkstraIterator ( const G & graph, const value_type start )

inline

Constructs a Dijkstra iterator starting at a given node.

Parameters

graph	The graph to explore.
start	The starting node ID.

Definition at line 39 of file dijkstra.h.

Member Function Documentation

begin()

template<valid_weighted_graph_type G>

const DijkstraIterator GraphLib::Internal::DijkstraIterator< G >::begin ( ) const

inline

Returns an iterator at the beginning of the Dijkstra traversal.

Definition at line 51 of file dijkstra.h.

end()

template<valid_weighted_graph_type G>

const DijkstraIterator GraphLib::Internal::DijkstraIterator< G >::end ( ) const

inline

Returns an iterator that marks the end of the traversal.

Definition at line 59 of file dijkstra.h.

get_current_cost()

template<valid_weighted_graph_type G>

value_type GraphLib::Internal::DijkstraIterator< G >::get_current_cost ( const value_type node ) const

inline

Returns the current cost to reach a node from the start.

Definition at line 113 of file dijkstra.h.

get_current_pred()

template<valid_weighted_graph_type G>

value_type GraphLib::Internal::DijkstraIterator< G >::get_current_pred ( const value_type node ) const

inline

Returns the current predecessor of a node in the shortest path tree.

Definition at line 105 of file dijkstra.h.

has_seen()

template<valid_weighted_graph_type G>

bool GraphLib::Internal::DijkstraIterator< G >::has_seen ( const value_type node ) const

inline

Checks whether a node has been encountered during traversal.

Definition at line 121 of file dijkstra.h.

operator!=()

template<valid_weighted_graph_type G>

bool GraphLib::Internal::DijkstraIterator< G >::operator!= ( const DijkstraIterator< G > & other ) const

inline

Definition at line 95 of file dijkstra.h.

operator*()

template<valid_weighted_graph_type G>

std::pair< value_type, value_type > GraphLib::Internal::DijkstraIterator< G >::operator* ( ) const

inline

Returns the current node and its predecessor on the shortest path.

Definition at line 69 of file dijkstra.h.

operator++()

template<valid_weighted_graph_type G>

DijkstraIterator & GraphLib::Internal::DijkstraIterator< G >::operator++ ( )

inline

Advances the iterator to the next node in the shortest path tree.

Definition at line 78 of file dijkstra.h.

operator==()

template<valid_weighted_graph_type G>

bool GraphLib::Internal::DijkstraIterator< G >::operator== ( const DijkstraIterator< G > & other ) const

inline

Definition at line 85 of file dijkstra.h.

perform_update()

template<valid_weighted_graph_type G>

void GraphLib::Internal::DijkstraIterator< G >::perform_update ( )

inlineprivate

Performs one iteration of the Dijkstra algorithm, expanding the best node.

Definition at line 154 of file dijkstra.h.

Member Data Documentation

closed_nodes

template<valid_weighted_graph_type G>

std::set<value_type> GraphLib::Internal::DijkstraIterator< G >::closed_nodes {}

private

Definition at line 143 of file dijkstra.h.

done

template<valid_weighted_graph_type G>

bool GraphLib::Internal::DijkstraIterator< G >::done {false}

private

Definition at line 136 of file dijkstra.h.

frontier

template<valid_weighted_graph_type G>

priority_queue_type GraphLib::Internal::DijkstraIterator< G >::frontier {}

private

Definition at line 149 of file dijkstra.h.

graph

template<valid_weighted_graph_type G>

const G& GraphLib::Internal::DijkstraIterator< G >::graph

private

Definition at line 134 of file dijkstra.h.

iterations

template<valid_weighted_graph_type G>

unsigned long GraphLib::Internal::DijkstraIterator< G >::iterations {0}

private

Definition at line 137 of file dijkstra.h.

node_lookup

template<valid_weighted_graph_type G>

std::unordered_map<value_type, std::pair<value_type, edge_weight_type> > GraphLib::Internal::DijkstraIterator< G >::node_lookup {}

private

Definition at line 140 of file dijkstra.h.

start

template<valid_weighted_graph_type G>

const value_type GraphLib::Internal::DijkstraIterator< G >::start

private

Definition at line 135 of file dijkstra.h.

---

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

• include/GraphLib/algorithms/dijkstra.h