Dijkstra Node implementation. More...

#include <dijkstra-node.hh>

Collaboration diagram for vcsn::detail::dijkstra_node< Aut >:

Public Member Functions
	dijkstra_node ()=default

	dijkstra_node (const automaton_t &aut, state_t state, boost::optional< weight_t > weight, state_t parent, unsigned depth=std::numeric_limits< unsigned >::max())

bool	operator< (const dijkstra_node &other) const
	Compare weights, used to order nodes in the shortest path heap. More...

weight_t	get_weight () const
	If there is no weight in the node then its weight is the weightset's maximum. More...

void	set_weight (weight_t weight)

state_t	get_state () const

unsigned	get_depth () const

void	set_depth (unsigned depth)

void	set_parent (state_t parent)

state_t	get_parent () const

Private Types
using	automaton_t = Aut

using	weight_t = weight_t_of< automaton_t >

using	state_t = state_t_of< automaton_t >

using	weightset_ptr = const weightset_t_of< automaton_t > *
	We have 2 alternatives to raw pointer: More...

Private Attributes
unsigned	depth_

state_t	state_

state_t	parent_

boost::optional< weight_t >	weight_

weightset_ptr	ws_

Detailed Description

template<Automaton Aut>
class vcsn::detail::dijkstra_node< Aut >

Dijkstra Node implementation.

Abstract representation of each node in shortest paths. Represented by their corresponding state, weight, depth in the automaton, and parent in the shortest path tree. Used by Eppstein algorithm to retrieve the next best predecessor to be treated. Sorted in a heap considering their weights (during the first path computation). Default constructed weights correspond to the maximum value of the weightset.

Definition at line 23 of file dijkstra-node.hh.

Member Typedef Documentation

◆ automaton_t

template<Automaton Aut>

using vcsn::detail::dijkstra_node< Aut >::automaton_t = Aut

private

Definition at line 25 of file dijkstra-node.hh.

◆ state_t

template<Automaton Aut>

using vcsn::detail::dijkstra_node< Aut >::state_t = state_t_of<automaton_t>

private

Definition at line 27 of file dijkstra-node.hh.

◆ weight_t

template<Automaton Aut>

using vcsn::detail::dijkstra_node< Aut >::weight_t = weight_t_of<automaton_t>

private

Definition at line 26 of file dijkstra-node.hh.

◆ weightset_ptr

template<Automaton Aut>

using vcsn::detail::dijkstra_node< Aut >::weightset_ptr = const weightset_t_of<automaton_t>*

private

We have 2 alternatives to raw pointer:

Reference: Not possible as the dijkstra node is used in a boost container that requires default contructible objects.
Shared pointer: Using the shared pointer returned by aut->weightset() would work but slows the algorithm down as a lot of dijkstra nodes are created. Hence, we stick with the raw pointer for now.

Definition at line 35 of file dijkstra-node.hh.

Constructor & Destructor Documentation

◆ dijkstra_node() [1/2]

template<Automaton Aut>

vcsn::detail::dijkstra_node< Aut >::dijkstra_node ( )

default

◆ dijkstra_node() [2/2]

template<Automaton Aut>

vcsn::detail::dijkstra_node< Aut >::dijkstra_node	(	const automaton_t &	aut,
		state_t	state,
		boost::optional< weight_t >	weight,
		state_t	parent,
		unsigned	depth = `std::numeric_limits<unsigned>::max()`
	)