Package org.jgrapht.alg
Algorithms provided with JGraphT.
-
Class Summary Class Description 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.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.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 usingClosestFirstIterator
.DirectedNeighborIndex<V,E> Maintains a cache of each vertex's neighbors.EdmondsKarpMaximumFlow<V,E> A flow network is a directed graph where each edge has a capacity and each edge receives a flow.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.HamiltonianCycle This class will deal with finding the optimal or approximately optimal minimum tour (hamiltonian cycle) or commonly known as the Traveling Salesman Problem.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.NeighborIndex<V,E> Maintains a cache of each vertex's neighbors.StoerWagnerMinimumCut<V,E> Implements the Stoer and Wagner minimum cut algorithm.StrongConnectivityInspector<V,E> Complements theConnectivityInspector
class with the capability to compute the strongly connected components of a directed graph.TransitiveClosure Constructs the transitive closure of the input graph.VertexCovers Algorithms to find a vertex cover for a graph.