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. Multiple variants are implemented, such as single source (SSSP), all pairs (APSP), S-T, K shortest paths between S-T, Voronoi cells, Chinese postman problem, TSP, ect.
[javadoc]

Matching

Matching is a set of edges without common vertices. Algorithms that find a matching with maximum/minimum edges/weight are available.
[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. There is also definition for undirected graphs used in the library.
[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]

Connectivity and Cuts

The connectivity of a graph is the ability of reaching from one vertex to another using the (maybe directed) edges of the graph. Available algorithms include strongly/weakly connected components, bi-connected components, k-vertex/edge connected components, min global/local(S-T) vertex/edge cut.
[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]

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 and Independent Sets

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. Finding all maximal independent sets is also implemented by computing the maximal cliques in the complement graph.
[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.

• 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.

• 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]

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.

• 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.

• 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.

• 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). Multiple variant exists, such as 'offline' where the algorithm receive both the graph and the set of queries in advance, and it is require to answer these queries along, 'static' where the algo preprocess the tree once, and can answer any LCA queries efficient afterwards, and the 'dynamic' that support efficient queries of LCA while allowing adding new leaves to the tree.
[javadoc]