Opus5
Class Algorithms

java.lang.Object
  |
  +--Opus5.Algorithms

public class Algorithms

extends java.lang.Object

Various algorithms.

Version:

$Id: Algorithms.java,v 3.10 1999/03/31 16:10:45 brpreiss Exp $

Author:

Bruno R. Preiss, P.Eng.

Constructor Summary

Algorithms()

Method Summary

static void	breadthFirstTraversal(Tree tree) Traverses a tree breadth-first, printing each node as it is visited.
static void	calculator(java.io.Reader in, java.io.PrintWriter out) A reverse-polish calculator.
static Digraph	criticalPathAnalysis(Digraph g) Computes the critical path in an event-node graph.
static Digraph	DijkstrasAlgorithm(Digraph g, int s) Dijkstra's algorithm to solve the single-source, shortest path problem for the given edge-weighted, directed graph.
static void	equivalenceClasses(java.io.Reader in, java.io.PrintWriter out) Computes equivalence classes using a partition.
static Digraph	FloydsAlgorithm(Digraph g) Floyd's algorithm to solve the all-pairs, shortest path problem for the given edge-weighted, directed graph.
static Graph	KruskalsAlgorithm(Graph g) Kruskal's algorithm to find a minimum-cost spanning tree for the given edge-weighted, undirected graph.
static Graph	PrimsAlgorithm(Graph g, int s) Prim's algorithm to find a minimum-cost spanning tree for the given edge-weighted, undirected graph.
static void	translate(java.io.Reader dictionary, java.io.Reader inputText, java.io.PrintWriter outputText) Reads a dictionary and then translates the words in an input text word-by-word, printing the result on the output stream.
static void	wordCounter(java.io.Reader in, java.io.PrintWriter out) Counts the number of distinct words in the input stream and then prints a table of the words and the number of occurrences on the output stream.

Methods inherited from class java.lang.Object

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

Constructor Detail

Algorithms

public Algorithms()

Method Detail

breadthFirstTraversal

public static void breadthFirstTraversal(Tree tree)

Traverses a tree breadth-first, printing each node as it is visited. Uses a queue to keep track of the nodes to be visited.

Parameters:

tree - The tree to traverse.

See Also:

Queue

equivalenceClasses

public static void equivalenceClasses(java.io.Reader in,
                                      java.io.PrintWriter out)
                               throws java.io.IOException

Computes equivalence classes using a partition. First reads an integer from the input stream that specifies the size of the universal set. Then reads pairs of integers from the input stream that denote equivalent items in the universal set. Prints the partition on end-of-file.

Parameters:

in - The input stream.

out - The output stream.

Throws:

java.io.IOException - If an error occurs while reading input.

See Also:

Partition

DijkstrasAlgorithm

public static Digraph DijkstrasAlgorithm(Digraph g,
                                         int s)

Dijkstra's algorithm to solve the single-source, shortest path problem for the given edge-weighted, directed graph. The graph must not contain any negative cost cycles.

Parameters:

g - An edge-weighted, directed graph. It is assumed that the edge weights are Ints

s - The start vertex in the graph.

Returns:

A vertex-weighted, directed graph. The weight on a vertex denotes the length of the shortest path to the start vertex. The one edge that emantes from a vertex connects that vertex to its predecessor on the shortest path to the start vertex.

FloydsAlgorithm

public static Digraph FloydsAlgorithm(Digraph g)

Floyd's algorithm to solve the all-pairs, shortest path problem for the given edge-weighted, directed graph.

Parameters:

An - edge-weighted, directed graph. It is assumed that the edge weights are Ints

Returns:

An edge-weighted, directed graph. There is an edge in the result for each pair of vertices if a path that connects those vertices exists. The weight on the edge is the length of the shortest path between the two vertices it connects.

PrimsAlgorithm

public static Graph PrimsAlgorithm(Graph g,
                                   int s)

Prim's algorithm to find a minimum-cost spanning tree for the given edge-weighted, undirected graph.

Parameters:

g - An edge-weighted, undirected graph. It is assumed that the edge weights are Ints

s - A vertex from which to begin constructing the spanning tree.

Returns:

An unweighted, undirected graph that represents the minimum-cost spanning tree.

KruskalsAlgorithm

public static Graph KruskalsAlgorithm(Graph g)

Kruskal's algorithm to find a minimum-cost spanning tree for the given edge-weighted, undirected graph. Uses a partition and a priority queue.

Parameters:

g - An edge-weighted, undirected graph. It is assumed that the edge weights are Ints

Returns:

An unweighted, undirected graph that represents the minimum-cost spanning tree.

See Also:

Partition, PriorityQueue

criticalPathAnalysis

public static Digraph criticalPathAnalysis(Digraph g)

Computes the critical path in an event-node graph.

Parameters:

g - An edge-weighted, directed acylic graph. It is assumed that the edge weights are Ints

Returns:

A vertex-weighted, directed graph. The events (vertices) on the critical path have zero weight. The one edge that emantes from a vertex connects that vertex to its predecessor on the critical path.

calculator

public static void calculator(java.io.Reader in,
                              java.io.PrintWriter out)
                       throws java.io.IOException

A reverse-polish calculator. Reads RPN expression from the input stream and writes the computed results on the output stream. Uses a stack. Recognizes single-digit numbers, +, * and =.

Parameters:

in - The input stream.

out - The output stream.

Throws:

java.io.IOException - If an error occurs while reading input.

See Also:

Stack

wordCounter

public static void wordCounter(java.io.Reader in,
                               java.io.PrintWriter out)
                        throws java.io.IOException

Counts the number of distinct words in the input stream and then prints a table of the words and the number of occurrences on the output stream. Uses a hash table.

Parameters:

in - The input stream.

out - The output stream.

Throws:

java.io.IOException - If an error occurs while reading input.

See Also:

HashTable

translate

public static void translate(java.io.Reader dictionary,
                             java.io.Reader inputText,
                             java.io.PrintWriter outputText)
                      throws java.io.IOException

Reads a dictionary and then translates the words in an input text word-by-word, printing the result on the output stream. The dictionary consists of pairs of words. The first element of each pair is a word in source language. The second element of each pair is the word in the target language. Uses a search tree.

Parameters:

dictionary - An input stream from which the pairs of words are read.

inputText - The input stream to be translated.

outputText - The output stream on which to print the translation.

Throws:

java.io.IOException - If an error occurs while reading input.

See Also:

SearchTree