JGAlgo library offers a diverse collection of graph algorithms that operate on a Graph object as input. From finding the shortest paths and maximum flows to computing minimum spanning trees, vertex covers, and cycle detection, the library provides a comprehensive set of optimized algorithms solving these problems.

Shortest Path

The Shortest Path family of algorithms deals with finding the shortest paths between vertices in a graph, where 'shortest' is defined with respect to a weight function that assign a real value to each edge, and the 'length' (or 'weight') of a path is its edge weights sum.

• Single Source (SSSP): Computes the shortest paths from a given source vertex to all other vertices in the graph using algorithms like Dijkstra's or Dial's algorithms for positive weights and Bellman-Ford's or Goldberg's algorithms if some of the weights are negative. It provides the shortest path distances and paths from the source vertex to all other vertices.
  [javadoc]

• All Pairs (APSP): Calculates the shortest paths between all pairs of vertices in the graph. It provides the shortest paths and distances between all pairs of vertices. It can also be run on a subset of vertices and compute the shortest paths between each pair of vertices contained in the subset.
  [javadoc] 

• S-T: Finds the shortest path from a specified source vertex `S` to a target vertex `T` [javadoc]. There is also a variant that can utilize a user-heuristic of the distant to `T` to optimize the search.
  [javadoc]

• K Shortest Paths S-T: Finds the `k` shortest loopless paths from a specified source vertex `S` to a target vertex `T`.
  [javadoc]

• Voronoi Cells: Computes the Voronoi cells of a set of points in a graph. The Voronoi cell of a point is the set of vertices in the graph that are closer to this point than to any other point in the set.
  [javadoc]

• Chinese Postman Problem: Solves the Chinese Postman Problem to find the shortest closed walk that traverses each edge at least once with respect to a weight function.
  [javadoc]

• Traveling Salesman Problem Approximation: Approximates the Traveling Salesman Problem to find a near-optimal tour that visits all vertices and returns to the starting point. It uses algorithms like Christofide's algorithm that uses perfect minimum matching.
  [javadoc]

Matching

Matching is a set of edges without common vertices.

• Maximum Matching: Computes the maximum cardinality matching in an undirected graph.
  [javadoc] 

• Maximum/Minimum Weighted (Perfect) Matching: Determines the maximum/minimum-weighted (optionally perfect) matching in an undirected graph using algorithms like the Blossom algorithm.
  [javadoc] 

Flow

Flow network is mapping of each directed edge in a graph to capacity and flow amount values. The amount of flow on an edge cannot exceed the capacity of the edge. An amount of flows along edges entering a vertex should be equal to the amount of flows along edges exiting it, except special vertices such as source and sink.

Algorithms of flow problem solve questions such as 'what is maximum flow that can be passed through the network from a source(s) to a sink(s)?'.

• Maximum Flow: Calculates the maximum flow in a network graph using algorithms like the Edmonds-Karp or Push-Relabel. It determines the maximum amount of flow that can be sent from a source(s) vertex to a sink(s) vertex through the network while respecting the capacity constraints of the edges.
  [javadoc]

• Minimum Cost Flow: Solves the minimum cost flow problem in a flow network using algorithms like the Cycle canceling, Cost scaling or Network Simplex. It finds the flow with the minimum total cost while satisfying the flow constraints and capacity constraints of the edges. Either a maximum flow with minimum cost is computed between a source(s) and a sink(s), or a signed supply function define for each vertex a real value representing the amount of flow it should provide/demand (negative value).
  [javadoc]

Minimum Spanning Tree (MST)

The Minimum Spanning Tree algorithms find the spanning tree (edges subset that maintain the connectivity of the graph) with the minimum weight with respect to a given edge weight function. Both  undirected and directed graphs are supported.
[javadoc]

Cores

Given a graph G=(V,E), a subgraph H induced by a subset of vertices W is a k-core if it is the maximum subgraph in which every vertex has a degree of at least k. The core number of vertex is the highest order of a core that contains this vertex. A cores algorithm can compute the core of a specific k, or the core number of the vertices.
[javadoc]

Cliques

Finds all maximal cliques in an undirected graph using algorithms like the Bron-Kerbosch algorithm. A clique is a set of vertices where every pair of vertices is adjacent, and a maximal clique is a clique that cannot be extended by adding more vertices.
[javadoc]

Coloring

The Coloring family of algorithms is concerned with finding the minimum number of colors needed to color the vertices of an undirected graph such that no adjacent vertices share the same color.
[javadoc]

Graph Traversal

Traversal algorithms are used to explore the vertices and edges of a graph in a systematic way.

• Breadth-First Search (BFS): Performs a breadth-first search traversal of the graph starting from a specified source vertex. It visits all vertices reachable from the source vertex level by level. Backward BFS iterator is also supported, namely a BFS that use the reverse edges of a directed graph.
  [javadoc]

• Depth-First Search (DFS): Executes a depth-first search traversal of the graph starting from a specified source vertex. It explores as far as possible along each branch before backtracking.
  [javadoc]

• Random Walk: Performs a random walk traversal of the graph starting from a specified source vertex. It explores the graph by randomly choosing an edge from the current vertex and moving to the adjacent vertex. The edges are chosen with uniform probability, or with respect to a weight function.
  [javadoc]

Connectivity and Cuts

