Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
Classes | Functions
Aleph::k_shortest_paths_detail Namespace Reference

Classes

struct  Filtered_Show_Arc
 
struct  Path_Snapshot
 
struct  Path_State
 
struct  Reverse_Arc_Distance
 
struct  Suffix_Index
 

Functions

template<class GT , class Distance , class SA >
void validate_non_negative_weights (const GT &g, Distance distance, SA sa)
 
template<class GT , typename Cost_Type >
Path_Snapshot< GT, Cost_Type > make_path_snapshot (const Path_State< GT, Cost_Type > &path)
 
template<class GT , typename Cost_Type >
Path_State< GT, Cost_Type > path_to_state (const Path< GT > &path, const Cost_Type total_cost)
 
template<class GT , typename Cost_Type >
Path< GT > state_to_path (const GT &g, const Path_State< GT, Cost_Type > &state)
 
template<class GT , typename Cost_Type >
bool same_path_sequence (const Path_State< GT, Cost_Type > &a, const Path_State< GT, Cost_Type > &b)
 
template<class GT , typename Cost_Type >
bool same_prefix_nodes (const Path_Snapshot< GT, Cost_Type > &a, const Path_Snapshot< GT, Cost_Type > &b, const size_t spur_index)
 
template<class GT , typename Cost_Type >
bool contains_path (const Array< Path_State< GT, Cost_Type > > &container, const Path_State< GT, Cost_Type > &candidate)
 
template<class GT , typename Cost_Type >
Cost_Type get_dist_to_target (const Suffix_Index< GT, Cost_Type > &index, typename GT::Node *node)
 
template<class GT , typename Cost_Type >
GT::Node * get_tree_next (const Suffix_Index< GT, Cost_Type > &index, typename GT::Node *node)
 
template<class GT , typename Cost_Type >
GT::Arc * get_tree_arc (const Suffix_Index< GT, Cost_Type > &index, typename GT::Node *node)
 
template<template< class, class > class Itor, class GT , class Distance , class SA >
Suffix_Index< GT, typename Distance::Distance_Type > build_suffix_index_with_itor (const GT &g, typename GT::Node *target, Distance distance, SA sa)
 
template<class GT , class Distance , class SA >
Suffix_Index< GT, typename Distance::Distance_Type > build_suffix_index_digraph (const GT &g, typename GT::Node *target, Distance distance, SA sa)
 
template<class GT , class Distance , class SA >
Suffix_Index< GT, typename Distance::Distance_Type > build_suffix_index (const GT &g, typename GT::Node *target, Distance distance, SA sa)
 
template<class GT , typename Cost_Type >
bool build_suffix_state (const GT &g, const Suffix_Index< GT, Cost_Type > &index, typename GT::Node *start, typename GT::Node *target, Path_State< GT, Cost_Type > &out_suffix)
 
template<class GT , class Distance , class SA >
bool shortest_path_filtered (const GT &g, typename GT::Node *source, typename GT::Node *target, Distance distance, SA sa, const DynSetTree< typename GT::Node * > *forbidden_nodes, const DynSetTree< typename GT::Arc * > *forbidden_arcs, Path_State< GT, typename Distance::Distance_Type > &out)
 
template<class GT , class Distance >
Distance::Distance_Type compute_cost_from_arcs (const DynList< typename GT::Arc * > &arcs, Distance distance)
 
template<class GT , typename Cost_Type >
Path_State< GT, Cost_Type > compose_candidate (const Path_Snapshot< GT, Cost_Type > &base_path, const size_t spur_index, const Path_State< GT, Cost_Type > &spur_state)
 
template<class GT , typename Cost_Type >
Path_State< GT, Cost_Type > compose_general_candidate (const Path_Snapshot< GT, Cost_Type > &base_path, const size_t spur_index, typename GT::Arc *deviation_arc, typename GT::Node *deviation_next_node, const Path_State< GT, Cost_Type > &suffix_state)
 
template<class GT , class Distance , class SA , typename Cost_Type >
void generate_general_deviation_candidates (const GT &g, const Path_State< GT, Cost_Type > &base_path, typename GT::Node *target, const Suffix_Index< GT, Cost_Type > &suffix_index, Distance distance, SA sa, const Array< Path_State< GT, Cost_Type > > &accepted, Array< Path_State< GT, Cost_Type > > &candidates)
 

Function Documentation

◆ build_suffix_index()

