uk.ac.ic.doc.automed.util.graph.impl
Class DijkstraSPAlgorithm

java.lang.Object
  uk.ac.ic.doc.automed.util.graph.impl.DijkstraSPAlgorithm

public class DijkstraSPAlgorithm
extends java.lang.Object

Implements Dijkstra Shortest Path Algorithm Coutersy of Ian Philips lecture note in Discrete Mathematics

Author:

dmle

Field Summary

private GraphI

_g

Constructor Summary

DijkstraSPAlgorithm(GraphI g)

Method Summary

void	dfs(Node n, GTree t)
void	dfs(Node n, GTree t, boolean copyEdge)
void	dfs(Node n, GTree t, int nodeCount)
void	dfs(Node n, GTree t, java.util.Map rangeMap, boolean copyEdge)
private Node	getStrictestNode(java.util.Collection nodes, java.util.Collection exclude, java.util.Map rangeMap)
protected Node	minFringe(Node n, GTree tree)
GTree	minimumSPT() Implement Prim's MST algorithm
protected Node	nextFringe(java.util.Map fringes)
GTree	spanningTree()
GTree	spanningTree(java.util.Map rangeMap, boolean copyEdge) Construct a spanning tree based on the range information of the nodes of its graphs
GTree	spanningTree(Node start)
GTree	spanningTree(Node start, boolean copyEdge)
java.util.List	spanningTreeList(int numTrees) Find a number of spanning trees in the graph
java.util.List	spanningTreeList(int numTrees, boolean copyEdge)
GTree	tree(int nodeCount) Return a tree containing a fixed number of nodes
protected java.lang.Double	weight(Node n1, Node n2)

Methods inherited from class java.lang.Object

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

Field Detail

_g

private GraphI _g

Constructor Detail

DijkstraSPAlgorithm

public DijkstraSPAlgorithm(GraphI g)

Method Detail

spanningTree

public GTree spanningTree()

tree

public GTree tree(int nodeCount)

Return a tree containing a fixed number of nodes

Parameters:

nodeCount -

Returns:

dfs

public void dfs(Node n,
                GTree t,
                int nodeCount)

spanningTreeList

public java.util.List spanningTreeList(int numTrees)

Find a number of spanning trees in the graph

Parameters:

numTrees -

Returns:

spanningTreeList

public java.util.List spanningTreeList(int numTrees,
                                       boolean copyEdge)

spanningTree

public GTree spanningTree(java.util.Map rangeMap,
                          boolean copyEdge)

Construct a spanning tree based on the range information of the nodes of its graphs

Parameters:

rangeMap -

copyEdge -

Returns:

getStrictestNode

private Node getStrictestNode(java.util.Collection nodes,
                              java.util.Collection exclude,
                              java.util.Map rangeMap)

spanningTree

public GTree spanningTree(Node start)

spanningTree

public GTree spanningTree(Node start,
                          boolean copyEdge)

dfs

public void dfs(Node n,
                GTree t)

dfs

public void dfs(Node n,
                GTree t,
                boolean copyEdge)

dfs

public void dfs(Node n,
                GTree t,
                java.util.Map rangeMap,
                boolean copyEdge)

minimumSPT

public GTree minimumSPT()

Implement Prim's MST algorithm

Returns:

nextFringe

protected Node nextFringe(java.util.Map fringes)

weight

protected java.lang.Double weight(Node n1,
                                  Node n2)

minFringe

protected Node minFringe(Node n,
                         GTree tree)