org.nongnu.multigraph

Class ShortestPathFirst<N,E>

java.lang.Object

org.nongnu.multigraph.ShortestPathFirst<N,E>

public class ShortestPathFirst<N,E>
extends java.lang.Object

Dijkstra's Shortest Path First algoritm, implemented to act on a Graph of N-nodes and Edges, with L-labels

Constructor Summary

Constructors

Constructor and Description
ShortestPathFirst(Graph<N,E> g)

Method Summary

Modifier and Type	Method and Description
N	nexthop(N to) Return the next-hop node for the shortest path from the root node to the given node.
java.util.List<Edge<N,E>>	path(N to) Return the path from the root node to the 'to' node, as a List of Edges, in the current SPF tree.
N	root()
void	run(N root) Construct the SPF tree rooted at the given node, to be used for subsequent shortest-path query call.

Methods inherited from class java.lang.Object

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

Constructor Detail

ShortestPathFirst

public ShortestPathFirst(Graph<N,E> g)

Method Detail

run

public void run(N root)

Construct the SPF tree rooted at the given node, to be used for subsequent shortest-path query call.

Parameters:

root - Root node for the Shortest-Path First tree.

path

public java.util.List<Edge<N,E>> path(N to)

Return the path from the root node to the 'to' node, as a List of Edges, in the current SPF tree. While our SPF supports equal-cost, multiple-paths, we only return one path, for simplicity's sake.

Parameters:

to - The node to query a path for

Returns:

List of Edges forming a path to the given node

nexthop

public N nexthop(N to)

Return the next-hop node for the shortest path from the root node to the given node.

Parameters:

to - Destination node to query path for

Returns:

The best next-hop from the root

root

public N root()