mascoptDev.algos.digraph
Class Bellman

java.lang.Object
  |
  +--mascoptDev.algos.digraph.Bellman

Direct Known Subclasses:

BellmanCost

public class Bellman

extends Object

Provides algorithm of Bellman Ford to find distance from a node and the paths corresponding to this node. After constructing the Bellman object with a graph and the source, two steps are necessary to obtain shortest paths or distances. launch run and choose a destination where you want shortest chain, then launch getChain(destination). The distance on vertex are read with getValue with the parameter COST_LONGEST_PATH. You can change this string to another string to read another value. Note that all values on edges must be stored as string.

Field Summary

String	CAPACITY_STRING_VALUE String which is read on edges for the capacity.
String	COST_BELLMAN String which identify the value to consider as the distance on arc.
static String	FATHER String which identify the value to consider the father of the destination on arc .
static String	FATHER_LEVEL String which identify the value to consider the level of father on vertex.
double	INFINITY String which is infinity.

Constructor Summary

Bellman(DiGraph g)
Constructor.

Bellman(DiGraph g, String cost)
Constructor.

Bellman(DiGraph g, Vertex s)
Constructor.

Bellman(DiGraph g, Vertex s, String cost)
Constructor.

Method Summary

DiPath	getChain(Vertex dest) Returns the chain from source to the vertex dest.
Double	getCost(Arc a)
Vertex	getSource() Return the source of shortest path.
void	run() Computes the shortest distances from vertex source to all other vertex of graph.
void	setSource(Vertex s) Set the source of shortest path.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

COST_BELLMAN

public String COST_BELLMAN

String which identify the value to consider as the distance on arc.

FATHER

public static String FATHER

String which identify the value to consider the father of the destination on arc .

FATHER_LEVEL

public static String FATHER_LEVEL

String which identify the value to consider the level of father on vertex.

CAPACITY_STRING_VALUE

public String CAPACITY_STRING_VALUE

String which is read on edges for the capacity.

INFINITY

public double INFINITY

String which is infinity.

Constructor Detail

Bellman

public Bellman(DiGraph g,
               Vertex s)

Constructor.

Parameters:

s - Vertexrepresenting the source of chains.

Bellman

public Bellman(DiGraph g)

Constructor.

Bellman

public Bellman(DiGraph g,
               String cost)

Constructor.

Parameters:

cost - Stringrepresenting the string value of the cost.

Bellman

public Bellman(DiGraph g,
               Vertex s,
               String cost)

Constructor.

Parameters:

s - Vertexrepresenting the source of chains.

cost - Stringrepresenting the string value of the cost.

Method Detail

getSource

public Vertex getSource()

Return the source of shortest path.

Returns:

the source of shortest path.

setSource

public void setSource(Vertex s)

Set the source of shortest path.

getCost

public Double getCost(Arc a)

run

public void run()

Computes the shortest distances from vertex source to all other vertex of graph.

getChain

public DiPath getChain(Vertex dest)

Returns the chain from source to the vertex dest.

Parameters:

dest - Vertexrepresenting the destination of chain.

Returns:

a DiPath which is the chain of shortest distance between source and dest.