Bellman-Ford algorithm for shortest paths with negative weights. More...

#include <Bellman_Ford.H>

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

Classes
struct	Ni

struct	Sni

Public Member Functions
	Bellman_Ford (GT &__g, Distance d=Distance(), SA __sa=SA())
	Construct a Bellman-Ford executor.

void	clear () noexcept
	Clear the painted state and reset internal data structures.

bool	has_computation () const noexcept
	Check if a shortest-path tree has been computed or painted.

bool	is_painted () const noexcept
	Check if a shortest-path tree has been painted.

Node *	get_start_node () const noexcept
	Get the start node of the last computation.

const GT &	get_graph () const noexcept
	Get reference to the graph.

bool	paint_spanning_tree (Node *start)
	Paint the shortest paths tree from a `start` node.

bool	faster_paint_spanning_tree (Node *start)
	Faster shortest paths tree painting from a `start` node.

bool	has_negative_cycle (Node *start)
	Test if a negative cycle exists starting from a specific node.

bool	has_negative_cycle ()
	Test if a negative cycle exists anywhere in the graph.

Path< GT >	test_negative_cycle (Node *start)
	Search a negative cycle on all possible paths starting from `start` node.

Path< GT >	test_negative_cycle ()
	Searches and returns a negative cycle (if it exists).

std::tuple< Path< GT >, size_t >	search_negative_cycle (Node *start, double it_factor, const size_t step)
	Searches a negative cycle using the faster version of Bellman-Ford algorithm and iteratively searching the cycle before finishing up.

Path< GT >	search_negative_cycle (Node *start)
	Searches a negative cycle using the faster version of Bellman-Ford algorithm (SPFA variant).

std::tuple< Path< GT >, size_t >	search_negative_cycle (double it_factor, const size_t step)

Path< GT >	search_negative_cycle ()

DynArray< Arc * >	extract_min_spanning_tree ()
	Extract the shortest paths tree in a compressed form.

Distance_Type	get_distance (typename GT::Node *node)
	Get the accumulated distance to a node from a previously painted tree.

void	build_tree (GT &tree, bool with_map=true)
	Extract from the graph a previously painted shortest paths tree.

bool	test_negative_cycle (typename GT::Node *s, Path< GT > &cycle)
	Test for negative cycle and return it if found.

bool	test_negative_cycle (Path< GT > &cycle)
	Test for negative cycle anywhere in the graph.

Distance_Type	get_min_path (typename GT::Node *end, Path< GT > &path)
	Extract the shortest path to a node from a previously painted tree.

DynMapTree< Node *, Distance_Type >	compute_nodes_weights ()
	Returns a mapping with the shortest distances to each node obtained after executing the Bellman-Ford algorithm from a dummy node connected to all nodes with zero-weight edges.

Private Types
typedef Distance::Distance_Type	Distance_Type

using	Node = typename GT::Node

using	Arc = typename GT::Arc

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

void	init_simple (Node *start)
	Initialize node cookies for simple mode (without predecessor tracking).

void	init_with_indexes (Node *start)
	Initialize node cookies with predecessor tracking for path reconstruction.

template<class Info_Type >
void	uninit ()
	Release the memory associated with the node cookies.

bool	check_painted_arcs () noexcept
	Check that painted arcs form a valid spanning tree structure.

void	relax_arcs () noexcept
	Relax all arcs n-1 times (standard Bellman-Ford).

void	relax_arcs (typename GT::Node src, DynListQueue< typename GT::Node > &q)
	Relax outgoing arcs from a source node (SPFA variant).

void	paint_tree () noexcept
	Paint the spanning tree nodes and arcs with the Spanning_Tree bit.

bool	last_relax_and_prepare_check_negative_cycle () noexcept
	Perform one more relaxation pass and check for negative cycle.

bool	last_relax_and_test_negative_cycle () noexcept
	Perform one more relaxation pass to detect (but not prepare) negative cycle.

void	link_cookies_and_free (typename GT::Node *start) noexcept
	Free node cookies and set up predecessor pointers for path reconstruction.

Node *	create_dummy_node ()
	Create a dummy node connected to all nodes with zero-weight edges.

template<class Info_Type >
void	remove_dummy_node (Node *p)
	Remove a dummy node and clean up its cookie.

Path< GT >	search_negative_cycle_on_partial_graph ()
	Build spanning tree from arcs and search for cycle using Tarjan's algorithm.

Static Private Member Functions
static Distance_Type &	accum (Node *p) noexcept

static int &	idx (Node *p) noexcept

static void	put_in_queue (DynListQueue< typename GT::Node * > &q, typename GT::Node *p)
	Insert a node into the queue if not already present (SPFA optimization).

static GT::Node *	get_from_queue (DynListQueue< typename GT::Node * > &q)
	Remove a node from the queue and clear its in-queue flag.

Private Attributes
DynArray< typename GT::Arc * >	arcs

GT &	g

const Distance_Type	Inf

bool	painted = false

Node *	s = nullptr

SA	sa

Distance	dist

Detailed Description

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

Bellman-Ford algorithm for shortest paths with negative weights.

This class implements the Bellman-Ford algorithm for finding shortest paths from a single source node. Unlike Dijkstra's algorithm, Bellman-Ford can handle graphs with negative edge weights and can detect negative cycles.

Two versions are provided:

Standard version: O(V*E) time complexity
Faster version: Uses a queue-based optimization (SPFA variant) which is often faster in practice.

Template parameters:

GT: Graph type (typically List_Digraph).
Distance: Arc weight accessor. Must define Distance_Type and provide Distance_Type operator()(typename GT::Arc *a).
Ait: Arc iterator template for traversing all arcs.
NAit: Node arc iterator template for traversing arcs from a node.
SA: Arc filter for the internal iterators.

Features:

Detects negative cycles
Can return the negative cycle as a path
Computes a shortest-path tree (painted or separate)
Used by Johnson's algorithm for node weight computation

State Management

This class maintains internal state between operations:

painted: Whether a spanning tree is currently painted on the graph
s: The start node of the last computation
arcs: Predecessor array for path reconstruction

Important usage notes:**

Graph modification: The graph is temporarily modified during each operation (node/arc bits and cookies). These modifications are cleaned up when the operation completes. Do not modify the graph structure during an operation.
Sequential calls: Calling paint_spanning_tree() twice without calling clear() will overwrite the previous painted state. If you need to preserve the previous state, call clear() first or use a new Bellman_Ford instance.
Reusability: The same Bellman_Ford object can be reused for multiple computations on the same graph. Each operation automatically resets the internal state.
Exception safety: All operations are exception-safe. If an exception is thrown, the graph is restored to a consistent state (RAII guards ensure cleanup).

Warning: This class is not thread-safe. Each instance maintains internal state that would be corrupted by concurrent access.; The constructor takes a non-const graph reference because the algorithm temporarily modifies node/arc bits and cookies. For methods that detect global negative cycles (no start node), a dummy node is temporarily added to the graph and removed when the operation completes.

Note: For graphs without negative weights, Dijkstra's algorithm is more efficient (O((V+E) log V) vs O(V*E)).

See also: Dijkstra_Min_Paths Johnson Floyd_All_Shortest_Paths

Definition at line 175 of file Bellman_Ford.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 = Out_Iterator, class SA = Dft_Show_Arc<GT>>

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

private

Definition at line 180 of file Bellman_Ford.H.

◆ Distance_Type

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

typedef Distance::Distance_Type Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::Distance_Type

private

Definition at line 177 of file Bellman_Ford.H.

◆ Node

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

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

private

Definition at line 179 of file Bellman_Ford.H.

Constructor & Destructor Documentation

◆ Bellman_Ford()

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

Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::Bellman_Ford	(	GT &	__g,
		Distance	d = `Distance()`,
		SA	__sa = `SA()`
	)

inline

Construct a Bellman-Ford executor.

Parameters

[in]	__g	The graph to operate on. Note: the graph will be temporarily modified (node/arc bits and cookies) during algorithm execution. The modifications are cleaned up after each operation completes.
[in]	d	Arc-weight accessor.
[in]	__sa	Arc filter for internal iterators.

