drcl.net.graph
Class ShortestPathTree

java.lang.Object
  drcl.net.graph.ShortestPathTree

Direct Known Subclasses:

routing_msp2

public class ShortestPathTree

extends java.lang.Object

This class implements the Dijkstra algorithm and calculates the minimum shortest path tree for a graph.

Constructor Summary

ShortestPathTree()

Method Summary

double[]	getCost() Returns the result cost from source from the previous run.
boolean	isDebugEnabled()
int[][]	run(int sourceID_, int[] destIDs_, Node[] nodes_, boolean trim_) Runs the Dijkstra algorithm.
void	setDebugEnabled(boolean enabled_)

Methods inherited from class java.lang.Object

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

Constructor Detail

ShortestPathTree

public ShortestPathTree()

Method Detail

setDebugEnabled

public void setDebugEnabled(boolean enabled_)

isDebugEnabled

public boolean isDebugEnabled()

run

public int[][] run(int sourceID_,
                   int[] destIDs_,
                   Node[] nodes_,
                   boolean trim_)

Runs the Dijkstra algorithm. The implementation excludes "marked" links (see Link.setMarked(boolean)).

Parameters:

sourceID_ - index of the source node, in the node array.

destIDs_ - indices of the destination node, in the node array.

nodes_ - the node array.

trim_ - set to trim the branches that do not contain destinations.

Returns:

three integer arrays. 1st array: parent indices of nodes. An index can be -1 if the node has no parent (i.e., the node is either the source or is not intree). 2nd array: parent node interface Id. 3rd array: interface Id of interface to the parent node.

getCost

public double[] getCost()

Returns the result cost from source from the previous run. The indices match the node array in the previous run.