mascoptDev.algos.digraph
Class LongestPath

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

public class LongestPath

extends Object

Provides an algorithm which finds the longest distance from a node toward all nodes, and the paths corresponding to this node. This algorithm is implemented like Bellman algorithm. After constructing the object with a graph and the source, two steps are necessary to obtain longest paths or distances. launch run and choose a destination where you want longest 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_LONGEST_PATH String which identify the value to consider as the distance on arc.
String	FATHER String which identify the value to consider the father of the destination on arc .
String	FATHER_LEVEL String which identify the value to consider the level of father on vertex.

Constructor Summary

LongestPath(DiGraph g, Vertex s)
Constructor.

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

Method Summary

DiPath	getChain(Vertex dest) Returns the chain from source to the vertex dest.
void	run() Computes the longest distances from vertex source to all other vertex of graph.

Methods inherited from class java.lang.Object

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

Field Detail

COST_LONGEST_PATH

public String COST_LONGEST_PATH

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

FATHER

public String FATHER

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

FATHER_LEVEL

public 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.

Constructor Detail

LongestPath

public LongestPath(DiGraph g,
                   Vertex s)

Constructor.

Parameters:

s - Vertex representing the source of chains.

LongestPath

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

Constructor.

Parameters:

s - Vertex representing the source of chains.

cost - String representing the string value of the cost.

Method Detail

run

public void run()

Computes the longest 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 - Vertex representing the destination of chain.

Returns:

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