template<class GT , class Distance , class SA >
Suffix_Index< GT, typename Distance::Distance_Type > Aleph::k_shortest_paths_detail::build_suffix_index ( const GT &  g,
typename GT::Node *  target,
Distance  distance,
SA  sa 
)

Definition at line 595 of file K_Shortest_Paths.H.

References Aleph::divide_and_conquer_partition_dp(), and GraphCommon< GT, Node, Arc >::is_digraph().

◆ build_suffix_index_digraph()

template<class GT , class Distance , class SA >
Suffix_Index< GT, typename Distance::Distance_Type > Aleph::k_shortest_paths_detail::build_suffix_index_digraph ( const GT &  g,
typename GT::Node *  target,
Distance  distance,
SA  sa 
)

Definition at line 474 of file K_Shortest_Paths.H.

References Aleph::shortest_path_detail::checked_add(), Aleph::diff(), Aleph::k_shortest_paths_detail::Suffix_Index< GT, Cost_Type >::dist_to_target, Aleph::divide_and_conquer_partition_dp(), Aleph::DynMapTree< Key, Data, Tree, Compare >::find(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::k_shortest_paths_detail::Suffix_Index< GT, Cost_Type >::inf, Aleph::DynMapTree< Key, Data, Tree, Compare >::insert(), IS_NODE_VISITED, Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), NODE_COOKIE, Aleph::Spanning_Tree, Aleph::k_shortest_paths_detail::Suffix_Index< GT, Cost_Type >::tree_arc, and Aleph::k_shortest_paths_detail::Suffix_Index< GT, Cost_Type >::tree_next.

◆ build_suffix_index_with_itor()

template<template< class, class > class Itor, class GT , class Distance , class SA >
Suffix_Index< GT, typename Distance::Distance_Type > Aleph::k_shortest_paths_detail::build_suffix_index_with_itor ( const GT &  g,
typename GT::Node *  target,
Distance  distance,
SA  sa 
)

Definition at line 388 of file K_Shortest_Paths.H.

References Aleph::and, Aleph::shortest_path_detail::checked_add(), Aleph::diff(), Aleph::k_shortest_paths_detail::Suffix_Index< GT, Cost_Type >::dist_to_target, Aleph::divide_and_conquer_partition_dp(), Aleph::DynMapTree< Key, Data, Tree, Compare >::find(), Aleph::k_shortest_paths_detail::Suffix_Index< GT, Cost_Type >::inf, Aleph::DynMapTree< Key, Data, Tree, Compare >::insert(), IS_ARC_VISITED, IS_NODE_VISITED, Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), NODE_COOKIE, Aleph::Spanning_Tree, Aleph::k_shortest_paths_detail::Suffix_Index< GT, Cost_Type >::tree_arc, and Aleph::k_shortest_paths_detail::Suffix_Index< GT, Cost_Type >::tree_next.

◆ build_suffix_state()

template<class GT , typename Cost_Type >
bool Aleph::k_shortest_paths_detail::build_suffix_state ( const GT &  g,
const Suffix_Index< GT, Cost_Type > &  index,
typename GT::Node *  start,
typename GT::Node *  target,
Path_State< GT, Cost_Type > &  out_suffix 
)

Definition at line 610 of file K_Shortest_Paths.H.

References Aleph::divide_and_conquer_partition_dp(), get_dist_to_target(), GraphCommon< GT, Node, Arc >::get_num_nodes(), get_tree_arc(), get_tree_next(), Aleph::k_shortest_paths_detail::Suffix_Index< GT, Cost_Type >::inf, and Aleph::next().

Referenced by generate_general_deviation_candidates().

◆ compose_candidate()

template<class GT , typename Cost_Type >
Path_State< GT, Cost_Type > Aleph::k_shortest_paths_detail::compose_candidate ( const Path_Snapshot< GT, Cost_Type > &  base_path,
const size_t  spur_index,
const Path_State< GT, Cost_Type > &  spur_state 
)

Definition at line 704 of file K_Shortest_Paths.H.

References Aleph::DynList< T >::append(), Aleph::Dlink::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::HTList::Iterator::has_curr(), and Aleph::k_shortest_paths_detail::Path_State< GT, Cost_Type >::nodes.

Referenced by Aleph::yen_k_shortest_paths().

◆ compose_general_candidate()

template<class GT , typename Cost_Type >
Path_State< GT, Cost_Type > Aleph::k_shortest_paths_detail::compose_general_candidate ( const Path_Snapshot< GT, Cost_Type > &  base_path,
const size_t  spur_index,
typename GT::Arc *  deviation_arc,
typename GT::Node *  deviation_next_node,
const Path_State< GT, Cost_Type > &  suffix_state 
)

