vcsn::detail::eppstein< Aut > Class Template Reference

Eppstein implementation of the K shortest path problem adapted to Vcsn. More...

#include <eppstein.hh>

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

Public Types
using	queue_t = vcsn::min_fibonacci_heap< implicit_path_t >

Public Member Functions
	eppstein (const automaton_t &aut)
std::vector< path< automaton_t > >	k_shortest_path (state_t src, state_t dst, int K)
	Compute the K shortest paths in the automaton from src to dst. More...

Private Types
using	automaton_t = Aut
using	state_t = state_t_of< automaton_t >
using	transition_t = transition_t_of< automaton_t >
using	weight_t = weight_t_of< automaton_t >
using	implicit_path_t = implicit_path< automaton_t >
using	sidetrack_costs_t = std::unordered_map< transition_t, weight_t >

Private Member Functions
void	add_children_to_queue_ (sidetrack_costs_t &sidetracks, state_t src, const implicit_path_t &k_path_implicit, int k, queue_t &queue, shortest_path_tree< automaton_t > &tree)
	Update queue with children of the first state in the sidetrack path. More...

Private Attributes
const automaton_t &	aut_

Detailed Description

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

Eppstein implementation of the K shortest path problem adapted to Vcsn.

Based on Finding the k shortest paths, David Eppstein (1997).

Definition at line 19 of file eppstein.hh.

Member Typedef Documentation

automaton_t

template<Automaton Aut>

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

private

Definition at line 21 of file eppstein.hh.

implicit_path_t

template<Automaton Aut>

using vcsn::detail::eppstein< Aut >::implicit_path_t = implicit_path<automaton_t>

private

Definition at line 25 of file eppstein.hh.

queue_t

template<Automaton Aut>

using vcsn::detail::eppstein< Aut >::queue_t = vcsn::min_fibonacci_heap<implicit_path_t>

Definition at line 33 of file eppstein.hh.

sidetrack_costs_t

template<Automaton Aut>

using vcsn::detail::eppstein< Aut >::sidetrack_costs_t = std::unordered_map<transition_t, weight_t>

private

Definition at line 26 of file eppstein.hh.

state_t

template<Automaton Aut>

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

private

Definition at line 22 of file eppstein.hh.

transition_t

template<Automaton Aut>

using vcsn::detail::eppstein< Aut >::transition_t = transition_t_of<automaton_t>

private

Definition at line 23 of file eppstein.hh.

weight_t

template<Automaton Aut>

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

private

Definition at line 24 of file eppstein.hh.

Constructor & Destructor Documentation

eppstein()

template<Automaton Aut>

vcsn::detail::eppstein< Aut >::eppstein ( const automaton_t &  aut )

inline

Definition at line 29 of file eppstein.hh.

Member Function Documentation

add_children_to_queue_()

template<Automaton Aut>

void vcsn::detail::eppstein< Aut >::add_children_to_queue_ ( sidetrack_costs_t &  sidetracks, state_t  src, const implicit_path_t &  k_path_implicit, int  k, queue_t &  queue, shortest_path_tree< automaton_t > &  tree  )

inlineprivate

Update queue with children of the first state in the sidetrack path.

On-the-fly update of the sidetrack costs map (avoid computing every sidetrack costs when not needed).

Definition at line 79 of file eppstein.hh.

References vcsn::detail::all_out(), vcsn::detail::eppstein< Aut >::aut_, vcsn::detail::shortest_path_tree< Aut >::get_parent_of(), vcsn::detail::implicit_path< Aut >::get_sidetrack(), vcsn::detail::implicit_path< Aut >::get_weight(), vcsn::detail::shortest_path_tree< Aut >::get_weight_of(), and vcsn::has().

Referenced by vcsn::detail::eppstein< Aut >::k_shortest_path().

Here is the call graph for this function:

k_shortest_path()

template<Automaton Aut>

std::vector<path<automaton_t> > vcsn::detail::eppstein< Aut >::k_shortest_path ( state_t  src, state_t  dst, int  K  )

inline

Compute the K shortest paths in the automaton from src to dst.

Definition at line 38 of file eppstein.hh.

References vcsn::detail::eppstein< Aut >::add_children_to_queue_(), vcsn::detail::eppstein< Aut >::aut_, vcsn::detail::make_shortest_path_tree(), vcsn::detail::implicit_path< Aut >::null_parent_path, and vcsn::res.

Referenced by vcsn::compute_eppstein().

Here is the call graph for this function:

Member Data Documentation

aut_

template<Automaton Aut>

const automaton_t& vcsn::detail::eppstein< Aut >::aut_

private

Definition at line 121 of file eppstein.hh.

Referenced by vcsn::detail::eppstein< Aut >::add_children_to_queue_(), and vcsn::detail::eppstein< Aut >::k_shortest_path().

---

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

• vcsn/algos/eppstein.hh