Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
Classes | Public Member Functions | Private Types | Private Member Functions | Static Private Member Functions | Private Attributes | List of all members
Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA > Class Template Reference
Graphs

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 >:
[legend]

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<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > 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:**

  1. 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.
  2. 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.
  3. Reusability: The same Bellman_Ford object can be reused for multiple computations on the same graph. Each operation automatically resets the internal state.
  4. 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 161 of file Bellman_Ford.H.

Member Typedef Documentation

◆ Arc

template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>
using Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::Arc = typename GT::Arc
private

Definition at line 166 of file Bellman_Ford.H.

◆ Distance_Type

template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>
typedef Distance::Distance_Type Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::Distance_Type
private

Definition at line 163 of file Bellman_Ford.H.

◆ Node

template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>
using Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::Node = typename GT::Node
private

Definition at line 165 of file Bellman_Ford.H.

Constructor & Destructor Documentation

◆ Bellman_Ford()

template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > 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]__gThe 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]dArc-weight accessor.
[in]__saArc 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 356 of file Bellman_Ford.H.

Member Function Documentation

◆ accum()

template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>
static Distance_Type & Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::accum ( Node *  p)
inlinestaticprivatenoexcept

Definition at line 178 of file Bellman_Ford.H.

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

Referenced by Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::accum(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::compute_nodes_weights(), 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().

◆ build_tree()

template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > 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]treea graph where the shortest paths tree will be stored.
[in]with_mapif 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::and, Aleph::blossom_maximum_cardinality_matching(), 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::Digraph_Iterator< GT, Filter >::has_curr(), 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(), 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<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > 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:

  1. Number of painted arcs == number of painted nodes - 1 (tree property)
  2. Each painted node (except root) has exactly one incoming painted arc
  3. 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 300 of file Bellman_Ford.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::g_, GraphCommon< GT, Node, Arc >::get_tgt_node(), IS_ARC_VISITED, IS_NODE_VISITED, 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<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > 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 189 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<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > 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 379 of file Bellman_Ford.H.

