openlist.examples
Class WeightedDirectedGraph

java.lang.Object
  openlist.examples.WeightedDirectedGraph

public class WeightedDirectedGraph
extends java.lang.Object

Weighted Directed Graph class to be used for Dijkstra's algorithm

Nested Class Summary

(package private) class	WeightedDirectedGraph.Arc Arc represents an arc from a given node to a target nodes, having a specified weight.
(package private) class	WeightedDirectedGraph.Node Node represents a node in the graph, along with distance and predecessor information used by Dijkstra's algorithm.

Field Summary

(package private) java.util.LinkedList<WeightedDirectedGraph.Node>	activeNodes a LinkedList of the active nodes during execution of Dijkstra's algorithm This list will be initialized as a clone of nodes, and retired nodes removed from it.
(package private) static long	INFINITY a large number used to represent infinity distance
(package private) java.util.LinkedList<WeightedDirectedGraph.Node>	nodes a LinkedList of the nodes in the graph in internal form
(package private) static int	SOURCE_INDEX The first node is always the source, by convention.

Constructor Summary

WeightedDirectedGraph(java.lang.Object raw)
Construct a graph from raw input.

Method Summary

OpenList<java.lang.Object>	analyze() analyze conducts Dijkstra's algorithm
(package private) WeightedDirectedGraph.Node	findByName(Symbol symbol) Find a Node by name in the LinkedList of nodes.
(package private) WeightedDirectedGraph.Node	findSmallestActiveNode() Find the active node with the smallest distance, and make it inactive.

Methods inherited from class java.lang.Object

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

Field Detail

SOURCE_INDEX

static final int SOURCE_INDEX

The first node is always the source, by convention.

See Also:

Constant Field Values

INFINITY

static final long INFINITY

a large number used to represent infinity distance

See Also:

Constant Field Values

nodes

java.util.LinkedList<WeightedDirectedGraph.Node> nodes

a LinkedList of the nodes in the graph in internal form

activeNodes

java.util.LinkedList<WeightedDirectedGraph.Node> activeNodes

a LinkedList of the active nodes during execution of Dijkstra's algorithm This list will be initialized as a clone of nodes, and retired nodes removed from it.

Constructor Detail

WeightedDirectedGraph

public WeightedDirectedGraph(java.lang.Object raw)

Construct a graph from raw input. We use asserts to provide to actions for errors, such as wrong input format.

Parameters:

raw - OpenList correspding to S expression representing graph

Method Detail

analyze

public OpenList<java.lang.Object> analyze()

analyze conducts Dijkstra's algorithm

Returns:

a list of Strings representing Nodes in decreasing distance from the source, with the predecessor node of each. By convention, the predecessor of the source will be returned as the source itself.

findByName

WeightedDirectedGraph.Node findByName(Symbol symbol)

Find a Node by name in the LinkedList of nodes. This is used during internalize() only.

Parameters:

symbol -

Returns:

a reference to the Node, or null if it is not found

findSmallestActiveNode

WeightedDirectedGraph.Node findSmallestActiveNode()

Find the active node with the smallest distance, and make it inactive.

Returns:

the active node with the smallest distance