Shortest Path Tree. More...

#include <shortest-path-tree.hh>

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

Public Member Functions
	shortest_path_tree (const automaton_t &aut, state_t root)

void	add (const node_t &n)

void	set_parent_of (state_t s, state_t parent)

weight_t	get_weight_of (state_t s) const

node_t &	get_node_of (state_t s)

state_t	get_parent_of (state_t s) const

state_t	get_root () const

node_t &	operator[] (state_t s)

Private Types
using	automaton_t = Aut

using	state_t = state_t_of< automaton_t >

using	weight_t = weight_t_of< automaton_t >

using	node_t = dijkstra_node< automaton_t >

using	map_t = std::unordered_map< state_t, node_t >

Private Member Functions
void	compute_ ()
	Compute the shortest path tree of aut_ starting from root_. More...

Private Attributes
map_t	states_

state_t	root_

const automaton_t &	aut_

Detailed Description

template<typename Aut>
class vcsn::detail::shortest_path_tree< Aut >

Shortest Path Tree.

Represent the tree of nodes in the graph with each node's parent being their lightest predecessor in the automaton (i.e., the path is from destination to source).

Definition at line 18 of file shortest-path-tree.hh.

Member Typedef Documentation

◆ automaton_t

template<typename Aut>

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

private

Definition at line 20 of file shortest-path-tree.hh.

◆ map_t

template<typename Aut>

using vcsn::detail::shortest_path_tree< Aut >::map_t = std::unordered_map<state_t, node_t>

private

Definition at line 24 of file shortest-path-tree.hh.

◆ node_t

template<typename Aut>

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

private

Definition at line 23 of file shortest-path-tree.hh.

◆ state_t

template<typename Aut>

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

private

Definition at line 21 of file shortest-path-tree.hh.

◆ weight_t

template<typename Aut>

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

private

Definition at line 22 of file shortest-path-tree.hh.

Constructor & Destructor Documentation

◆ shortest_path_tree()

template<typename Aut>

vcsn::detail::shortest_path_tree< Aut >::shortest_path_tree	(	const automaton_t &	aut,
		state_t	root
	)

inline

Definition at line 27 of file shortest-path-tree.hh.

References vcsn::detail::shortest_path_tree< Aut >::aut_, and vcsn::detail::shortest_path_tree< Aut >::compute_().

Here is the call graph for this function:

Member Function Documentation

◆ add()

template<typename Aut>

void vcsn::detail::shortest_path_tree< Aut >::add ( const node_t & n )

inline

Definition at line 35 of file shortest-path-tree.hh.

References vcsn::detail::dijkstra_node< Aut >::state_, and vcsn::detail::shortest_path_tree< Aut >::states_.

◆ compute_()

template<typename Aut>

void vcsn::detail::shortest_path_tree< Aut >::compute_ ( )

inlineprivate

Compute the shortest path tree of aut_ starting from root_.

Create a shortest path tree with root_ as root, then construct the tree by going backwards in the automaton with a basic shortest path method (heap of incoming nodes sorted by nodes' weight).

Definition at line 101 of file shortest-path-tree.hh.

References vcsn::detail::all_in(), vcsn::detail::shortest_path_tree< Aut >::aut_, vcsn::detail::shortest_path_tree< Aut >::get_node_of(), vcsn::detail::shortest_path_tree< Aut >::get_root(), and vcsn::detail::dijkstra_node< Aut >::get_weight().

Referenced by vcsn::detail::shortest_path_tree< Aut >::shortest_path_tree().

Here is the call graph for this function: