Package jdsl.graph.algo

Package of basic graph algorithms, including algorithms for depth-first search, single-source shortest paths (Dijkstra's), topological sort (Knuth), and minimum spanning trees (Prim-Jarnik).

See:
Description

Class Summary

AbstractTopologicalSort	This abstract class is the foundation for both types of topological sorts, that is, the standard variety where each vertex is given a unique number, and the level-numbering variety in which numbers attached to vertices are not unique.
DFS	algorithmic template may be extended to solve a variety of problems on either directed or undirected graphs.
DirectedDFS
DirectedFindCycleDFS	This class specializes DFS to determine if the connected component of the start vertex contains a cycle and if so return it.
FindCycleDFS	This class specializes DFS to determine if the connected component of the start vertex contains a cycle and if so return it.
IntegerDijkstraPathfinder	using Dijkstra's algorithm.
IntegerDijkstraTemplate	Implementation of Dijkstra's algorithm using the template-method pattern: the core functionality is coded in a few final methods that call overridable methods to do some of the work.
IntegerPrimTemplate	Implementation of the algorithm of Prim and Jarnik for finding a minimum spanning tree, using the template-method pattern: the core functionality is coded in a few final methods that call overridable methods to do some of the work.
TopologicalSort	This algorithm class performs a topological ordering on a given DAG.
UnitWeightedTopologicalNumbering	This algorithm class computes the optimal unit-weighted topological numbering for a given DAG.

Exception Summary

AnachronismException	This is an exception thrown specifically by the DFS to signify that an internal error has arisen in the computation of start/finish times.
InvalidQueryException	This exception is currently used only by the two subclasses of AbstractTopologicalSort.

Package jdsl.graph.algo Description

Package of basic graph algorithms, including algorithms for depth-first search, single-source shortest paths (Dijkstra's), topological sort (Knuth), and minimum spanning trees (Prim-Jarnik).