The connectivity of a graph is the ability of reaching from one vertex to another use the (maybe directed) edges of the graph.

• (Strongly) Connected Components: Finds the connected components in a undirected graph, or the strongly connected components in a directed graph. A strongly connected component is a subgraph where any two vertices are reachable from each other.
  [javadoc]

• Weakly Connected Components: Identifies the connected components in a directed graph as if the edges were undirected.
  [javadoc]

• Bi-Connected Components: Determines the bi-connected (2-vertex-connected) components of an undirected graph. A bi-connected component is a maximal connected subset of vertices for which if any single one of the vertices would be removed, the component were still connected.
  [javadoc]

• K-(vertex)-Connected Components: Finds the k-connected components of an undirected graph. A k-connected component is a maximal connected subset of vertices for which if any `k-1` vertices would be removed, the component were still connected.
  [javadoc]

• K-Edge-Connected Components: Finds the k-edge-connected components of an undirected graph. A k-edge-connected component is a maximal connected subset of vertices for which if any `k-1` edges would be removed, the component were still connected.
  [javadoc]

• S-T Min Vertex Cut / Local Vertex Connectivity: Computes the minimum vertex cut between two specified vertices `S` and `T`. The minimum vertex cut is the set of vertices with minimum weight sum that can be removed such that `S` and `T` are not connected. The unweighted version of the problem is the *local vertex connectivity* between two vertices, namely how many vertices we must remove such that `S` and `T` are not connected. [javadoc] There is also a variant that finds *all* minimum vertex-cuts between two vertices.[javadoc]

• Min Vertex Cut / Global Vertex Connectivity: Finds the minimum vertex cut that partitions the graph into two disjoint sets with the smallest sum of vertex weights. The unweighted version of the problem is the *global vertex connectivity*, namely how many vertices we must remove such that the graph is not connected.  [javadoc] There is also a variant that finds *all* minimum vertex-cuts in the graph.[javadoc]

• S-T Min Edge Cut / Local Edge Connectivity: Computes the minimum cut between two specified vertices `S` and `T` using algorithms like the Stoer-Wagner algorithm. The minimum cut is the minimum weight of a cut that partitions the graph into two disjoint sets with respect to a weight function. The unweighted version of the problem is the *local edge connectivity* between two vertices, namely how many edges we must remove such that `S` and `T` are not connected. [javadoc]  There is also a variant that finds *all* minimum cuts between two vertices.[javadoc]

• Min Edge Cut / Global Edge Connectivity: Finds the minimum cut that partitions the graph into two disjoint sets with the smallest sum of edge weights. The unweighted version of the problem is the *global edge connectivity*, namely how many edges we must remove such that the graph is not connected.
  [javadoc]

Covers

• Vertex Cover: Computes the minimum (weighted) vertex cover in an undirected graph using algorithms like Bar-Yehuda. A vertex cover is a set of vertices such that every edge in the graph is incident to at least one vertex in the set.
  [javadoc]

• Edge Cover: Computes the minimum (weighted) edge cover in an undirected graph. An edge cover is a set of edges such that every vertex in the graph is incident to at least one edge in the set.
  [javadoc]

• Dominating Set: Computes the minimum (weighted) dominating set in graph. A dominating set is a set of vertices such that every vertex in the graph is either in the set or adjacent to a vertex in the set. The dominance can be define with respect to any of out/in/out+in edges.
  [javadoc]

Cycles

Cycles algorithms involves finding cycles in a graph.

• Minimum Mean Cycle: Finds the cycle in the graph with the minimum mean edge weight with respect to some weight function.
  [javadoc]

• Cycle Enumeration: Iterate over the simple cycle in a directed graph using algorithms like the Tarjan or Johnson's cycle finding algorithm.
  [javadoc]

Lowest Common Ancestor (LCA)

Given a tree, the least common ancestor of two vertices is the common ancestor of both vertices (contained in the paths from the vertices to the root) and is the furthest from the root (lowest).

• Offline: The algorithm receive both the graph and the set of queries in advance, and it is require to answer these queries along.
  [javadoc]

• Static: Preprocesses the tree once, and can answer any LCA queries efficient afterwards. The static LCA algorithm uses Euler tour and RMQ (Range Minimum Query) to find the lowest common ancestor of two vertices in a tree efficiently.
  [javadoc]

• Dynamic: support efficient queries of LCA while allowing adding new leaves to the tree.
  [javadoc]

Isomorphism

Given two graphs, an isomorphic mapping is a mapping between the vertices of the two graphs while preserving the structure of the graph. There are a few variants of the problem:

• Full Isomorphism: An isomorphic bijective mapping between the vertices of the two graphs such that there is an edge between two vertices in one graph if and only if there is an edge between the corresponding vertices in the other graph.

• Induced Subgraph Isomorphism: An isomorphic injective mapping between the vertices of the first (smaller) graph to the vertices of the second (larger) graph such that there is an edge between two vertices in the first graph if and only if there is an edge between the corresponding vertices in the second graph.

• Subgraph Isomorphism: An isomorphic injective mapping between the vertices of the first (smaller) graph to the vertices of the second (larger) graph such that if there is an edge between two vertices in the first graph than there is an edge between the corresponding vertices in the second graph.

All The variants are supported by the library using algorithms like the VF2 algorithm.
[javadoc]