Johnson's algorithm for all-pairs shortest paths. More...

#include <Johnson.H>

Collaboration diagram for Aleph::Johnson< GT, Distance, Ait, NAit, SA >:

Classes
struct	Reweighted_Dist

Public Types
using	Node = typename GT::Node

using	Arc = typename GT::Arc

using	Distance_Type = typename Distance::Distance_Type

Public Member Functions
	Johnson (const GT &g, Distance d=Distance(), SA __sa=SA())
	Construct a Johnson's all-pairs shortest paths executor.

	Johnson ()=default
	Default constructor (uninitialized state)

bool	is_initialized () const noexcept
	Check if the algorithm has been initialized.

Distance_Type	get_distance (Node src, Node tgt)
	Get the shortest distance from source to target.

Path< GT >	find_path (Node src, Node tgt)
	Find the shortest path from source to target.

DynMapTree< std::pair< Node , Node >, Distance_Type >	compute_all_pairs_distances ()
	Compute the shortest distance for all pairs.

Distance_Type	get_potential (Node *node) const
	Get the node potential (h value) for a node.

GT &	get_reweighted_graph () noexcept
	Get access to the internal reweighted graph.

const GT &	get_reweighted_graph () const noexcept
	Get const access to the internal reweighted graph.

Node *	get_copy_node (Node *orig) const
	Get the copy of a node in the reweighted graph.

Private Member Functions
void	reweight_arcs ()
	Reweight all arcs using node potentials.

void	build_reverse_mappings (const GT &orig)

Path< GT >	map_copy_path_to_original (const Path< GT > &copy_path) const

Static Private Member Functions
static Distance_Type	checked_add (const Distance_Type &a, const Distance_Type &b)

static Distance_Type	checked_sub (const Distance_Type &a, const Distance_Type &b)

Private Attributes
const GT *	orig_graph = nullptr

GraphCopyWithMapping< GT >	graph_copy
	Copy of graph with node mapping.

DynMapTree< Node , Node >	copy_to_orig_node

DynMapTree< Arc , Arc >	copy_to_orig_arc

DynMapTree< Node *, Distance_Type >	h
	Node potentials from Bellman-Ford.

Distance	dist

SA	sa

bool	initialized = false

Detailed Description

template<class GT, class Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>
class Aleph::Johnson< GT, Distance, Ait, NAit, SA >

Johnson's algorithm for all-pairs shortest paths.

This class implements Johnson's algorithm for computing shortest paths between all pairs of vertices in a weighted directed graph. It handles graphs with negative edge weights (but not negative cycles).

The algorithm is efficient for sparse graphs, with complexity O(V² log V + VE), compared to Floyd-Warshall's O(V³).

Template Parameters

GT	Graph type (typically List_Digraph).
Distance	Arc weight accessor class. Must provide: `Distance_Type`: The numeric type for weights `operator()(Arc*)`: Returns the weight of an arc
Ait	Arc iterator template for traversing all arcs.
NAit	Node arc iterator template for outgoing arcs.
SA	Arc filter for internal iterators.

Usage example:

List_Digraph<Node, Arc> g;
// ... build graph with possibly negative edges ...
 
try {
  Johnson<List_Digraph<Node, Arc>> johnson(g);
  
  // Query shortest path between any pair
  auto path = johnson.find_path(src, tgt);
  auto dist = johnson.get_distance(src, tgt);
}
catch (const std::domain_error& e) {
  // Graph has a negative cycle
}

Warning: The graph must be a digraph. For undirected graphs, convert to digraph first (each edge becomes two arcs).

See also: Bellman_Ford Dijkstra_Min_Paths Floyd_All_Shortest_Paths

Definition at line 124 of file Johnson.H.

Member Typedef Documentation

◆ Arc

template<class GT , class Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

using Aleph::Johnson< GT, Distance, Ait, NAit, SA >::Arc = typename GT::Arc

Definition at line 128 of file Johnson.H.

◆ Distance_Type

template<class GT , class Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

using Aleph::Johnson< GT, Distance, Ait, NAit, SA >::Distance_Type = typename Distance::Distance_Type

Definition at line 129 of file Johnson.H.

◆ Node

template<class GT , class Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

using Aleph::Johnson< GT, Distance, Ait, NAit, SA >::Node = typename GT::Node

Definition at line 127 of file Johnson.H.

Constructor & Destructor Documentation

◆ Johnson() [1/2]

template<class GT , class Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

Aleph::Johnson< GT, Distance, Ait, NAit, SA >::Johnson	(	const GT &	g,
		Distance	d = `Distance()`,
		SA	__sa = `SA()`
	)

inlineexplicit

Construct a Johnson's all-pairs shortest paths executor.

The constructor:

Copies the input graph (preserving node mapping)
Runs Bellman-Ford to compute node potentials
Reweights all edges to be non-negative

Parameters

[in]	g	The graph to operate on.
[in]	d	Arc-weight accessor (default constructed).
[in]	__sa	Arc filter for internal iterators (default constructed).

Exceptions

std::bad_alloc	if there is not enough memory.
std::domain_error	if a negative cycle is detected.

Definition at line 287 of file Johnson.H.

References Aleph::Johnson< GT, Distance, Ait, NAit, SA >::build_reverse_mappings(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::dist, Aleph::Johnson< GT, Distance, Ait, NAit, SA >::graph_copy, Aleph::Johnson< GT, Distance, Ait, NAit, SA >::h, Aleph::Johnson< GT, Distance, Ait, NAit, SA >::initialized, Aleph::maps(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::reweight_arcs(), and Aleph::Johnson< GT, Distance, Ait, NAit, SA >::sa.

◆ Johnson() [2/2]

template<class GT , class Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

Aleph::Johnson< GT, Distance, Ait, NAit, SA >::Johnson ( )

default

Default constructor (uninitialized state)

Member Function Documentation

◆ build_reverse_mappings()

template<class GT , class Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

void Aleph::Johnson< GT, Distance, Ait, NAit, SA >::build_reverse_mappings ( const GT & orig )

inlineprivate

Definition at line 203 of file Johnson.H.

References ah_domain_error_if, Aleph::DynList< T >::append(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::copy_to_orig_arc, Aleph::Johnson< GT, Distance, Ait, NAit, SA >::copy_to_orig_node, Aleph::DynSetTree< Key, Tree, Compare >::empty(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::graph_copy, Aleph::DynMapTree< Key, Data, Tree, Compare >::insert(), Aleph::HTList::is_empty(), Aleph::maps(), Aleph::DynList< T >::remove_first(), and Aleph::DynSetTree< Key, Tree, Compare >::size().

Referenced by Aleph::Johnson< GT, Distance, Ait, NAit, SA >::Johnson().

◆ checked_add()

template<class GT , class Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

static Distance_Type Aleph::Johnson< GT, Distance, Ait, NAit, SA >::checked_add	(	const Distance_Type &	a,
		const Distance_Type &	b
	)

inlinestaticprivate

Definition at line 154 of file Johnson.H.

References Aleph::shortest_path_detail::checked_add().

Referenced by Aleph::Johnson< GT, Distance, Ait, NAit, SA >::reweight_arcs().

◆ checked_sub()

template<class GT , class Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

static Distance_Type Aleph::Johnson< GT, Distance, Ait, NAit, SA >::checked_sub	(	const Distance_Type &	a,
		const Distance_Type &	b
	)

inlinestaticprivate

Definition at line 159 of file Johnson.H.

References ah_overflow_error_if, and Aleph::maps().

Referenced by Aleph::Johnson< GT, Distance, Ait, NAit, SA >::reweight_arcs().

◆ compute_all_pairs_distances()

template<class GT , class Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

DynMapTree< std::pair< Node *, Node * >, Distance_Type > Aleph::Johnson< GT, Distance, Ait, NAit, SA >::compute_all_pairs_distances ( )

inline

Compute the shortest distance for all pairs.

Returns: A map where key is (src, tgt) pair and value is shortest distance.

Exceptions

std::domain_error if not initialized.

Definition at line 391 of file Johnson.H.

References ah_domain_error_if, Aleph::DynMapTree< Key, Data, Tree, Compare >::find(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::graph_copy, Aleph::Johnson< GT, Distance, Ait, NAit, SA >::h, Aleph::Johnson< GT, Distance, Ait, NAit, SA >::initialized, Aleph::DynMapTree< Key, Data, Tree, Compare >::insert(), IS_NODE_VISITED, Aleph::maps(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::sa, and Aleph::Spanning_Tree.

◆ find_path()

template<class GT , class Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

Path< GT > Aleph::Johnson< GT, Distance, Ait, NAit, SA >::find_path	(	Node *	src,
		Node *	tgt
	)

inline

Find the shortest path from source to target.

Parameters

[in]	src	Source node (from original graph).
[in]	tgt	Target node (from original graph).

Returns: Path in the original graph from src to tgt, or an empty path if unreachable.

Exceptions

std::domain_error if not initialized or nodes not found.

Definition at line 360 of file Johnson.H.

References ah_domain_error_if, Aleph::Johnson< GT, Distance, Ait, NAit, SA >::graph_copy, Aleph::Johnson< GT, Distance, Ait, NAit, SA >::initialized, IS_NODE_VISITED, Aleph::Johnson< GT, Distance, Ait, NAit, SA >::map_copy_path_to_original(), Aleph::maps(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::orig_graph, Aleph::Johnson< GT, Distance, Ait, NAit, SA >::sa, and Aleph::Spanning_Tree.

◆ get_copy_node()

template<class GT , class Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

Node * Aleph::Johnson< GT, Distance, Ait, NAit, SA >::get_copy_node ( Node * orig ) const

inline

Get the copy of a node in the reweighted graph.

Parameters

[in] orig Original node.

Returns: Corresponding node in the reweighted graph.

Definition at line 459 of file Johnson.H.

References Aleph::Johnson< GT, Distance, Ait, NAit, SA >::graph_copy, and Aleph::maps().

◆ get_distance()

template<class GT , class Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

Distance_Type Aleph::Johnson< GT, Distance, Ait, NAit, SA >::get_distance	(	Node *	src,
		Node *	tgt
	)

inline

Get the shortest distance from source to target.

Parameters

[in]	src	Source node (from original graph).
[in]	tgt	Target node (from original graph).

Returns: The shortest distance from src to tgt, or infinity if unreachable.

Exceptions

std::domain_error if not initialized or nodes not found.

Definition at line 320 of file Johnson.H.

References ah_domain_error_if, Aleph::DynMapTree< Key, Data, Tree, Compare >::find(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::graph_copy, Aleph::Johnson< GT, Distance, Ait, NAit, SA >::h, Aleph::Johnson< GT, Distance, Ait, NAit, SA >::initialized, IS_NODE_VISITED, Aleph::maps(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::sa, and Aleph::Spanning_Tree.

◆ get_potential()

template<class GT , class Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

Distance_Type Aleph::Johnson< GT, Distance, Ait, NAit, SA >::get_potential ( Node * node ) const

inline

Get the node potential (h value) for a node.

The potential h(v) represents the shortest distance from the dummy source to v, computed by Bellman-Ford.

Parameters

[in] node Node from the original graph.

Returns: The potential h(node).

Exceptions

std::domain_error if not initialized or node not found.

Definition at line 435 of file Johnson.H.

References ah_domain_error_if, Aleph::DynMapTree< Key, Data, Tree, Compare >::find(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::graph_copy, Aleph::Johnson< GT, Distance, Ait, NAit, SA >::h, Aleph::Johnson< GT, Distance, Ait, NAit, SA >::initialized, and Aleph::maps().

◆ get_reweighted_graph() [1/2]

template<class GT , class Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

const GT & Aleph::Johnson< GT, Distance, Ait, NAit, SA >::get_reweighted_graph ( ) const

inlinenoexcept

Get const access to the internal reweighted graph.

Definition at line 452 of file Johnson.H.

References Aleph::Johnson< GT, Distance, Ait, NAit, SA >::graph_copy.

◆ get_reweighted_graph() [2/2]

template<class GT , class Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

GT & Aleph::Johnson< GT, Distance, Ait, NAit, SA >::get_reweighted_graph ( )

inlinenoexcept

Get access to the internal reweighted graph.

Useful for debugging or advanced operations.

Returns: Reference to the internal graph copy.

Definition at line 448 of file Johnson.H.

References Aleph::Johnson< GT, Distance, Ait, NAit, SA >::graph_copy.

◆ is_initialized()

template<class GT , class Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

bool Aleph::Johnson< GT, Distance, Ait, NAit, SA >::is_initialized ( ) const

inlinenoexcept

Check if the algorithm has been initialized.

Returns: true if ready for queries, false otherwise.

Definition at line 311 of file Johnson.H.

References Aleph::Johnson< GT, Distance, Ait, NAit, SA >::initialized.

◆ map_copy_path_to_original()

template<class GT , class Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

Path< GT > Aleph::Johnson< GT, Distance, Ait, NAit, SA >::map_copy_path_to_original ( const Path< GT > & copy_path ) const

inlineprivate

Definition at line 244 of file Johnson.H.

References ah_domain_error_if, Aleph::DynList< T >::append(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::copy_to_orig_arc, Aleph::Johnson< GT, Distance, Ait, NAit, SA >::copy_to_orig_node, LocateFunctions< Container, Type >::get_it(), Aleph::HTList::is_empty(), Aleph::maps(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::orig_graph, and Aleph::DynMapTree< Key, Data, Tree, Compare >::search().

Referenced by Aleph::Johnson< GT, Distance, Ait, NAit, SA >::find_path().

◆ reweight_arcs()

template<class GT , class Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

void Aleph::Johnson< GT, Distance, Ait, NAit, SA >::reweight_arcs ( )

inlineprivate

Reweight all arcs using node potentials.

New weight: w'(u,v) = w(u,v) + h(u) - h(v) This guarantees all weights are non-negative.

Definition at line 180 of file Johnson.H.

References Aleph::Johnson< GT, Distance, Ait, NAit, SA >::checked_add(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::checked_sub(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::copy_to_orig_arc, Aleph::Johnson< GT, Distance, Ait, NAit, SA >::dist, Aleph::DynMapTree< Key, Data, Tree, Compare >::find(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::graph_copy, Aleph::Johnson< GT, Distance, Ait, NAit, SA >::h, Aleph::maps(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::sa, Aleph::DynMapTree< Key, Data, Tree, Compare >::search(), and w.

Referenced by Aleph::Johnson< GT, Distance, Ait, NAit, SA >::Johnson().

Member Data Documentation

◆ copy_to_orig_arc

template<class GT , class Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

DynMapTree<Arc*, Arc*> Aleph::Johnson< GT, Distance, Ait, NAit, SA >::copy_to_orig_arc

private

Definition at line 135 of file Johnson.H.

Referenced by Aleph::Johnson< GT, Distance, Ait, NAit, SA >::build_reverse_mappings(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::map_copy_path_to_original(), and Aleph::Johnson< GT, Distance, Ait, NAit, SA >::reweight_arcs().

◆ copy_to_orig_node

template<class GT , class Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

DynMapTree<Node*, Node*> Aleph::Johnson< GT, Distance, Ait, NAit, SA >::copy_to_orig_node

private

Definition at line 134 of file Johnson.H.

Referenced by Aleph::Johnson< GT, Distance, Ait, NAit, SA >::build_reverse_mappings(), and Aleph::Johnson< GT, Distance, Ait, NAit, SA >::map_copy_path_to_original().

◆ dist

template<class GT , class Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

Distance Aleph::Johnson< GT, Distance, Ait, NAit, SA >::dist

private

Definition at line 137 of file Johnson.H.

Referenced by Aleph::Johnson< GT, Distance, Ait, NAit, SA >::Johnson(), and Aleph::Johnson< GT, Distance, Ait, NAit, SA >::reweight_arcs().

◆ graph_copy

template<class GT , class Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

GraphCopyWithMapping<GT> Aleph::Johnson< GT, Distance, Ait, NAit, SA >::graph_copy

private

Copy of graph with node mapping.

Definition at line 133 of file Johnson.H.

◆ h

template<class GT , class Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

DynMapTree<Node*, Distance_Type> Aleph::Johnson< GT, Distance, Ait, NAit, SA >::h

private

Node potentials from Bellman-Ford.

Definition at line 136 of file Johnson.H.

Referenced by Aleph::Johnson< GT, Distance, Ait, NAit, SA >::Johnson(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::compute_all_pairs_distances(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::get_distance(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::get_potential(), and Aleph::Johnson< GT, Distance, Ait, NAit, SA >::reweight_arcs().

◆ initialized

template<class GT , class Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

bool Aleph::Johnson< GT, Distance, Ait, NAit, SA >::initialized = false

private

Definition at line 139 of file Johnson.H.

Referenced by Aleph::Johnson< GT, Distance, Ait, NAit, SA >::Johnson(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::compute_all_pairs_distances(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::find_path(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::get_distance(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::get_potential(), and Aleph::Johnson< GT, Distance, Ait, NAit, SA >::is_initialized().

◆ orig_graph

template<class GT , class Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

const GT* Aleph::Johnson< GT, Distance, Ait, NAit, SA >::orig_graph = nullptr

private

Definition at line 132 of file Johnson.H.

Referenced by Aleph::Johnson< GT, Distance, Ait, NAit, SA >::find_path(), and Aleph::Johnson< GT, Distance, Ait, NAit, SA >::map_copy_path_to_original().

◆ sa

template<class GT , class Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

SA Aleph::Johnson< GT, Distance, Ait, NAit, SA >::sa

private

Definition at line 138 of file Johnson.H.

Referenced by Aleph::Johnson< GT, Distance, Ait, NAit, SA >::Johnson(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::compute_all_pairs_distances(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::find_path(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::get_distance(), and Aleph::Johnson< GT, Distance, Ait, NAit, SA >::reweight_arcs().

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

Johnson.H

Classes

Public Types

Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ Arc

◆ Distance_Type

◆ Node

Constructor & Destructor Documentation

◆ Johnson() [1/2]

◆ Johnson() [2/2]

Member Function Documentation

◆ build_reverse_mappings()

◆ checked_add()

◆ checked_sub()

◆ compute_all_pairs_distances()

◆ find_path()

◆ get_copy_node()

◆ get_distance()

◆ get_potential()

◆ get_reweighted_graph() [1/2]

◆ get_reweighted_graph() [2/2]

◆ is_initialized()

◆ map_copy_path_to_original()

◆ reweight_arcs()

Member Data Documentation

◆ copy_to_orig_arc

◆ copy_to_orig_node

◆ dist

◆ graph_copy

◆ h

◆ initialized

◆ orig_graph

◆ sa