Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA > Class Template Reference

#include <Bellman_Ford.H>

Public Member Functions
	Bellman_Ford (const GT &__g, Distance d=Distance(), SA __sa=SA())
bool	paint_spanning_tree (Node *start)
bool	faster_paint_spanning_tree (Node *start)
bool	has_negative_cycle (Node *start)
bool	has_negative_cycle ()
Path< GT >	test_negative_cycle (Node *start)
Path< GT >	test_negative_cycle ()
tuple< Path< GT >, size_t >	search_negative_cycle (Node *start, double it_factor, const size_t step)
Path< GT >	search_negative_cycle (Node *start)
tuple< Path< GT >, size_t >	search_negative_cycle (double it_factor, const size_t step)
Path< GT >	search_negative_cycle ()
DynArray< Arc * >	extract_mim_spanning_tree ()
void	build_tree (GT &tree, bool with_map=true)
bool	test_negative_cycle (typename GT::Node *s, Path< GT > &cycle)
bool	test_negative_cycle (Path< GT > &cycle)
Distance_Type	get_min_path (typename GT::Node *end, Path< GT > &path)
DynMapTree< Node *, Distance_Type >	compute_nodes_weights ()

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 >

Algorithms associated to Bellman-Ford algorithm for searching minimal paths in a graph.

Member Function Documentation

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 minimal spanning tree of minimal paths.

This method requires that a minimal spanning tree has been executed with a paint() method.

Parameters

[in]	tree	a graph where the minimal spanning tree will be put.
[in]	with_map	if true the the extracted tree is mapped through the cookies with the graph.

Here is the call graph for this function:

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

Retorna en el mapeo avl los pesos asociados a cada nodo obtenidos luego de ejecutar el algoritmo de Bellman-Ford a partir de un nodo ficticio. Esta rutina está concebida específicamente para el algoritmo de Jhonson de cálculo de todos los caminos mínimos a partir de un nodo dado.

Parameters

[in]

m

un mapeo avl dinámico de la forma Node*–>w de puntero a nodo a peso asociado al nodo.

Returns

true si el grafo no tiene un ciclo negativo, en cuyo caso los valores de en m pueden usarse para el algoritmo de Jhonson. Retorna false si se detecta un ciclo negativo.

Here is the call graph for this function:

extract_mim_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_mim_spanning_tree ( )

inline

Extract the minimal spanning tree in a compressed form.

On a previously painted minimal spanning tree of shortest paths starting on source node, this method extract the tree and loads it in an array of arcs.

Returns

an array of arcs belonging to the minimal spanning tree.

Exceptions

domain_error

if the minimal spanning tree has not previously built

Here is the call graph for this function:

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 minimal spaning tree painting from a start node.

This methods executes a probably faster version of Bellman-Ford algorithm

Parameters

[in]

start

source node from which the minimal path will be computed

Returns

true if negative cycles are detected, which case the spanning minimal tree has note sense. Otherwise, false is returned and the minimal spanning tree is painted with the bit Spanning_Tree

Here is the call graph for this function:

has_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 >::has_negative_cycle ( Node *  start )

inline

Returns true if it exists a negative cycle in any path starting from node start

Here is the call graph for this function:

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 minimal spaning tree for the a start node.

Parameters

[in]

start

source node from which the minimal path will be computed

Returns

true if negative cycles are detected, which case the spanning minimal tree has note sense. Otherwise, false is returned and the minimal spanning tree is painted with the bit Spanning_Tree

search_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>>

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 cylce is found return it; } }

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

Warning

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

Parameters

[in]	start	node from which the spanning tree is build.
[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 cyle 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.

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

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 perfomed using the dummy node as starting node.

Here is the call graph for this function:

search_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>>

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.

Parameters

[in]	start	node from which the spanning tree is build.
[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 cyle 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.

Here is the call graph for this function:

test_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>>

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

inline

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

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

Parameters

[in]

start

stating node

Returns

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

Here is the call graph for this function:

test_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>>

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.

---

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

• Bellman_Ford.H