Definition at line 739 of file K_Shortest_Paths.H.

References Aleph::DynList< T >::append(), Aleph::Dlink::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::HTList::Iterator::has_curr(), and Aleph::k_shortest_paths_detail::Path_State< GT, Cost_Type >::nodes.

◆ compute_cost_from_arcs()

template<class GT , class Distance >
Distance::Distance_Type Aleph::k_shortest_paths_detail::compute_cost_from_arcs ( const DynList< typename GT::Arc * > &  arcs,
Distance  distance 
)

Definition at line 689 of file K_Shortest_Paths.H.

References arcs, Aleph::shortest_path_detail::checked_add(), Aleph::divide_and_conquer_partition_dp(), and Aleph::HTList::Iterator::has_curr().

◆ contains_path()

template<class GT , typename Cost_Type >
bool Aleph::k_shortest_paths_detail::contains_path ( const Array< Path_State< GT, Cost_Type > > &  container,
const Path_State< GT, Cost_Type > &  candidate 
)

Definition at line 343 of file K_Shortest_Paths.H.

References Aleph::divide_and_conquer_partition_dp(), and same_path_sequence().

Referenced by Aleph::eppstein_k_shortest_paths(), generate_general_deviation_candidates(), and Aleph::yen_k_shortest_paths().

◆ generate_general_deviation_candidates()

template<class GT , class Distance , class SA , typename Cost_Type >
void Aleph::k_shortest_paths_detail::generate_general_deviation_candidates ( const GT &  g,
const Path_State< GT, Cost_Type > &  base_path,
typename GT::Node *  target,
const Suffix_Index< GT, Cost_Type > &  suffix_index,
Distance  distance,
SA  sa,
const Array< Path_State< GT, Cost_Type > > &  accepted,
Array< Path_State< GT, Cost_Type > > &  candidates 
)

Definition at line 778 of file K_Shortest_Paths.H.

References Aleph::and, build_suffix_state(), Aleph::shortest_path_detail::checked_add(), contains_path(), Aleph::divide_and_conquer_partition_dp(), get_dist_to_target(), Aleph::k_shortest_paths_detail::Suffix_Index< GT, Cost_Type >::inf, and Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne().

◆ get_dist_to_target()

template<class GT , typename Cost_Type >
Cost_Type Aleph::k_shortest_paths_detail::get_dist_to_target ( const Suffix_Index< GT, Cost_Type > &  index,
typename GT::Node *  node 
)

Definition at line 355 of file K_Shortest_Paths.H.

References Aleph::k_shortest_paths_detail::Suffix_Index< GT, Cost_Type >::dist_to_target, Aleph::k_shortest_paths_detail::Suffix_Index< GT, Cost_Type >::inf, and Aleph::DynMapTree< Key, Data, Tree, Compare >::search().

Referenced by build_suffix_state(), and generate_general_deviation_candidates().

◆ get_tree_arc()

template<class GT , typename Cost_Type >
GT::Arc * Aleph::k_shortest_paths_detail::get_tree_arc ( const Suffix_Index< GT, Cost_Type > &  index,
typename GT::Node *  node 
)

Definition at line 377 of file K_Shortest_Paths.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::DynMapTree< Key, Data, Tree, Compare >::search(), and Aleph::k_shortest_paths_detail::Suffix_Index< GT, Cost_Type >::tree_arc.

Referenced by build_suffix_state().

◆ get_tree_next()

template<class GT , typename Cost_Type >
GT::Node * Aleph::k_shortest_paths_detail::get_tree_next ( const Suffix_Index< GT, Cost_Type > &  index,
typename GT::Node *  node 
)

Definition at line 367 of file K_Shortest_Paths.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::DynMapTree< Key, Data, Tree, Compare >::search(), and Aleph::k_shortest_paths_detail::Suffix_Index< GT, Cost_Type >::tree_next.

Referenced by build_suffix_state().

◆ make_path_snapshot()

template<class GT , typename Cost_Type >
Path_Snapshot< GT, Cost_Type > Aleph::k_shortest_paths_detail::make_path_snapshot ( const Path_State< GT, Cost_Type > &  path)

Definition at line 227 of file K_Shortest_Paths.H.

