K_Shortest_Paths.H File Reference

K-shortest path algorithms (Yen and Eppstein-style API). More...

#include <cmath>
#include <cstddef>
#include <limits>
#include <type_traits>
#include <utility>
#include <Dijkstra.H>
#include <ah-errors.H>
#include <cookie_guard.H>
#include <shortest_path_common.H>
#include <htlist.H>
#include <tpl_array.H>
#include <tpl_dynMapTree.H>
#include <tpl_dynSetTree.H>

Include dependency graph for K_Shortest_Paths.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	Aleph::K_Shortest_Path_Item< GT, Cost_Type >
	A shortest-path item returned by k-shortest algorithms. More...
struct	Aleph::k_shortest_paths_detail::Path_State< GT, Cost_Type >
struct	Aleph::k_shortest_paths_detail::Suffix_Index< GT, Cost_Type >
struct	Aleph::k_shortest_paths_detail::Filtered_Show_Arc< GT, SA >
struct	Aleph::k_shortest_paths_detail::Reverse_Arc_Distance< GT, Distance >
struct	Aleph::k_shortest_paths_detail::Path_Snapshot< GT, Cost_Type >
class	Aleph::Yen_K_Shortest_Paths< GT, Distance, SA >
	Functor wrapper for Yen's k-shortest loopless paths algorithm. More...
class	Aleph::Eppstein_K_Shortest_Paths< GT, Distance, SA >
	Functor wrapper for Eppstein-style k-shortest paths API. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.
namespace	Aleph::k_shortest_paths_detail

Functions
template<class GT , class Distance , class SA >
void	Aleph::k_shortest_paths_detail::validate_non_negative_weights (const GT &g, Distance distance, SA sa)
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)
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)
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)
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)
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)
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)
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)
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)
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)
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)
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)
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)
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)
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)
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)
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)
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)
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)
template<class GT , class Distance = Dft_Dist<GT>, class SA = Dft_Show_Arc<GT>>
DynList< K_Shortest_Path_Item< GT, typename Distance::Distance_Type > >	Aleph::yen_k_shortest_paths (const GT &g, typename GT::Node *source, typename GT::Node *target, const size_t k, Distance distance=Distance(), SA sa=SA())
	Compute k shortest loopless paths using Yen's algorithm.
template<class GT , class Distance = Dft_Dist<GT>, class SA = Dft_Show_Arc<GT>>
DynList< K_Shortest_Path_Item< GT, typename Distance::Distance_Type > >	Aleph::eppstein_k_shortest_paths (const GT &g, typename GT::Node *source, typename GT::Node *target, const size_t k, Distance distance=Distance(), SA sa=SA())
	Compute k shortest general (loopy) paths.

Detailed Description

K-shortest path algorithms (Yen and Eppstein-style API).

This header provides two k-shortest path modes over Aleph graphs.

• yen_k_shortest_paths(...): Yen's algorithm for loopless paths.
• eppstein_k_shortest_paths(...): General (non-loopless) k-shortest API based on deviation expansion over shortest suffixes.

Problem solved

Given graph \(G=(V,E)\), source \(s\), target \(t\), and integer \(k\), compute:

• Yen: the first \(k\) shortest simple (loopless) paths.
• Eppstein-style API: the first \(k\) shortest general paths (cycles may appear).

Assumptions

• Non-negative arc weights (validated at runtime).
• Works with Aleph graph backends (List_Graph, List_Digraph, List_SGraph, Array_Graph, etc.) through generic graph interfaces.

See also

Dijkstra.H For single-source shortest paths

Johnson.H For all-pairs shortest paths on sparse graphs

Definition in file K_Shortest_Paths.H.