Package com.jgalgo.alg

Algorithms for solving graph problems.

Most algorithms accept a Graph object as input, and perform some computation on it. Algorithms in this package follow a common pattern: an interface is defined for the functionality only (e.g. ShortestPathSingleSource), a result object is defined within the interface (e.g. ShortestPathSingleSource.Result), a default implementation is provided via newInstance() method (e.g. ShortestPathSingleSource.newInstance()), and a builder that allow more control over the algorithm may be provided via builder() method (e.g. ShortestPathSingleSource.builder()). In addition, algorithm interfaces define a result object specifically for int graphs in which the vertices and edges are integer only (e.g. ShortestPathSingleSource.IResult). In the common use case, there is no need to use IntGraph and the result objects that are specific for it.

None of the algorithms or result objects in this package are thread safe. Result objects should not be used once the graph on which the result was computed is modified, as the result object may relay on the graph for information and may not be able to detect the modification.

Most algorithm implementations are not expose as public API.

Interface Summary

Interface	Description
AlgorithmBuilderBase	A base interface for all algorithm builders.
BfsIter<V,E>	Bread first search (BFS) iterator.
BfsIter.Int	A BFS iterator for IntGraph.
BiConnectedComponentsAlgo	An algorithm that compute the bi-connected components of a graph.
BiConnectedComponentsAlgo.IResult	A result object of a BiConnectedComponentsAlgo computation for IntGraph.
BiConnectedComponentsAlgo.Result<V,E>	A result object of a BiConnectedComponentsAlgo computation.
ChinesePostman	An algorithm for the chinese postman problem.
ClosuresEnumerator	An algorithm that enumerate all the closure subsets in a directed graph.
ColoringAlgo	An algorithm that assign a color to each vertex in a graph while avoiding identical color for any pair of adjacent vertices.
ColoringAlgo.Builder	A builder for ColoringAlgo objects.
CoresAlgo	Cores computing algorithm.
CoresAlgo.IResult	The result of the cores computation for IntGraph.
CoresAlgo.Result<V,E>	The result of the cores computation.
CyclesEnumerator	An algorithm that enumerate all cycles in a graph.
CyclesEnumerator.Builder	A builder for CyclesEnumerator objects.
DfsIter<V,E>	Depth first search (DFS) iterators static class.
DfsIter.Int	A DFS iterator for IntGraph.
DistanceMeasures<V,E>	A set of graph distance measures.
DominatingSetAlgo	An algorithm for computing a minimum dominating set.
EdgeCover	Minimum edge vertex cover algorithm.
EdgeCover.Builder	A builder for EdgeCover algorithms.
EulerianTourAlgo	Eulerian tour calculation algorithm.
Flow<V,E>	Flow on graph edges.
HamiltonianPathAlgo	Hamiltonian path/cycle algorithm.
IDistanceMeasures	A set of graph distance measures for IntGraph.
IFlow	Flow on IntGraph edges.
IMatching	A matching in a IntGraph.
IPath	A path of edges in an int graph.
IsomorphismIMapping	A mapping between two graphs that preserves the structure of the graphs for IntGraph.
IsomorphismMapping<V1,E1,V2,E2>	A mapping between two graphs that preserves the structure of the graphs.
IsomorphismTester	Tester that check whether two graphs are isomorphic.
IVertexBiPartition	A partition of the vertices of an int graph into two blocks.
IVertexPartition	A partition of the vertices of an int graph.
KEdgeConnectedComponentsAlgo	An algorithm that compute the k-edge connected components of a graph.
KShortestPathsST	An algorithm for computing the K shortest paths between two vertices in a graph.
KVertexConnectedComponentsAlgo	Finds the k-vertex connected components of a graph.
KVertexConnectedComponentsAlgo.IResult	Result of a KVertexConnectedComponentsAlgo computation for IntGraph.
KVertexConnectedComponentsAlgo.Result<V,E>	Result of a KVertexConnectedComponentsAlgo computation.
LowestCommonAncestorDynamic	Dynamic algorithm for Lowest Common Ancestor (LCA) queries.
LowestCommonAncestorDynamic.Builder	A builder for LowestCommonAncestorDynamic objects.
LowestCommonAncestorDynamic.Vertex	A tree vertex in an LowestCommonAncestorDynamic data structure.
LowestCommonAncestorOffline	An algorithm for computing the lowest common ancestor (LCA) of two vertices in a tree, offline.
LowestCommonAncestorOffline.IQueries	Queries container for LowestCommonAncestorOffline computations for IntGraph.
LowestCommonAncestorOffline.IResult	Result of a LowestCommonAncestorOffline computation for IntGraph.
LowestCommonAncestorOffline.Queries<V,E>	Queries container for LowestCommonAncestorOffline computations.
LowestCommonAncestorOffline.Result<V,E>	Result of a LowestCommonAncestorOffline computation.
LowestCommonAncestorStatic	Static Lowest Common Ancestor (LCA) algorithm.
LowestCommonAncestorStatic.DataStructure<V,E>	Data structure result created from a static LCA pre-processing.
LowestCommonAncestorStatic.IDataStructure	Data structure result created from a static LCA pre-processing for IntGraph.
Matching<V,E>	A matching in a graph.
MatchingAlgo	Maximum/minimum matching algorithm.
MatchingAlgo.Builder	A builder for MatchingAlgo objects.
MaximalCliquesEnumerator	Algorithm for enumerating over all maximal cliques in a graph.
MaximalCliquesEnumerator.Builder	A builder for MaximalCliquesEnumerator objects.
MaximumFlow	Calculate the maximum flow in a flow network.
MaximumFlow.Builder	A builder for MaximumFlow objects.
MinimumCostFlow	Compute the minimum-cost (max) flow in a flow network.
MinimumCostFlow.Builder	A builder for MinimumCostFlow objects.
MinimumDirectedSpanningTree	Minimum spanning tree algorithm for directed graphs.
MinimumEdgeCutAllST	Minimum Edge-Cut algorithm that finds all minimum edge-cuts in a graph between two terminal vertices (source-sink, S-T).
MinimumEdgeCutGlobal	Global Minimum Edge-Cut algorithm without terminal vertices.
MinimumEdgeCutST	Minimum Edge-Cut algorithm with terminal vertices (source-sink, S-T).
MinimumMeanCycle	Algorithm that find the cycle with the minimum mean weight.
MinimumMeanCycle.Builder	A builder for MinimumMeanCycle objects.
MinimumSpanningTree	Minimum spanning tree algorithm.
MinimumSpanningTree.Builder	A builder for MinimumSpanningTree objects.
MinimumSpanningTree.IResult	A result object for MinimumSpanningTree computation for IntGraph.
MinimumSpanningTree.Result<V,E>	A result object for MinimumSpanningTree computation.
MinimumVertexCutAllGlobal	Minimum Vertex-Cut algorithm that finds all minimum vertex-cuts in a graph (global vertex-cut).
MinimumVertexCutAllST	Minimum Vertex-Cut algorithm that finds all minimum vertex-cuts in a graph between two terminal vertices (source-sink, S-T).
MinimumVertexCutGlobal	Minimum Vertex-Cut algorithm without terminal vertices.
MinimumVertexCutST	Minimum Vertex-Cut algorithm with terminal vertices (source-sink, S-T).
Path<V,E>	A path of edges in a graph.
RandomizedAlgorithm	Randomized algorithm interface.
RandomWalkIter<V,E>	Random walk iterator.
RandomWalkIter.Int	A random walk iterator for IntGraph.
ShortestPathAllPairs	An algorithm that compute all pairs shortest path (APSP) in a graph.
ShortestPathAllPairs.Builder	A builder for ShortestPathAllPairs objects.
ShortestPathAllPairs.IResult	A result object for an ShortestPathAllPairs algorithm for IntGraph.
ShortestPathAllPairs.Result<V,E>	A result object for an ShortestPathAllPairs algorithm.
ShortestPathHeuristicST	Shortest path algorithm that uses a distance heuristic function.
ShortestPathHeuristicST.Builder	A builder for ShortestPathHeuristicST objects.
ShortestPathSingleSource	Single Source Shortest Path algorithm.
ShortestPathSingleSource.Builder	A builder for ShortestPathSingleSource objects.
ShortestPathSingleSource.IResult	A result object for the ShortestPathSingleSource problem for IntGraph.
ShortestPathSingleSource.Result<V,E>	A result object for the ShortestPathSingleSource problem.
ShortestPathST	An algorithm for computing the shortest path between two vertices in a graph.
ShortestPathST.Builder	A builder for ShortestPathST objects.
SimplePathsEnumerator	An algorithm that enumerate over simple paths between a source and a target.
SteinerTreeAlgo	An algorithm for the Steiner tree problem.
SteinerTreeAlgo.IResult	A result object for SteinerTreeAlgo computation for IntGraph.
SteinerTreeAlgo.Result<V,E>	A result object for SteinerTreeAlgo computation.
StronglyConnectedComponentsAlgo	Strongly Connected components algorithm.
StronglyConnectedComponentsAlgo.Builder	A builder for StronglyConnectedComponentsAlgo objects.
TopologicalOrderAlgo	Algorithm that calculate a topological order of graph vertices.
TopologicalOrderAlgo.IResult	A result object of a TopologicalOrderAlgo algorithm for IntGraph.
TopologicalOrderAlgo.Result<V,E>	A result object of a TopologicalOrderAlgo algorithm.
TreePathMaxima	Tree Path Maxima (TPM) algorithm.
TreePathMaxima.Builder	A builder for TreePathMaxima objects.
TreePathMaxima.IQueries	Queries container for TreePathMaxima computations for IntGraph.
TreePathMaxima.IResult	A result object for TreePathMaxima algorithm for IntGraph.
TreePathMaxima.Queries<V,E>	Queries container for TreePathMaxima computations.
TreePathMaxima.Result<V,E>	A result object for TreePathMaxima algorithm.
TspMetric	Metric Traveling Salesman Problem (TSP) algorithm.
VertexBiPartition<V,E>	A partition of the vertices of a graph into two blocks.
VertexCover	Minimum weighted vertex cover algorithm.
VertexPartition<V,E>	A partition of the vertices of a graph.
VoronoiAlgo	Voronoi cells algorithm.
VoronoiAlgo.IResult	A result object of VoronoiAlgo computation for IntGraph.
VoronoiAlgo.Result<V,E>	A result object of VoronoiAlgo computation.
WeaklyConnectedComponentsAlgo	Weakly Connected components algorithm.

Class Summary

Class	Description
BipartiteGraphs	Static class for bipartite graphs.
Trees	Static methods class for tree graphs.
TspMetricMatchingAppx	TSP \(3/2\)-approximation using maximum matching.
TspMetricMSTAppx	TSP \(2\)-approximation using MST.

Enum Summary

Enum	Description
EdgeDirection	The direction type of an edge with respect to a vertex.

Exception Summary

Exception	Description
NegativeCycleException	Exception thrown when a negative cycle is detected in a graph during a shortest path computation.