Common utilities and base class for shortest path algorithms. More...

#include <limits>
#include <type_traits>
#include <ah-errors.H>
#include <tpl_graph.H>
#include <tpl_find_path.H>

Include dependency graph for shortest_path_common.H:

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

Go to the source code of this file.

Classes
class	Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >
	Base class providing common infrastructure for shortest path algorithms. More...

struct	Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::Arc_Info
	Information stored in arc cookies for painting version. More...

struct	Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::Tree_Arc_Info
	Extended arc info with tree arc mapping. More...

struct	Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::Node_Info
	Information stored in node cookies for painting version. More...

struct	Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::Tree_Node_Info
	Extended node info with tree node mapping. More...

struct	Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::Heap_Info
	Functor to access heap node handle from node cookie. More...

struct	Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::Get_Potential_Arc
	Functor to get arc potential for heap ordering. More...

struct	Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::Initialize_Node
	Node initialization for painting version. More...

struct	Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::Initialize_Arc
	Arc initialization for painting version. More...

struct	Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::Initialize_Tree_Node
	Node initialization for tree-building version. More...

struct	Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::Initialize_Tree_Arc
	Arc initialization for tree-building version. More...

struct	Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::Destroy_Node
	Node cleanup for painting version. More...

struct	Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::Destroy_Arc
	Arc cleanup for painting version. More...

struct	Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::Destroy_Tree_Node
	Node cleanup and mapping for tree-building version. More...

struct	Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::Destroy_Tree_Arc
	Arc cleanup and mapping for tree-building version. More...

struct	Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::Total
	Distance totalizer class for path copying. More...

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

namespace	Aleph::shortest_path_detail
	Namespace for shortest path algorithm implementation details.

Macros
#define	SP_NODE_INFO(p) (static_cast<typename Shortest_Path_Base::Node_Info*>(NODE_COOKIE(p)))
	Convert node cookie to Node_Info pointer.

#define	SP_TREE_NODE_INFO(p) (static_cast<typename Shortest_Path_Base::Tree_Node_Info*>(NODE_COOKIE(p)))
	Convert node cookie to Tree_Node_Info pointer.

#define	SP_ACC(p) (SP_NODE_INFO(p)->dist)
	Access accumulated distance from node cookie.

#define	SP_HEAPNODE(p) (SP_NODE_INFO(p)->heap_node)
	Access heap node handle from node cookie.

#define	SP_PARENT(p) (SP_NODE_INFO(p)->ret_node)
	Access parent pointer from node cookie.

#define	SP_TREENODE(p) (SP_TREE_NODE_INFO(p)->tree_node)
	Access tree node mapping from node cookie.

#define	SP_ARC_INFO(p) (static_cast<typename Shortest_Path_Base::Arc_Info*>(ARC_COOKIE(p)))
	Convert arc cookie to Arc_Info pointer.

#define	SP_TREE_ARC_INFO(p) (static_cast<typename Shortest_Path_Base::Tree_Arc_Info*>(ARC_COOKIE(p)))
	Convert arc cookie to Tree_Arc_Info pointer.

#define	SP_POT(p) (SP_ARC_INFO(p)->pot)
	Access arc potential from arc cookie.

#define	SP_TREEARC(p) (SP_TREE_ARC_INFO(p)->tree_arc)
	Access tree arc mapping from arc cookie.

#define	SP_ARC_DIST(p) (Distance()(p))
	Get arc distance using Distance functor.

Functions
template<typename T >
T	Aleph::shortest_path_detail::checked_add (const T &a, const T &b)
	Safely add two distance values with overflow checking.

Detailed Description

Common utilities and base class for shortest path algorithms.

This file contains shared functionality used by Dijkstra's algorithm, A*, and other shortest path algorithms. It provides:

Overflow-checked arithmetic operations
Common cookie structures for node/arc information
Initialize/Destroy functors for cookie management
Base class with common algorithm infrastructure

Author: Leandro Rabindranath León

Definition in file shortest_path_common.H.

Macro Definition Documentation

◆ SP_ACC

#define SP_ACC ( p ) (SP_NODE_INFO(p)->dist)

Access accumulated distance from node cookie.

Definition at line 73 of file shortest_path_common.H.

◆ SP_ARC_DIST

#define SP_ARC_DIST ( p ) (Distance()(p))

Get arc distance using Distance functor.

Definition at line 97 of file shortest_path_common.H.

◆ SP_ARC_INFO

#define SP_ARC_INFO ( p ) (static_cast<typename Shortest_Path_Base::Arc_Info*>(ARC_COOKIE(p)))

Convert arc cookie to Arc_Info pointer.

Definition at line 85 of file shortest_path_common.H.

◆ SP_HEAPNODE

#define SP_HEAPNODE ( p ) (SP_NODE_INFO(p)->heap_node)

Access heap node handle from node cookie.

Definition at line 76 of file shortest_path_common.H.

◆ SP_NODE_INFO

#define SP_NODE_INFO ( p ) (static_cast<typename Shortest_Path_Base::Node_Info*>(NODE_COOKIE(p)))

Convert node cookie to Node_Info pointer.

Definition at line 67 of file shortest_path_common.H.

◆ SP_PARENT

#define SP_PARENT ( p ) (SP_NODE_INFO(p)->ret_node)

Access parent pointer from node cookie.

Definition at line 79 of file shortest_path_common.H.

◆ SP_POT

#define SP_POT ( p ) (SP_ARC_INFO(p)->pot)

Access arc potential from arc cookie.

Definition at line 91 of file shortest_path_common.H.

◆ SP_TREE_ARC_INFO

#define SP_TREE_ARC_INFO ( p ) (static_cast<typename Shortest_Path_Base::Tree_Arc_Info*>(ARC_COOKIE(p)))

Convert arc cookie to Tree_Arc_Info pointer.

Definition at line 88 of file shortest_path_common.H.

◆ SP_TREE_NODE_INFO

#define SP_TREE_NODE_INFO ( p ) (static_cast<typename Shortest_Path_Base::Tree_Node_Info*>(NODE_COOKIE(p)))

Convert node cookie to Tree_Node_Info pointer.

Definition at line 70 of file shortest_path_common.H.

◆ SP_TREEARC

#define SP_TREEARC ( p ) (SP_TREE_ARC_INFO(p)->tree_arc)

Access tree arc mapping from arc cookie.

Definition at line 94 of file shortest_path_common.H.

◆ SP_TREENODE

#define SP_TREENODE ( p ) (SP_TREE_NODE_INFO(p)->tree_node)

Access tree node mapping from node cookie.

Definition at line 82 of file shortest_path_common.H.

Classes

Namespaces

Macros

Functions