Package goldman.graph

A graph represents general relationships between pairs of elements from among a set of elements.

See:
          Description

Interface Summary
Edge<V> The Edge interface is used for an unweighted edge.
Graph<V,E extends Edge<V>> A graph represents general relationships between pairs of elements from among a set of elements.
GraphRepresentation<V,E extends Edge<V>> The GraphRepresentation interface defines the methods that must be supported by any graph representation, such as the adjacency list and adjacency matrix representations.
WeightedEdge<V> The WeightedEdge interface is used for a weighted edge.
WeightedGraph<V,E extends WeightedEdge<V>> The weighted graph algorithms we present do not depend on a particular graph implementation.
 

Class Summary
AbstractGraph<V,E extends Edge<V>> The AbstractGraph class embodies algorithms that perform computations on a graph in terms of the Graph interface.
AbstractWeightedGraph<V,E extends WeightedEdge<V>> The AbstractWeightedGraph class embodies algorithms that perform computations on a weighted graph in terms of the WeightedGraph interface.
AdjacencyList<V,E extends Edge<V>> The AdjacencyList class provides an implementation for the adjacency list representation of a graph.
AdjacencyListRepresentation<V,E extends Edge<V>> The AdjacencyListRepresentation class implements the adjacency list representation of a graph.
AdjacencyMatrix<V,E extends Edge<V>> The AdjacencyMatrix class provides an implementation for the adjacency matrix representation of a graph.
AdjacencyMatrixRepresentation<V,E extends Edge<V>> The AdjacencyMatrixRepresentation class implements the adjacency matrix representation of a graph.
InTree<V,E extends Edge<V>> The InTree class provides an implementation of an in-tree that stores a parent edge associated with each vertex of the graph (possibly null).
ShortestPathMatrix<V,E extends WeightedEdge<V>> The ShortestPathMatrix class is used to store the result from an all-pairs shortest path algorithm.
SimpleEdge<V> The SimpleEdge class provides a sample implementation for an edge.
SimpleWeightedEdge<V> The simple weighted edge class provides a sample implementation for a weighted edge.
WeightedAdjacencyList<V,E extends WeightedEdge<V>> The WeightedAdjacencyList class provides an implementation for a weighted adjacency list.
WeightedAdjacencyMatrix<V,E extends WeightedEdge<V>> The WeightedAdjacencyMatrix class provides an implementation for a weighted adjacency matrix.
 

Exception Summary
DisconnectedGraphException The DisconnectedGraphException is thrown when a graph algorithm that should only be applied on a connected graph (e.g., a spanning tree algorithm) is applied to a graph that is composed of more than one connected component.
GraphException The GraphException is thrown when a graph algorithm is called on the incorrect type of graph.
NegativeWeightEdgeException The NegativeWeightEdgeException is thrown when a graph algorithm that should only be applied on a weighted graph without any negative weight edges (e.g., Dijkstra's single-source shortest path algorithm) whenever a negative weight edge that is encountered.
 

Package goldman.graph Description

A graph represents general relationships between pairs of elements from among a set of elements. The elements are called vertices, and the relationships between them are called edges. The graph algorithms we present do not depend on a particular graph implementation. Instead, they are implemented entirely in terms of the Graph ADT or WeightedGraph ADT. One advantage of this approach is that it allows the presentation and implementation of the graph algorithms to be expressed independent of the underlying graph representation.