References ARC_BITS, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::arcs_, Aleph::blossom_maximum_cardinality_matching(), Aleph::DynArray< T >::cut(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::g_, 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<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > 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_errorif negative cycles are detected.

Definition at line 1270 of file Bellman_Ford.H.

References Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::accum(), ah_domain_error_if, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::arcs_, Aleph::blossom_maximum_cardinality_matching(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::create_dummy_node(), Aleph::DynArray< T >::cut(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::g_, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::get_from_queue(), GraphCommon< GT, Node, Arc >::get_node_it(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::init_with_indexes(), Aleph::DynMapTree< Key, Data, Tree, Compare >::insert(), Aleph::DynListQueue< T >::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 >::put_in_queue(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::relax_arcs(), and Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::s_.

◆ create_dummy_node()

template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > 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 679 of file Bellman_Ford.H.

References add_arc(), Aleph::blossom_maximum_cardinality_matching(), 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::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<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > 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_errorif the shortest paths tree has not been previously built.

Definition at line 1113 of file Bellman_Ford.H.

References ah_domain_error_if, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::arcs_, Aleph::blossom_maximum_cardinality_matching(), and Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::painted_.

◆ faster_paint_spanning_tree()

template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > 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]startsource 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 630 of file Bellman_Ford.H.

References ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::g_, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::get_from_queue(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::init_with_indexes(), Aleph::DynListQueue< T >::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::Bellman_Ford< GT, Distance, Ait, NAit, SA >::paint_tree(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::put_in_queue(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::relax_arcs(), and Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::s_.

◆ get_distance()

template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > 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]nodeThe destination node.
Returns
The accumulated distance from the start node to node.
Exceptions
std::domain_errorif the graph has not been previously painted or if the node is unreachable.

Definition at line 1130 of file Bellman_Ford.H.

References ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), 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, 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<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > 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 464 of file Bellman_Ford.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Depth_First, Aleph::DynListQueue< T >::get(), IS_NODE_VISITED, 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<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > 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 419 of file Bellman_Ford.H.

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

◆ get_min_path()

template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > 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]endThe destination node.
[out]pathPath where the shortest path will be stored.
Returns
The total cost of the path.
Exceptions
std::domain_errorif the graph has not been previously painted.

Definition at line 1254 of file Bellman_Ford.H.

References ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::painted_, and Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::s_.

◆ get_start_node()

template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > 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 412 of file Bellman_Ford.H.

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

◆ has_computation()

template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > 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 398 of file Bellman_Ford.H.

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

◆ has_negative_cycle() [1/2]

template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > 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 781 of file Bellman_Ford.H.

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

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

◆ has_negative_cycle() [2/2]

template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > 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]startSource node from which to check for negative cycles.
Returns
true if a negative cycle is reachable from start, false otherwise.
Exceptions
std::domain_errorif start is nullptr.

Definition at line 757 of file Bellman_Ford.H.

References ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), 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(), and Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::relax_arcs().

◆ idx()

template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>
static int & Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::idx ( Node *  p)
inlinestaticprivatenoexcept

Definition at line 183 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<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > 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 214 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::blossom_maximum_cardinality_matching(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::g_, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::Inf, 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<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > 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 240 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::blossom_maximum_cardinality_matching(), 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, NODE_BITS, NODE_COOKIE, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::painted_, 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<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > 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 405 of file Bellman_Ford.H.

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

◆ last_relax_and_prepare_check_negative_cycle()

template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > 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 522 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::blossom_maximum_cardinality_matching(), 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::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<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > 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 549 of file Bellman_Ford.H.

References Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::accum(), Aleph::blossom_maximum_cardinality_matching(), 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::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<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > 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 570 of file Bellman_Ford.H.

References Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::arcs_, Aleph::blossom_maximum_cardinality_matching(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::g_, GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), 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<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > 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]startsource 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 599 of file Bellman_Ford.H.

References ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), 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::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<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > 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 498 of file Bellman_Ford.H.

References ARC_BITS, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::arcs_, Aleph::blossom_maximum_cardinality_matching(), 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(), 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<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > 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 455 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<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > 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 426 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::blossom_maximum_cardinality_matching(), 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(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::idx(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::Inf, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::sa_, Aleph::sum(), GraphCommon< GT, Node, Arc >::vsize(), and w.

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<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > 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 473 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::blossom_maximum_cardinality_matching(), 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::Bellman_Ford< GT, Distance, Ait, NAit, SA >::put_in_queue(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::sa_, Aleph::sum(), and w.

◆ remove_dummy_node()

template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > 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 741 of file Bellman_Ford.H.

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

◆ search_negative_cycle() [1/4]

template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>
Path< GT > Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::search_negative_cycle ( )
inline

Definition at line 1088 of file Bellman_Ford.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::create_dummy_node(), 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<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > 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 1069 of file Bellman_Ford.H.

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

◆ search_negative_cycle() [3/4]

template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > 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]startsource 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 1015 of file Bellman_Ford.H.

References ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::g_, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::get_from_queue(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::init_with_indexes(), Aleph::DynListQueue< T >::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::Bellman_Ford< GT, Distance, Ait, NAit, SA >::put_in_queue(), 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.

◆ search_negative_cycle() [4/4]

template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > 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]startnode from which the spanning tree is built.
[in]it_factoriterative factor since then the negative cycle is searched.
[in]stepnext 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 952 of file Bellman_Ford.H.

References ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::g_, Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::get_from_queue(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::init_with_indexes(), Aleph::DynListQueue< T >::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::Bellman_Ford< GT, Distance, Ait, NAit, SA >::put_in_queue(), 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.

◆ search_negative_cycle_on_partial_graph()

template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > 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 820 of file Bellman_Ford.H.

References Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::arcs_, Aleph::blossom_maximum_cardinality_matching(), 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(), 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<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > 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 893 of file Bellman_Ford.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::create_dummy_node(), 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<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > 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]startstarting node
Returns
a valid path corresponding to a negative cycle if this is found. Otherwise, an empty path

Definition at line 862 of file Bellman_Ford.H.

References ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::g_, 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::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<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > 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]cyclePath 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::blossom_maximum_cardinality_matching(), and Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::test_negative_cycle().

◆ test_negative_cycle() [4/4]

template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > 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]sThe starting node.
[out]cyclePath 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::blossom_maximum_cardinality_matching(), and Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::test_negative_cycle().

◆ uninit()

template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > 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 279 of file Bellman_Ford.H.

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

Member Data Documentation

◆ arcs_

template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>
DynArray<typename GT::Arc *> Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::arcs_
private

Definition at line 205 of file Bellman_Ford.H.

Referenced by Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::clear(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::compute_nodes_weights(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::extract_min_spanning_tree(), 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::Bellman_Ford< GT, Distance, Ait, NAit, SA >::paint_tree(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::relax_arcs(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::relax_arcs(), and Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::search_negative_cycle_on_partial_graph().

◆ dist_

template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>
Distance Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::dist_
private

Definition at line 211 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<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>
GT& Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::g_
private

Definition at line 206 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 >::check_painted_arcs(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::clear(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::compute_nodes_weights(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::create_dummy_node(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::faster_paint_spanning_tree(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::get_distance(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::get_graph(), 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 >::link_cookies_and_free(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::paint_tree(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::relax_arcs(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::relax_arcs(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::remove_dummy_node(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::search_negative_cycle(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::search_negative_cycle(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::search_negative_cycle_on_partial_graph(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::test_negative_cycle(), and Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::uninit().

◆ Inf

template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>
const Distance_Type Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::Inf
private

Definition at line 207 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<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>
bool Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::painted_ = false
private

Definition at line 208 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 >::init_with_indexes(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::is_painted(), and Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::paint_tree().

◆ s_

template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>
Node* Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::s_ = nullptr
private

Definition at line 209 of file Bellman_Ford.H.

Referenced by Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::check_painted_arcs(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::clear(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::compute_nodes_weights(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::create_dummy_node(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::faster_paint_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 >::get_start_node(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::has_computation(), 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 >::paint_spanning_tree(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::paint_tree(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::remove_dummy_node(), 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().

◆ sa_

template<AlephGraph GT, ArcDistance< GT > Distance = Dft_Dist<GT>, template< class, class > class Ait = Arc_Iterator, template< class, class > class NAit = Out_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>
SA Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::sa_
private

Definition at line 210 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 >::check_painted_arcs(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::clear(), 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(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::relax_arcs(), and Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::search_negative_cycle_on_partial_graph().

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