Warning: The graph reference is stored internally. Do not modify the graph structure while a Bellman_Ford operation is in progress.

Definition at line 369 of file Bellman_Ford.H.

Member Function Documentation

◆ accum()

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

static Distance_Type & Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::accum ( Node * p )

inlinestaticprivatenoexcept

Definition at line 192 of file Bellman_Ford.H.

References Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::accum(), and NODE_COOKIE.

◆ build_tree()

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

void Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::build_tree	(	GT &	tree,
		bool	with_map = `true`
	)

inline

Extract from the graph a previously painted shortest paths tree.

This method requires that the shortest paths tree has been computed with paint_spanning_tree() or faster_paint_spanning_tree().

Parameters

[in]	tree	a graph where the shortest paths tree will be stored.
[in]	with_map	if true the extracted tree is mapped through the cookies with the graph.

Definition at line 1174 of file Bellman_Ford.H.

References ah_domain_error_if, ah_logic_error_unless, Aleph::clear_graph(), FunctionalMethods< Container, T >::for_each(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::g, GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::DynMapTree< Key, Data, Tree, Compare >::insert(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), IS_ARC_VISITED, GraphCommon< GT, Node, Arc >::map_arcs(), GraphCommon< GT, Node, Arc >::map_nodes(), Aleph::maps(), NODE_COOKIE, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::painted, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::sa, Aleph::DynMapTree< Key, Data, Tree, Compare >::search(), and Aleph::Spanning_Tree.

◆ check_painted_arcs()

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

bool Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::check_painted_arcs ( )

inlineprivatenoexcept

Check that painted arcs form a valid spanning tree structure.

Verifies the following invariants:

Number of painted arcs == number of painted nodes - 1 (tree property)
Each painted node (except root) has exactly one incoming painted arc
Root node (s) has no incoming painted arcs

For disconnected graphs, only the component reachable from s is verified.

Returns: true if the painted structure is valid, false otherwise.

Definition at line 308 of file Bellman_Ford.H.

References Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::g, GraphCommon< GT, Node, Arc >::get_tgt_node(), IS_ARC_VISITED, IS_NODE_VISITED, Aleph::maps(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::s, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::sa, and Aleph::Spanning_Tree.

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

◆ checked_add()

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

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

inlineprivate

Definition at line 203 of file Bellman_Ford.H.

References ah_overflow_error_if.

Referenced by Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::get_distance(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::last_relax_and_prepare_check_negative_cycle(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::last_relax_and_test_negative_cycle(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::relax_arcs(), and Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::relax_arcs().

◆ clear()

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

void Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::clear ( )

inlinenoexcept

Clear the painted state and reset internal data structures.

This method should be called if you want to reuse the same Bellman_Ford object for a different computation, or if you want to clear the Spanning_Tree bits that were painted on the graph.

After calling clear():

has_computation() returns false
is_painted() returns false
All Spanning_Tree bits on nodes/arcs are cleared
The predecessor array is cleared
NODE_COOKIE pointers are NOT touched (they were already cleaned by previous operations)

Note: This is automatically called at the start of each paint/compute operation, so explicit calls are usually not needed.

Definition at line 393 of file Bellman_Ford.H.

References ARC_BITS, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::arcs, Aleph::DynArray< T >::cut(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::g, Aleph::maps(), NODE_BITS, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::painted, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::s, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::sa, and Aleph::Spanning_Tree.

◆ compute_nodes_weights()

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

DynMapTree< Node *, Distance_Type > Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::compute_nodes_weights ( )

inline

Returns a mapping with the shortest distances to each node obtained after executing the Bellman-Ford algorithm from a dummy node connected to all nodes with zero-weight edges.

This routine is specifically designed for Johnson's algorithm for computing all-pairs shortest paths.

Returns: A tree mapping where each node is mapped to its distance from the dummy source (used as potential for edge reweighting).

Exceptions

std::domain_error if negative cycles are detected.

Definition at line 1270 of file Bellman_Ford.H.

◆ create_dummy_node()

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

Node * Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::create_dummy_node ( )

inlineprivate

Create a dummy node connected to all nodes with zero-weight edges.

Used for detecting negative cycles in the entire graph.

Definition at line 680 of file Bellman_Ford.H.

References add_arc(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::g, GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::maps(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::remove_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::remove_node(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::s, and Distance::set_zero().

Referenced by Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::compute_nodes_weights(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::has_negative_cycle(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::search_negative_cycle(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::search_negative_cycle(), and Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::test_negative_cycle().

◆ extract_min_spanning_tree()

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

DynArray< Arc * > Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::extract_min_spanning_tree ( )

inline

Extract the shortest paths tree in a compressed form.

On a previously painted shortest paths tree starting from a source node, this method extracts the tree and loads it in an array of arcs.

Returns: an array of arcs belonging to the shortest paths tree.

Exceptions

domain_error if the shortest paths tree has not been previously built.

Definition at line 1109 of file Bellman_Ford.H.

References ah_domain_error_if, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::arcs, Aleph::maps(), and Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::painted.

◆ faster_paint_spanning_tree()

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

bool Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::faster_paint_spanning_tree ( Node * start )

inline

Faster shortest paths tree painting from a start node.

This method executes a faster version of Bellman-Ford algorithm (SPFA variant) which is often more efficient in practice.

Parameters

[in] start source node from which the shortest paths will be computed.

Returns: true if negative cycles are detected, in which case the shortest paths tree has no sense. Otherwise, false is returned and the shortest paths tree is painted with the bit Spanning_Tree.

Definition at line 634 of file Bellman_Ford.H.

◆ get_distance()

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

Distance_Type Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::get_distance ( typename GT::Node * node )

inline

Get the accumulated distance to a node from a previously painted tree.

This method is useful when you only need the distance without reconstructing the full path.

Parameters

[in] node The destination node.

Returns: The accumulated distance from the start node to node.

Exceptions

std::domain_error if the graph has not been previously painted or if the node is unreachable.

Definition at line 1127 of file Bellman_Ford.H.

References ah_domain_error_if, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::checked_add(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::dist, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::g, GraphCommon< GT, Node, Arc >::get_tgt_node(), IS_ARC_VISITED, Aleph::maps(), NODE_COOKIE, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::painted, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::s, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::sa, and Aleph::Spanning_Tree.

◆ get_from_queue()

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

static GT::Node * Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::get_from_queue ( DynListQueue< typename GT::Node * > & q )

inlinestaticprivate

Remove a node from the queue and clear its in-queue flag.

Definition at line 467 of file Bellman_Ford.H.

References Aleph::Depth_First, Aleph::DynListQueue< T >::get(), IS_NODE_VISITED, Aleph::maps(), and NODE_BITS.

Referenced by Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::compute_nodes_weights(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::faster_paint_spanning_tree(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::search_negative_cycle(), and Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::search_negative_cycle().

◆ get_graph()

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

const GT & Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::get_graph ( ) const

inlinenoexcept

Get reference to the graph.

Returns: Reference to the graph.

Definition at line 424 of file Bellman_Ford.H.

References Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::g.

◆ get_min_path()

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

Distance_Type Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::get_min_path	(	typename GT::Node *	end,
		Path< GT > &	path
	)

inline

Extract the shortest path to a node from a previously painted tree.

Parameters

[in]	end	The destination node.
[out]	path	Path where the shortest path will be stored.

Returns: The total cost of the path.

Exceptions

std::domain_error if the graph has not been previously painted.

Definition at line 1254 of file Bellman_Ford.H.

References ah_domain_error_if, Aleph::maps(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::painted, and Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::s.

◆ get_start_node()

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

Node * Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::get_start_node ( ) const

inlinenoexcept

Get the start node of the last computation.

Returns: Pointer to the start node, or nullptr if no computation exists.

Definition at line 420 of file Bellman_Ford.H.

References Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::s.

◆ has_computation()

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

bool Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::has_computation ( ) const

inlinenoexcept

Check if a shortest-path tree has been computed or painted.

Returns: true if a previous computation exists, false otherwise.

Definition at line 412 of file Bellman_Ford.H.

References Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::s.

◆ has_negative_cycle() [1/2]

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

bool Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::has_negative_cycle ( )

inline

Test if a negative cycle exists anywhere in the graph.

Creates a temporary dummy node connected to all other nodes with zero-weight edges, then runs negative cycle detection from it.

Returns: true if any negative cycle exists in the graph, false otherwise.

Note: This method temporarily modifies the graph by adding a dummy node. The modification is rolled back even if an exception is thrown.

Definition at line 774 of file Bellman_Ford.H.

References Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::create_dummy_node(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::has_negative_cycle(), and Aleph::maps().

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

◆ has_negative_cycle() [2/2]

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

bool Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::has_negative_cycle ( Node * start )

inline

Test if a negative cycle exists starting from a specific node.

Parameters

[in] start Source node from which to check for negative cycles.

Returns: true if a negative cycle is reachable from start, false otherwise.

Exceptions

std::domain_error if start is nullptr.

Definition at line 749 of file Bellman_Ford.H.

References ah_domain_error_if, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::init_with_indexes(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::last_relax_and_test_negative_cycle(), Aleph::maps(), and Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::relax_arcs().

◆ idx()

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

static int & Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::idx ( Node * p )

inlinestaticprivatenoexcept

Definition at line 197 of file Bellman_Ford.H.

References Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::idx(), and NODE_COOKIE.

Referenced by Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::idx(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::last_relax_and_prepare_check_negative_cycle(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::relax_arcs(), and Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::relax_arcs().

◆ init_simple()

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

void Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::init_simple ( Node * start )

inlineprivate

Initialize node cookies for simple mode (without predecessor tracking).

Definition at line 228 of file Bellman_Ford.H.

References Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::Sni::accum, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::accum(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::g, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::Inf, Aleph::maps(), NODE_BITS, NODE_COOKIE, GraphCommon< GT, Node, Arc >::reset_arcs(), GraphCommon< GT, Node, Arc >::reset_bit(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::s, and Aleph::Spanning_Tree.

◆ init_with_indexes()

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

void Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::init_with_indexes ( Node * start )

inlineprivate

Initialize node cookies with predecessor tracking for path reconstruction.

Definition at line 250 of file Bellman_Ford.H.

References Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::Sni::accum, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::accum(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::arcs, Aleph::DynArray< T >::cut(), Aleph::Depth_First, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::g, GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::Inf, Aleph::maps(), NODE_BITS, NODE_COOKIE, Aleph::DynArray< T >::reserve(), GraphCommon< GT, Node, Arc >::reset_arcs(), GraphCommon< GT, Node, Arc >::reset_bit(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::s, Aleph::Spanning_Tree, and Aleph::DynArray< T >::touch().

Referenced by Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::compute_nodes_weights(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::faster_paint_spanning_tree(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::has_negative_cycle(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::paint_spanning_tree(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::search_negative_cycle(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::search_negative_cycle(), and Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::test_negative_cycle().

◆ is_painted()

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

bool Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::is_painted ( ) const

inlinenoexcept

Check if a shortest-path tree has been painted.

Returns: true if a tree has been painted, false otherwise.

Definition at line 416 of file Bellman_Ford.H.

References Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::painted.

◆ last_relax_and_prepare_check_negative_cycle()

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

bool Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::last_relax_and_prepare_check_negative_cycle ( )

inlineprivatenoexcept

Perform one more relaxation pass and check for negative cycle.

Also updates predecessor array for cycle detection.

Definition at line 525 of file Bellman_Ford.H.

References Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::accum(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::arcs, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::checked_add(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::dist, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::g, GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::idx(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::Inf, Aleph::maps(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::sa, and Aleph::sum().

Referenced by Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::compute_nodes_weights(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::faster_paint_spanning_tree(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::paint_spanning_tree(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::search_negative_cycle(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::search_negative_cycle(), and Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::test_negative_cycle().

◆ last_relax_and_test_negative_cycle()

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

bool Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::last_relax_and_test_negative_cycle ( )

inlineprivatenoexcept

Perform one more relaxation pass to detect (but not prepare) negative cycle.

Definition at line 552 of file Bellman_Ford.H.

References Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::accum(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::checked_add(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::dist, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::g, GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::Inf, Aleph::maps(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::sa, and Aleph::sum().

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

◆ link_cookies_and_free()

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

void Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::link_cookies_and_free ( typename GT::Node * start )

inlineprivatenoexcept

Free node cookies and set up predecessor pointers for path reconstruction.

Definition at line 573 of file Bellman_Ford.H.

References Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::arcs, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::g, GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::maps(), NODE_COOKIE, and GraphCommon< GT, Node, Arc >::vsize().

Referenced by Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::faster_paint_spanning_tree(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::paint_spanning_tree(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::search_negative_cycle(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::search_negative_cycle(), and Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::test_negative_cycle().

◆ paint_spanning_tree()

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

bool Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::paint_spanning_tree ( Node * start )

inline

Paint the shortest paths tree from a start node.

Parameters

[in] start source node from which the shortest paths will be computed.

Returns: true if negative cycles are detected, in which case the shortest paths tree has no sense. Otherwise, false is returned and the shortest paths tree is painted with the bit Spanning_Tree.

Definition at line 602 of file Bellman_Ford.H.

References ah_domain_error_if, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::init_with_indexes(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::last_relax_and_prepare_check_negative_cycle(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::link_cookies_and_free(), Aleph::maps(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::paint_tree(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::relax_arcs(), and Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::s.

◆ paint_tree()

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

void Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::paint_tree ( )

inlineprivatenoexcept

Paint the spanning tree nodes and arcs with the Spanning_Tree bit.

Definition at line 501 of file Bellman_Ford.H.

References ARC_BITS, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::arcs, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::check_painted_arcs(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::g, GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::maps(), NODE_BITS, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::painted, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::s, Aleph::Spanning_Tree, and GraphCommon< GT, Node, Arc >::vsize().

Referenced by Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::faster_paint_spanning_tree(), and Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::paint_spanning_tree().

◆ put_in_queue()

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

static void Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::put_in_queue	(	DynListQueue< typename GT::Node * > &	q,
		typename GT::Node *	p
	)

inlinestaticprivate

Insert a node into the queue if not already present (SPFA optimization).

Definition at line 458 of file Bellman_Ford.H.

References Aleph::Depth_First, IS_NODE_VISITED, NODE_BITS, and Aleph::DynListQueue< T >::put().

Referenced by Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::compute_nodes_weights(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::faster_paint_spanning_tree(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::relax_arcs(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::search_negative_cycle(), and Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::search_negative_cycle().

◆ relax_arcs() [1/2]

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

void Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::relax_arcs ( )

inlineprivatenoexcept

Relax all arcs n-1 times (standard Bellman-Ford).

Definition at line 428 of file Bellman_Ford.H.

Referenced by Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::compute_nodes_weights(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::faster_paint_spanning_tree(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::has_negative_cycle(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::paint_spanning_tree(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::search_negative_cycle(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::search_negative_cycle(), and Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::test_negative_cycle().

◆ relax_arcs() [2/2]

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

void Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::relax_arcs	(	typename GT::Node *	src,
		DynListQueue< typename GT::Node * > &	q
	)

inlineprivate

Relax outgoing arcs from a source node (SPFA variant).

Definition at line 476 of file Bellman_Ford.H.

◆ remove_dummy_node()

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

template<class Info_Type >

void Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::remove_dummy_node ( Node * p )

inlineprivate

Remove a dummy node and clean up its cookie.

Definition at line 736 of file Bellman_Ford.H.

References Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::g, Aleph::maps(), NODE_COOKIE, and Aleph::List_Graph< _Graph_Node, _Graph_Arc >::remove_node().

◆ search_negative_cycle() [1/4]

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

Path< GT > Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::search_negative_cycle ( )

inline

Definition at line 1083 of file Bellman_Ford.H.

References Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::create_dummy_node(), Aleph::maps(), and Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::search_negative_cycle().

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

◆ search_negative_cycle() [2/4]

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

std::tuple< Path< GT >, size_t > Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::search_negative_cycle	(	double	it_factor,
		const size_t	step
	)

inline

Definition at line 1063 of file Bellman_Ford.H.

References Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::create_dummy_node(), Aleph::maps(), and Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::search_negative_cycle().

◆ search_negative_cycle() [3/4]

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

Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::search_negative_cycle ( Node * start )

inline

Searches a negative cycle using the faster version of Bellman-Ford algorithm (SPFA variant).

Parameters

[in] start source node from which the shortest paths tree is built.

Returns: a path containing the negative cycle if found, or an empty path if no negative cycle exists reachable from the start node.

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 1008 of file Bellman_Ford.H.

◆ search_negative_cycle() [4/4]

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

Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::search_negative_cycle	(	Node *	start,
		double	it_factor,
		const size_t	step
	)

inline

Searches a negative cycle using the faster version of Bellman-Ford algorithm and iteratively searching the cycle before finishing up.

Normally, the Bellman-Ford algorith certainly detects a negative cycle if during an additional arcs scanning an arc is relaxed. However, very frequently the cycle appears in graph used for representing the partial spanning tree.

This version could be seen as thus:

threshold = it_factor*|V|;
for (int i = 0; i < |V|; ++i)
  {
    for (e in Arcs) // for each arc e
      relax e;
    if (i >= threshold)
      {

search a cycle in the graph representing the spanning tree threshold += step; if negative cycle is found return it; } }

So, from the threshold-th iteration, the algorithm tries to find a negative cycle on the hope that if this exists, then the algorithm will finish much before the normal completion.

Warning: The cycle searching is done with respect to a source node. So, if no negative cycle is found, then this is still not conclusive for determining that the graph has no negative cycles.

Parameters

[in]	start	node from which the spanning tree is built.
[in]	it_factor	iterative factor since then the negative cycle is searched.
[in]	step	next step from which the next negative cycle will be done.

Returns: a tuple whose get<0> value corresponds to the found negative cycle (if this one exists) and get<1> value is the external iteration when the cycle was found. The idea of this second field is to give feedback in order to eventually refine the it_factor value.

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

This overloaded version searches for negatives cycles in all the graph. For that, a dummy and temporal node is inserted into the graph and the search is performed using the dummy node as starting node.

Definition at line 944 of file Bellman_Ford.H.

◆ search_negative_cycle_on_partial_graph()

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

Path< GT > Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::search_negative_cycle_on_partial_graph ( )

inlineprivate

Build spanning tree from arcs and search for cycle using Tarjan's algorithm.

Definition at line 810 of file Bellman_Ford.H.

References Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::arcs, Aleph::DynMapTree< Key, Data, Tree, Compare >::find(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::g, Aleph::Path< GT >::Iterator::has_current_node(), Aleph::DynMapTree< Key, Data, Tree, Compare >::insert(), Aleph::maps(), NODE_COOKIE, and Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::sa.

Referenced by Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::search_negative_cycle(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::search_negative_cycle(), and Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::test_negative_cycle().

◆ test_negative_cycle() [1/4]

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

Path< GT > Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::test_negative_cycle ( )

inline

Searches and returns a negative cycle (if it exists).

Returns: a path containing a negative cycle (if it exists). Otherwise, it returns an empty path.

Definition at line 884 of file Bellman_Ford.H.

References Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::create_dummy_node(), Aleph::maps(), and Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::test_negative_cycle().

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

◆ test_negative_cycle() [2/4]

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

Path< GT > Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::test_negative_cycle ( Node * start )

inline

Search a negative cycle on all possible paths starting from start node.

If a negative cycle is found, then the Tarjan algorithm is executed for retrieving it. In this case the cycle is returned. Otherwise (there is no negative cycle), the returned path is empty.

Parameters

[in] start starting node

Returns: a valid path corresponding to a negative cycle if this is found. Otherwise, an empty path

Definition at line 853 of file Bellman_Ford.H.

References ah_domain_error_if, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::g, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::init_with_indexes(), Aleph::HTList::is_empty(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::last_relax_and_prepare_check_negative_cycle(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::link_cookies_and_free(), Aleph::maps(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::relax_arcs(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::s, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::search_negative_cycle_on_partial_graph(), and WARNING.

◆ test_negative_cycle() [3/4]

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

bool Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::test_negative_cycle ( Path< GT > & cycle )

inline

Test for negative cycle anywhere in the graph.

Parameters

[out] cycle Path where the cycle is stored if found.

Returns: true if a negative cycle exists, false otherwise.

Definition at line 1241 of file Bellman_Ford.H.

References Aleph::HTList::is_empty(), Aleph::maps(), and Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::test_negative_cycle().

◆ test_negative_cycle() [4/4]

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

bool Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::test_negative_cycle	(	typename GT::Node *	s,
		Path< GT > &	cycle
	)

inline

Test for negative cycle and return it if found.

Parameters

[in]	s	The starting node.
[out]	cycle	Path where the cycle is stored if found.

Returns: true if a negative cycle exists, false otherwise.

Definition at line 1230 of file Bellman_Ford.H.

References Aleph::HTList::is_empty(), Aleph::maps(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::s, and Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::test_negative_cycle().

◆ uninit()

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

template<class Info_Type >

void Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::uninit ( )

inlineprivate

Release the memory associated with the node cookies.

Definition at line 287 of file Bellman_Ford.H.

References Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::g, Aleph::maps(), and NODE_COOKIE.

Member Data Documentation

◆ arcs

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

DynArray<typename GT::Arc *> Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::arcs

private

Definition at line 219 of file Bellman_Ford.H.

◆ dist

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

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

private

Definition at line 225 of file Bellman_Ford.H.

Referenced by Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::get_distance(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::last_relax_and_prepare_check_negative_cycle(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::last_relax_and_test_negative_cycle(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::relax_arcs(), and Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::relax_arcs().

◆ g

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

GT& Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::g

private

Definition at line 220 of file Bellman_Ford.H.

◆ Inf

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

const Distance_Type Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::Inf

private

Definition at line 221 of file Bellman_Ford.H.

Referenced by Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::init_simple(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::init_with_indexes(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::last_relax_and_prepare_check_negative_cycle(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::last_relax_and_test_negative_cycle(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::relax_arcs(), and Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::relax_arcs().

◆ painted

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

bool Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::painted = false

private

Definition at line 222 of file Bellman_Ford.H.

Referenced by Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::build_tree(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::clear(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::extract_min_spanning_tree(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::get_distance(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::get_min_path(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::is_painted(), and Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::paint_tree().

◆ s

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

Node* Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::s = nullptr

private

Definition at line 223 of file Bellman_Ford.H.

◆ sa

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

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

private

Definition at line 224 of file Bellman_Ford.H.

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

Bellman_Ford.H

Classes

Public Member Functions

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

State Management

Member Typedef Documentation

◆ Arc

◆ Distance_Type

◆ Node

Constructor & Destructor Documentation

◆ Bellman_Ford()

Member Function Documentation

◆ accum()

◆ build_tree()

◆ check_painted_arcs()

◆ checked_add()

◆ clear()

◆ compute_nodes_weights()

◆ create_dummy_node()

◆ extract_min_spanning_tree()

◆ faster_paint_spanning_tree()

◆ get_distance()

◆ get_from_queue()

◆ get_graph()

◆ get_min_path()

◆ get_start_node()

◆ has_computation()

◆ has_negative_cycle() [1/2]

◆ has_negative_cycle() [2/2]

◆ idx()

◆ init_simple()

◆ init_with_indexes()

◆ is_painted()

◆ last_relax_and_prepare_check_negative_cycle()

◆ last_relax_and_test_negative_cycle()

◆ link_cookies_and_free()

◆ paint_spanning_tree()

◆ paint_tree()

◆ put_in_queue()

◆ relax_arcs() [1/2]

◆ relax_arcs() [2/2]

◆ remove_dummy_node()

◆ search_negative_cycle() [1/4]

◆ search_negative_cycle() [2/4]

◆ search_negative_cycle() [3/4]

◆ search_negative_cycle() [4/4]

◆ search_negative_cycle_on_partial_graph()

◆ test_negative_cycle() [1/4]

◆ test_negative_cycle() [2/4]

◆ test_negative_cycle() [3/4]

◆ test_negative_cycle() [4/4]

◆ uninit()

Member Data Documentation

◆ arcs

◆ dist

◆ g

◆ Inf

◆ painted

◆ s

◆ sa