mascoptDev.algos.digraph
Class LongestPathDAG

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

Direct Known Subclasses:

LongestPathDAGCost

public class LongestPathDAG

extends Object

Provides an algorithm which finds the longest distance in a DAG, ie in a DiGraph without cycle and with one source and one well. After constructing the object with a graph, a vertexSet and Arc two steps are necessary to obtain longest path. launch run then launch getChain. 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.
String	LEVEL_VERTEX String which identify the value to consider the level of vertex in the DAG on vertex.

Constructor Summary

LongestPathDAG(DiGraph g, VertexSet w)
Constructor.

LongestPathDAG(DiGraph g, VertexSet w, Arc r)
Constructor.

LongestPathDAG(DiGraph g, VertexSet w, Arc r, String cost)
Constructor.

Method Summary

DiPath	getChain() Returns the chain from the head of request to the tail of request.
Double	getCost(Arc a)
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.

LEVEL_VERTEX

public String LEVEL_VERTEX

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

CAPACITY_STRING_VALUE

public String CAPACITY_STRING_VALUE

String which is read on edges for the capacity.

Constructor Detail

LongestPathDAG

public LongestPathDAG(DiGraph g,
                      VertexSet w,
                      Arc r)

Constructor.

Parameters:

w - VertexSet representing the vertex which belong to the DAG.

r - Arc representing the the source and the destination of the longest path.

LongestPathDAG

public LongestPathDAG(DiGraph g,
                      VertexSet w,
                      Arc r,
                      String cost)

Constructor.

Parameters:

w - VertexSet representing the vertex which belong to the DAG.

cost - String representing the string value of the cost.

r - Arc representing the the source and the destination of the longest path.

LongestPathDAG

public LongestPathDAG(DiGraph g,
                      VertexSet w)

Constructor.

Parameters:

w - VertexSet representing the vertex which belong to the DAG.

Method Detail

getCost

public Double getCost(Arc a)

run

public void run()

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

getChain

public DiPath getChain()

Returns the chain from the head of request to the tail of request.

Returns:

a DiPath which is the chain of longest distance on the request.