Bellman Ford algorithm. More...

#include <JETSCAPE/blob/main/external_packages/gtl/include/GTL/bellman_ford.h>

Inheritance diagram for bellman_ford:

Collaboration diagram for bellman_ford:

Public Member Functions
	bellman_ford ()
	Constructor.

virtual	~bellman_ford ()
	Destructor.

int	check (graph &G)
	Checks whether the preconditions for Bellman Ford are satisfied.

int	run (graph &G)
	Applies algorithm to graph g.

void	reset ()
	Resets the algorithm.

void	source (const node &n)
	Sets source.

node	source () const
	Returns source.

void	weights (const edge_map< double > &weight)
	Sets weights of the edges.

void	store_preds (bool set)
	Enables or disables the storing of predecessors.

bool	store_preds () const
	Returns whether the storing of predecessors is enabled.

bool	reached (const node &n) const
	Returns whether is reachable from source.

double	distance (const node &n) const
	Returns the distance from source to n.

edge	predecessor_edge (const node &n) const
	edge to predecessor of node n on the shortest path from source

node	predecessor_node (const node &n) const
	predecessor of node n on the shortest path from source

bool	negative_cycle () const
	Returns whether there is a cycle with negative weight.

Public Member Functions inherited from algorithm
	algorithm ()
	Creates an algorithm object.

virtual	~algorithm ()
	Destroys the algorithm object.

Private Member Functions
void	relax (const edge &e, bool dir)
	Main method for Bellman Ford.

Private Attributes
node	s
	Stores source.

edge_map< double >	w
	Stores the weights of the edges.

bool	vars_set
	Indicates whether weights were set.

node_map< double >	d
	distance from source s.

node_map< bool >	inf
	Indicates whether the node has distance infinity.

node_map< edge > *	preds
	Stores father of each node (if enabled)

bool	cycle
	Indicates whether there is a cycle with negative weight.

Additional Inherited Members
Public Types inherited from algorithm
enum	{ GTL_OK = 1, GTL_ERROR = 0 }
	Return values for algorithm::check and algorithm::run. More...

Detailed Description

Bellman Ford algorithm.

Date:: 2003/03/24 15:58:54

Revision:: 1.5

Implementation of the single source shortest path due to Bellman and Ford. Unlike Dijkstra's SSSP algorithm this one allows negative edge weights, as long as there are no cycles with negative weight. If there are negative cycles this implementation finds them.

Definition at line 33 of file bellman_ford.h.

View newest version in sPHENIX GitHub at line 33 of file bellman_ford.h

Constructor & Destructor Documentation

__GTL_BEGIN_NAMESPACE bellman_ford::bellman_ford ( )

Constructor.

Definition at line 24 of file bellman_ford.cpp.

View newest version in sPHENIX GitHub at line 24 of file bellman_ford.cpp

References preds, and vars_set.

bellman_ford::~bellman_ford ( )

virtual

Destructor.

Definition at line 30 of file bellman_ford.cpp.

View newest version in sPHENIX GitHub at line 30 of file bellman_ford.cpp

References preds.

Member Function Documentation

int bellman_ford::check ( graph & G )

virtual

Checks whether the preconditions for Bellman Ford are satisfied.

The Precondition are that the weights of the edges have been set and that the graph has at least one node.

Parameters

G graph.

Return values

algorithm::GTL_OK	if algorithm can be applied
algorithm::GTL_ERROR	otherwise.

Implements algorithm.

Definition at line 46 of file bellman_ford.cpp.

View newest version in sPHENIX GitHub at line 46 of file bellman_ford.cpp

References algorithm::GTL_ERROR, algorithm::GTL_OK, graph::nodes_begin(), graph::nodes_end(), and vars_set.

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

double bellman_ford::distance ( const node & n ) const

inline

Returns the distance from source to n.

Parameters

n node

Definition at line 131 of file bellman_ford.h.

View newest version in sPHENIX GitHub at line 131 of file bellman_ford.h

References n.

Referenced by main().

Here is the caller graph for this function:

bool bellman_ford::negative_cycle ( ) const

inline

Returns whether there is a cycle with negative weight.

Definition at line 171 of file bellman_ford.h.

View newest version in sPHENIX GitHub at line 171 of file bellman_ford.h

Referenced by main().

Here is the caller graph for this function:

edge bellman_ford::predecessor_edge ( const node & n ) const

inline

edge to predecessor of node n on the shortest path from source

If n is a root or wasn't reached the return value is the invalid edge edge::edge().

Please note that this requires that this option was enabled during last run.

Parameters

n node.

Returns: predecessor of n.

See Also: bellman_ford::store_preds

Definition at line 147 of file bellman_ford.h.

View newest version in sPHENIX GitHub at line 147 of file bellman_ford.h

References assert, and n.

node bellman_ford::predecessor_node ( const node & n ) const

inline

predecessor of node n on the shortest path from source

If n is a root or wasn't reached the return value is the invalid node node::node().

Please note that this requires that this option was enabled during last run.

Parameters

n node.

Returns: predecessor of n.

See Also: bellman_ford::store_preds

Definition at line 164 of file bellman_ford.h.

View newest version in sPHENIX GitHub at line 164 of file bellman_ford.h

References Acts::UnitConstants::e, and edge::opposite().

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

bool bellman_ford::reached ( const node & n ) const

inline

Returns whether is reachable from source.

Parameters

n node

Definition at line 124 of file bellman_ford.h.

View newest version in sPHENIX GitHub at line 124 of file bellman_ford.h

References inf, and n.

void bellman_ford::relax	(	const edge &	e,
		bool	dir
	)

private

Main method for Bellman Ford.

Parameters

e	edge to be relaxed

Definition at line 126 of file bellman_ford.cpp.

View newest version in sPHENIX GitHub at line 126 of file bellman_ford.cpp

References d, Acts::UnitConstants::e, inf, preds, edge::source(), edge::target(), Acts::Test::tmp(), physmon_ckf_tracking::u, testSigmaEff::v, and w.

Referenced by run().

Here is the call graph for this function:

Here is the caller graph for this function:

void bellman_ford::reset ( )

virtual

Resets the algorithm.

The weights are not reset. You can apply this algorithms twice without setting the weights for the second call.

Implements algorithm.

Definition at line 122 of file bellman_ford.cpp.

View newest version in sPHENIX GitHub at line 122 of file bellman_ford.cpp

Referenced by main().

Here is the caller graph for this function:

int bellman_ford::run ( graph & g )

virtual

Applies algorithm to graph g.

Parameters

g graph

Return values

algorithm::GTL_OK	on success
algorithm::GTL_ERROR	otherwise

Implements algorithm.

Definition at line 61 of file bellman_ford.cpp.

View newest version in sPHENIX GitHub at line 61 of file bellman_ford.cpp

References cycle, d, graph::edges_begin(), graph::edges_end(), end, algorithm::GTL_OK, i, inf, ne_map< Key, Value, Graph, Alloc >::init(), graph::is_undirected(), it, graph::nodes_begin(), graph::number_of_nodes(), preds, relax(), s, physmon_ckf_tracking::u, testSigmaEff::v, and w.

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

void bellman_ford::source ( const node & n )

inline

Sets source.

The default source is the invalid node (node::node()), in this case an arbitrary node is chosen and stored when this algorithm is run.

Parameters

n source.

Definition at line 79 of file bellman_ford.h.

View newest version in sPHENIX GitHub at line 79 of file bellman_ford.h

References n, and physmon_simulation::s.

Referenced by main().

Here is the caller graph for this function:

node bellman_ford::source ( ) const

inline

Returns source.

Returns: source.

Definition at line 86 of file bellman_ford.h.

View newest version in sPHENIX GitHub at line 86 of file bellman_ford.h

References physmon_simulation::s.

void bellman_ford::store_preds ( bool set )

Enables or disables the storing of predecessors.

If enabled for every node the predecessor on the shortest path from will be stored.

Parameters

set	if true predecessors will be stored.

See Also: bellman_ford::predecessor_node, bellman_ford::predecessor_edge

Definition at line 35 of file bellman_ford.cpp.

View newest version in sPHENIX GitHub at line 35 of file bellman_ford.cpp

References preds.

Referenced by main().

Here is the caller graph for this function:

bool bellman_ford::store_preds ( ) const

inline

Returns whether the storing of predecessors is enabled.

Return values

true	iff the storing of predecessors is enabled.

See Also: bellman_ford::predecessor_node, bellman_ford::predecessor_edge

Definition at line 117 of file bellman_ford.h.

View newest version in sPHENIX GitHub at line 117 of file bellman_ford.h

void bellman_ford::weights ( const edge_map< double > & weight )

inline

Sets weights of the edges.

This method must be called before run.

Parameters

w	weights of the edges.

Definition at line 95 of file bellman_ford.h.

View newest version in sPHENIX GitHub at line 95 of file bellman_ford.h

Referenced by main().

Here is the caller graph for this function:

Member Data Documentation

bool bellman_ford::cycle

private

Indicates whether there is a cycle with negative weight.

See Also: bellman_ford::negative_cycle.

Definition at line 232 of file bellman_ford.h.

View newest version in sPHENIX GitHub at line 232 of file bellman_ford.h

Referenced by run().

node_map<double> bellman_ford::d

private

distance from source s.

See Also: bellman_ford::distance.

Definition at line 210 of file bellman_ford.h.

View newest version in sPHENIX GitHub at line 210 of file bellman_ford.h

Referenced by relax(), and run().

node_map<bool> bellman_ford::inf

private

Indicates whether the node has distance infinity.

See Also: bellman_ford::distance.

Definition at line 217 of file bellman_ford.h.

View newest version in sPHENIX GitHub at line 217 of file bellman_ford.h

Referenced by relax(), and run().

node_map<edge>* bellman_ford::preds

private

Stores father of each node (if enabled)

See Also: bellman_ford::store_preds

Definition at line 224 of file bellman_ford.h.

View newest version in sPHENIX GitHub at line 224 of file bellman_ford.h

Referenced by bellman_ford(), relax(), run(), store_preds(), and ~bellman_ford().

node bellman_ford::s

private

Stores source.

See Also: bellman_ford::source.

Definition at line 189 of file bellman_ford.h.

View newest version in sPHENIX GitHub at line 189 of file bellman_ford.h

Referenced by run().

bool bellman_ford::vars_set

private

Indicates whether weights were set.

See Also: bellman_ford::weights.

Definition at line 203 of file bellman_ford.h.

View newest version in sPHENIX GitHub at line 203 of file bellman_ford.h

Referenced by bellman_ford(), and check().

edge_map<double> bellman_ford::w

private

Stores the weights of the edges.

See Also: bellman_ford::weights.

Definition at line 196 of file bellman_ford.h.

View newest version in sPHENIX GitHub at line 196 of file bellman_ford.h

Referenced by relax(), and run().

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

JETSCAPE/blob/main/external_packages/gtl/include/GTL/bellman_ford.h
JETSCAPE/blob/main/external_packages/gtl/src/bellman_ford.cpp

Public Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation