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 is provided via newBuilder() method (e.g. ShortestPathSingleSource.newBuilder()). In addition, algorithm interfaces define a result specifically for graphs in which the vertices and edges are integer only, IntGraph (e.g. ShortestPathSingleSource.IResult). For the most common use case, there is no need to use IntGraph and the result objects that are specific to it.

Non 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.
Bfs	Bread first search (BFS) iterator.
Bfs.IntIter	A BFS iterator for IntGraph.
Bfs.Iter<V,E>	A BFS iterator.
BiConnectedComponentsAlgo	An algorithm that compute the bi-connected components of a graph.
BiConnectedComponentsAlgo.Builder	A builder for BiConnectedComponentsAlgo objects.
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.
ChinesePostman.Builder	A builder for ChinesePostman objects.
ClosuresEnumerator	An algorithm that enumerate all the closure subsets in a directed graph.
ClosuresEnumerator.Builder	A builder for ClosuresEnumerator objects.
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.Builder	A builder for CoresAlgo objects.
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.
Dfs	Depth first search (DFS) iterator.
Dfs.IntIter	A DFS iterator for IntGraph.
Dfs.Iter<V,E>	A DFS iterator.
DominatingSetAlgo	An algorithm for computing a minimum dominating set.
DominatingSetAlgo.Builder	A builder for DominatingSetAlgo algorithms.
EdgeCover	Minimum edge vertex cover algorithm.
EdgeCover.Builder	A builder for EdgeCover algorithms.
EulerianTourAlgo	Eulerian tour calculation algorithm.
EulerianTourAlgo.Builder	A builder for EulerianTourAlgo objects.
Flow<V,E>	Flow on graph edges.
IFlow	Flow on IntGraph edges.
IMatching	A matching in a IntGraph.
IPath	A path of edges in an int graph.
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.
KEdgeConnectedComponentsAlgo.Builder	A builder for KEdgeConnectedComponentsAlgo objects.
KShortestPathsST	An algorithm for computing the K shortest paths between two vertices in a graph.
KShortestPathsST.Builder	A builder for KShortestPathsST objects.
KVertexConnectedComponentsAlgo	Finds the k-vertex connected components of a graph.
KVertexConnectedComponentsAlgo.Builder	A builder for KVertexConnectedComponentsAlgo objects.
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.Builder	A builder for LowestCommonAncestorOffline objects.
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.Builder	A builder for LowestCommonAncestorStatic objects.
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.
MinimumDirectedSpanningTree.Builder	A builder for MinimumDirectedSpanningTree objects.
MinimumEdgeCutAllST	Minimum Edge-Cut algorithm that finds all minimum edge-cuts in a graph between two terminal vertices (source-sink, S-T).
MinimumEdgeCutAllST.Builder	A builder for MinimumEdgeCutAllST objects.
MinimumEdgeCutGlobal	Global Minimum Edge-Cut algorithm without terminal vertices.
MinimumEdgeCutGlobal.Builder	A builder for MinimumEdgeCutGlobal objects.
MinimumEdgeCutST	Minimum Edge-Cut algorithm with terminal vertices (source-sink, S-T).
MinimumEdgeCutST.Builder	A builder for MinimumEdgeCutST objects.
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).
MinimumVertexCutAllGlobal.Builder	A builder for MinimumVertexCutAllGlobal objects.
MinimumVertexCutAllST	Minimum Vertex-Cut algorithm that finds all minimum vertex-cuts in a graph between two terminal vertices (source-sink, S-T).
MinimumVertexCutAllST.Builder	A builder for MinimumVertexCutAllST objects.
MinimumVertexCutGlobal	Minimum Vertex-Cut algorithm without terminal vertices.
MinimumVertexCutGlobal.Builder	A builder for MinimumVertexCutGlobal objects.
MinimumVertexCutST	Minimum Vertex-Cut algorithm with terminal vertices (source-sink, S-T).
MinimumVertexCutST.Builder	A builder for MinimumVertexCutST objects.
Path<V,E>	A path of edges in a graph.
RandomizedAlgorithm	Randomized algorithm interface.
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.
SimplePathsEnumerator.Builder	A builder for SimplePathsEnumerator objects.
SteinerTreeAlgo	An algorithm for the Steiner tree problem.
SteinerTreeAlgo.Builder	A builder for SteinerTreeAlgo objects.
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.Builder	A builder for TopologicalOrderAlgo objects.
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.
VertexCover.Builder	A builder for VertexCover algorithms.
VertexPartition<V,E>	A partition of the vertices of a graph.
VoronoiAlgo	Voronoi cells algorithm.
VoronoiAlgo.Builder	A builder for VoronoiAlgo algorithms.
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.
WeaklyConnectedComponentsAlgo.Builder	A builder for WeaklyConnectedComponentsAlgo objects.

Class Summary

Class	Description
BipartiteGraphs	Static class for bipartite graphs.
GraphsUtils	Static methods class for 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.