net.spy.util
Class ShortestPathFinder

java.lang.Object
  net.spy.util.ShortestPathFinder

public class ShortestPathFinder
extends Object

This is a utility class for finding the least costly paths from each node from a collection to all nodes to which they link.

The basic process is to create some SPNodes and link them together arbitrarily with SPVertex instances. Once the graph is complete, obtain an instance of ShortestPathFinder and have it calculate the paths for any (or all) nodes. calculatePaths may be called as many times as you need, it will reset the paths and build new ones.

For example, consider the graph to the right. The following will be true (this is actually my test case):

From	To	Next Hop	Cost
A	A	n/a	n/a
A	B	B	10
A	C	C	15
A	D	C	25
A	E	C	25
A	F	C	25
A	G	C	35
B	A	n/a	n/a
B	B	C	220
B	C	C	10
B	D	C	20
B	E	C	20
B	F	C	20
B	G	C	30
C	A	n/a	n/a
C	B	F	210
C	C	D	110
C	D	D	10
C	E	E	10
C	F	F	10
C	G	F	20
D	A	n/a	n/a
D	B	C	310
D	C	C	100
D	D	C	110
D	E	C	110
D	F	C	110
D	G	C	120

From	To	Next Hop	Cost
E	A	n/a	n/a
E	B	n/a	n/a
E	C	n/a	n/a
E	D	n/a	n/a
E	E	E	10
E	F	n/a	n/a
E	G	n/a	n/a
F	A	n/a	n/a
F	B	B	200
F	C	B	210
F	D	B	220
F	E	B	220
F	F	B	220
F	G	G	10
G	A	n/a	n/a
G	B	n/a	n/a
G	C	n/a	n/a
G	D	n/a	n/a
G	E	n/a	n/a
G	F	n/a	n/a
G	G	n/a	n/a

Constructor Summary

ShortestPathFinder()
Get an instance of ShortestPathFinder.

Method Summary

void	calculatePaths(Collection<? extends SPNode<?>> nodes) Calculate all the paths for all the nodes in the given collection.
void	calculatePaths(SPNode<?> node) Calculate all of the paths for a single node.

Methods inherited from class java.lang.Object

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

Constructor Detail

ShortestPathFinder

public ShortestPathFinder()

Get an instance of ShortestPathFinder.

Method Detail

calculatePaths

public void calculatePaths(Collection<? extends SPNode<?>> nodes)

Calculate all the paths for all the nodes in the given collection.

Parameters:

nodes - the nodes to calculate

calculatePaths

public void calculatePaths(SPNode<?> node)

Calculate all of the paths for a single node.

Parameters:

node - the node from which to calculate paths