References Aleph::Array< T >::append(), Aleph::k_shortest_paths_detail::Path_State< GT, Cost_Type >::arcs, Aleph::k_shortest_paths_detail::Path_Snapshot< GT, Cost_Type >::arcs, LocateFunctions< Container, Type >::get_it(), Aleph::k_shortest_paths_detail::Path_State< GT, Cost_Type >::nodes, Aleph::k_shortest_paths_detail::Path_Snapshot< GT, Cost_Type >::nodes, Aleph::Array< T >::reserve(), and Aleph::HTList::size().

◆ path_to_state()

template<class GT , typename Cost_Type >
Path_State< GT, Cost_Type > Aleph::k_shortest_paths_detail::path_to_state ( const Path< GT > &  path,
const Cost_Type  total_cost 
)

Definition at line 245 of file K_Shortest_Paths.H.

References Aleph::DynList< T >::append(), Aleph::k_shortest_paths_detail::Path_State< GT, Cost_Type >::arcs, Aleph::Path< GT >::Iterator::has_current_node(), Aleph::k_shortest_paths_detail::Path_State< GT, Cost_Type >::nodes, and Aleph::k_shortest_paths_detail::Path_State< GT, Cost_Type >::total_cost.

◆ same_path_sequence()

template<class GT , typename Cost_Type >
bool Aleph::k_shortest_paths_detail::same_path_sequence ( const Path_State< GT, Cost_Type > &  a,
const Path_State< GT, Cost_Type > &  b 
)

Definition at line 288 of file K_Shortest_Paths.H.

References Aleph::k_shortest_paths_detail::Path_State< GT, Cost_Type >::arcs, Aleph::divide_and_conquer_partition_dp(), LocateFunctions< Container, Type >::get_it(), Aleph::k_shortest_paths_detail::Path_State< GT, Cost_Type >::nodes, and Aleph::HTList::size().

Referenced by contains_path().

◆ same_prefix_nodes()

template<class GT , typename Cost_Type >
bool Aleph::k_shortest_paths_detail::same_prefix_nodes ( const Path_Snapshot< GT, Cost_Type > &  a,
const Path_Snapshot< GT, Cost_Type > &  b,
const size_t  spur_index 
)

Definition at line 321 of file K_Shortest_Paths.H.

References Aleph::k_shortest_paths_detail::Path_Snapshot< GT, Cost_Type >::arcs, Aleph::divide_and_conquer_partition_dp(), Aleph::k_shortest_paths_detail::Path_Snapshot< GT, Cost_Type >::nodes, and Aleph::Array< T >::size().

Referenced by Aleph::yen_k_shortest_paths().

◆ shortest_path_filtered()

template<class GT , class Distance , class SA >
bool Aleph::k_shortest_paths_detail::shortest_path_filtered ( const GT &  g,
typename GT::Node *  source,
typename GT::Node *  target,
Distance  distance,
SA  sa,
const DynSetTree< typename GT::Node * > *  forbidden_nodes,
const DynSetTree< typename GT::Arc * > *  forbidden_arcs,
Path_State< GT, typename Distance::Distance_Type > &  out 
)

Definition at line 646 of file K_Shortest_Paths.H.

References Aleph::and, Aleph::DynSetTree< Key, Tree, Compare >::contains(), Aleph::divide_and_conquer_partition_dp(), and Aleph::filter().

◆ state_to_path()

template<class GT , typename Cost_Type >
Path< GT > Aleph::k_shortest_paths_detail::state_to_path ( const GT &  g,
const Path_State< GT, Cost_Type > &  state 
)

Definition at line 262 of file K_Shortest_Paths.H.

References Aleph::Path< GT >::append(), Aleph::Path< GT >::append_directed(), Aleph::k_shortest_paths_detail::Path_State< GT, Cost_Type >::arcs, Aleph::DynList< T >::get_first(), Aleph::HTList::Iterator::has_curr(), GraphCommon< GT, Node, Arc >::is_digraph(), Aleph::HTList::is_empty(), Aleph::k_shortest_paths_detail::Path_State< GT, Cost_Type >::nodes, and Aleph::Path< GT >::set_graph().

Referenced by Aleph::eppstein_k_shortest_paths(), and Aleph::yen_k_shortest_paths().

◆ validate_non_negative_weights()

template<class GT , class Distance , class SA >
void Aleph::k_shortest_paths_detail::validate_non_negative_weights ( const GT &  g,
Distance  distance,
SA  sa 
)

Definition at line 192 of file K_Shortest_Paths.H.

References ah_domain_error_if, Aleph::divide_and_conquer_partition_dp(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), and w.

Referenced by Aleph::eppstein_k_shortest_paths(), and Aleph::yen_k_shortest_paths().