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.
BFS Class implementing an abstract Breadth First Search.
DBFS Class extending BFS to create a directed Breadth First Search.
DFS Class implementing an abstract Depth First Search.
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 Class that allows finding a path between two vertices of a graph, 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.
IntegerPrimTreeBuilder Constructs a full minimum spanning tree on a given graph and reports the tree as an iterator over the edges.
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).