Package org.jgrapht.alg

Algorithms provided with JGraphT.

See:
          Description

Class Summary
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 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.
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.
HopcroftKarpBipartiteMatching<V,E> This class is an implementation of the Hopcroft-Karp algorithm which finds a maximum matching in an undirected simple bipartite 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> ...
MinSourceSinkCut<V,E> Given a directed, weighted graph G(V,E).
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> Complements the ConnectivityInspector class with the capability to compute the strongly connected components of a directed graph.
TarjanLowestCommonAncestor<V,E> Used to calculate Tarjan's Lowest Common Ancestors Algorithm
TarjanLowestCommonAncestor.LcaRequestResponse<V>  
TransitiveClosure Constructs the transitive closure of the input graph.
VertexCovers Algorithms to find a vertex cover for a graph.
 

Package org.jgrapht.alg Description

Algorithms provided with JGraphT.



Copyright © 2013. All rights reserved.