Aleph::Bellman_Ford_Negative_Cycle< GT, Distance, Ait, NAit, SA > Struct Template Reference

Detects if a negative cycle exists and eventually computes it. More...

#include <Bellman_Ford.H>

Public Member Functions
bool	operator() (GT &g, Path< GT > &path, Distance &d, SA &sa) const
	Invokes the detection and calculation of a negative cycle.
bool	operator() (GT &g, Path< GT > &path, Distance &&d=Distance(), SA &&sa=SA()) const
bool	operator() (GT &g, typename GT::Node *s, Path< GT > &path, Distance &d, SA &sa) const
	Invokes the detection and calculation of a negative cycle.
bool	operator() (GT &g, typename GT::Node *s, Path< GT > &path, Distance &&d=Distance(), SA &&sa=SA()) const
Path< GT >	operator() (GT &g, typename GT::Node *s, Distance &d, SA &sa) const
	Search for a negative cycle starting from a specific node.
Path< GT >	operator() (GT &g, typename GT::Node *s, Distance &&d=Distance(), SA &&sa=SA()) const
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
Path< GT >	operator() (GT &g, Distance &d, SA &sa) const
	Search for a negative cycle in the entire graph.
Path< GT >	operator() (GT &g, Distance &&d=Distance(), SA &&sa=SA()) const
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Detailed Description

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

Detects if a negative cycle exists and eventually computes it.

This functor takes a digraph and optionally a source node, executes the Bellman-Ford algorithm and if a negative cycle is detected then it stores it in a path.

The procedure is parameterized with the following specifications:

• GT: the graph type based on List_Graph or List_Digraph.
• Distance: The arc weight reading class that must export the following attributes:
  • Distance::Distance_Type: the data type that represents a weight on an arc.
  • Distance::Distance_Type operator()(typename GT::Arc *a): returns the weight value on arc a.
• SA: arc filter.

Definition at line 1356 of file Bellman_Ford.H.

Member Function Documentation

operator()() [1/8]

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

Path< GT > Aleph::Bellman_Ford_Negative_Cycle< GT, Distance, Ait, NAit, SA >::operator() ( GT &  g, Distance &&  d = Distance(), SA &&  sa = SA()  ) const

inline

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 1446 of file Bellman_Ford.H.

References Aleph::maps().

operator()() [2/8]

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

Path< GT > Aleph::Bellman_Ford_Negative_Cycle< GT, Distance, Ait, NAit, SA >::operator() ( GT &  g, Distance &  d, SA &  sa  ) const

inline

Search for a negative cycle in the entire graph.

Parameters

[in,out]	g	The graph (temporarily modified during computation).
[in]	d	Distance accessor.
[in]	sa	Arc filter.

Returns

Path containing the negative cycle if found, empty path otherwise.

Definition at line 1438 of file Bellman_Ford.H.

References Aleph::maps().

operator()() [3/8]

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

bool Aleph::Bellman_Ford_Negative_Cycle< GT, Distance, Ait, NAit, SA >::operator() ( GT &  g, Path< GT > &  path, Distance &&  d = Distance(), SA &&  sa = SA()  ) const

inline

Definition at line 1375 of file Bellman_Ford.H.

References Aleph::maps().

operator()() [4/8]

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

bool Aleph::Bellman_Ford_Negative_Cycle< GT, Distance, Ait, NAit, SA >::operator() ( GT &  g, Path< GT > &  path, Distance &  d, SA &  sa  ) const

inline

Invokes the detection and calculation of a negative cycle.

Parameters

[in,out]	g	the graph (temporarily modified during computation).
[out]	path	the path where the cycle is stored in case a negative cycle is detected.
[in,out]	d	distance map (modified during computation).
[in]	sa	arc filter for traversal.

Returns

true if a negative cycle exists; false otherwise.

Exceptions

bad_alloc

if there is not enough memory.

Definition at line 1368 of file Bellman_Ford.H.

References Aleph::maps().

operator()() [5/8]

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

Path< GT > Aleph::Bellman_Ford_Negative_Cycle< GT, Distance, Ait, NAit, SA >::operator() ( GT &  g, typename GT::Node *  s, Distance &&  d = Distance(), SA &&  sa = SA()  ) const

inline

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 1424 of file Bellman_Ford.H.

References Aleph::maps().

operator()() [6/8]

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

Path< GT > Aleph::Bellman_Ford_Negative_Cycle< GT, Distance, Ait, NAit, SA >::operator() ( GT &  g, typename GT::Node *  s, Distance &  d, SA &  sa  ) const

inline

Search for a negative cycle starting from a specific node.

Parameters

[in,out]	g	The graph (temporarily modified during computation).
[in]	s	The starting node.
[in]	d	Distance accessor.
[in]	sa	Arc filter.

Returns

Path containing the negative cycle if found, empty path otherwise.

Definition at line 1416 of file Bellman_Ford.H.

References Aleph::maps().

operator()() [7/8]

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

bool Aleph::Bellman_Ford_Negative_Cycle< GT, Distance, Ait, NAit, SA >::operator() ( GT &  g, typename GT::Node *  s, Path< GT > &  path, Distance &&  d = Distance(), SA &&  sa = SA()  ) const

inline

Definition at line 1400 of file Bellman_Ford.H.

References Aleph::maps().

operator()() [8/8]

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

bool Aleph::Bellman_Ford_Negative_Cycle< GT, Distance, Ait, NAit, SA >::operator() ( GT &  g, typename GT::Node *  s, Path< GT > &  path, Distance &  d, SA &  sa  ) const

inline

Invokes the detection and calculation of a negative cycle.

Parameters

[in,out]	g	the graph (temporarily modified during computation).
[in]	s	the starting node.
[out]	path	the path where the cycle is stored in case a negative cycle is detected.
[in,out]	d	distance map (modified during computation).
[in]	sa	arc filter for traversal.

Returns

true if a negative cycle exists; false otherwise.

Exceptions

bad_alloc

if there is not enough memory.

Definition at line 1393 of file Bellman_Ford.H.

References Aleph::maps().

---

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

• Bellman_Ford.H