Package org.jgrapht.alg

Algorithms provided with JGraphT.

See: Description

Interface Summary

Interface	Description
PathValidator<V,E>	May be used to provide external path validations in addition to the basic validations done by KShortestPaths - that the path is from source to target and that it does not contain loops.

Class Summary

Class	Description
AllDirectedPaths<V,E>	A Dijkstra-like algorithm to find all paths between two sets of nodes in a directed graph, with options to search only simple paths and to limit the path length.
AStarShortestPath<V,E>	An implementation of A* shortest path algorithm.
BellmanFordShortestPath<V,E>	Bellman-Ford algorithm: weights could be negative, paths could be constrained by a maximum number of edges.
BiconnectivityInspector<V,E>	Inspects a graph for the biconnectivity property.
BidirectionalDijkstraShortestPath<V,E>	A bidirectional version of Dijkstra's algorithm.
BlockCutpointGraph<V,E>	Definition of a block of a graph in MathWorld. Definition and lemma taken from the article Structure-Based Resilience Metrics for Service-Oriented Networks: Definition 4.5 Let G(V; E) be a connected undirected graph.
BronKerboschCliqueFinder<V,E>	This class implements Bron-Kerbosch clique detection algorithm as it is described in [Samudrala R.,Moult J.:A Graph-theoretic Algorithm for comparative Modeling of Protein Structure; J.Mol.
ChromaticNumber	Allows the chromatic number of a graph to be calculated.
CliqueMinimalSeparatorDecomposition<V,E>	Clique Minimal Separator Decomposition using MCS-M+ and Atoms algorithm as described in Berry et al.
ConnectivityInspector<V,E>	Allows obtaining various connectivity aspects of a graph.
CycleDetector<V,E>	Performs cycle detection on a graph.
DijkstraShortestPath<V,E>	An implementation of Dijkstra's shortest path algorithm using ClosestFirstIterator.
DirectedNeighborIndex<V,E>	Maintains a cache of each vertex's neighbors.
EdmondsBlossomShrinking<V,E>	An implementation of Edmonds Blossom Shrinking algorithm for constructing maximum matchings on graphs.
EulerianCircuit	This algorithm will check whether a graph is Eulerian (hence it contains an Eulerian circuit).
FloydWarshallShortestPaths<V,E>	The Floyd-Warshall algorithm finds all shortest paths (all n^2 of them) in O(n^3) time.
GabowStrongConnectivityInspector<V,E>	Allows obtaining the strongly connected components of a directed graph.
GreedyMultiplicativeSpanner<V,E>	Greedy algorithm for (2k-1)-multiplicative spanner construction (for any integer k >= 1).
HamiltonianCycle	This class will deal with finding the optimal or approximately optimal minimum tour (hamiltonian cycle) or commonly known as the Traveling Salesman Problem.
HopcroftKarpBipartiteMatching<V,E>	This class is an implementation of the Hopcroft-Karp algorithm which finds a maximum matching in an undirected simple bipartite graph.
KosarajuStrongConnectivityInspector<V,E>	Complements the ConnectivityInspector class with the capability to compute the strongly connected components of a directed graph.
KruskalMinimumSpanningTree<V,E>	An implementation of Kruskal's minimum spanning tree algorithm.
KShortestPaths<V,E>	The algorithm determines the k shortest simple paths in increasing order of weight.
KuhnMunkresMinimalWeightBipartitePerfectMatching<V,E>	Kuhn-Munkres algorithm (named in honor of Harold Kuhn and James Munkres) solving assignment problem also known as hungarian algorithm (in the honor of hungarian mathematicians Dénes K?nig and Jen? Egerváry).
KuhnMunkresMinimalWeightBipartitePerfectMatching.KuhnMunkresMatrixImplementation<V,E>	The actual implementation.
MaximumWeightBipartiteMatching<V,E>	This class finds a maximum weight matching of a simple undirected weighted bipartite graph.
MinSourceSinkCut<V,E>	Deprecated Use MinimumSTCutAlgorithm instead
NaiveLcaFinder<V,E>	Find the Lowest Common Ancestor of a directed graph.
NeighborIndex<V,E>	Maintains a cache of each vertex's neighbors.
PrimMinimumSpanningTree<V,E>	An implementation of Prim's algorithm that finds a minimum spanning tree/forest subject to connectivity of the supplied weighted undirected graph.
StoerWagnerMinimumCut<V,E>	Implements the Stoer and Wagner minimum cut algorithm.
StrongConnectivityInspector<V,E>	Deprecated Use KosarajuStrongConnectivityInspector instead.
TarjanLowestCommonAncestor<V,E>	Used to calculate Tarjan's Lowest Common Ancestors Algorithm
TarjanLowestCommonAncestor.LcaRequestResponse<V>	Data transfer object for LCA request and response.
TransitiveClosure	Constructs the transitive closure of the input graph.
TransitiveReduction	An implementation of Harry Hsu's transitive reduction algorithm.
VertexCovers	Deprecated

Package org.jgrapht.alg Description

Algorithms provided with JGraphT.