Package com.jgalgo.graph

package com.jgalgo.graph
Graphs object are the fundamental building blocks of the JGAlgo library.

A graph is a collection of vertices (nodes) and edges (links) between them. The edges may be directed or undirected. The Graph object represent a graph, in which vertices and edges are hashable identifiers. Vertices can be added or removed to/from a graph, and edges can be added or removed between vertices. The Graph object also provides methods to query the graph, such as the number of vertices and edges, and whether a vertex is connected to another vertex, the out-edges or in-edges of a vertex, etc.

Weights can be associated with the vertices or edges of a graph, and the Graph object provides methods to add or remove weights to it. When a weight is added to the vertices, it is added to all vertices of the graph. The weights can be an Object or any other primitive such as int, double, etc. When weights are added to a graph via the Graph.addVerticesWeights(String, Class) or Graph.addEdgesWeights(String, Class) methods, a Weights object is created and return, which allow setting and getting the weights values by vertex/edge identifier. If the weights type is primitive, a specific subclass of Weights such as WeightsInt, WeightsDouble, etc. is returned. These specific primitive weights containers avoid the overhead of boxing and unboxing primitive values.

Each Graph object expose an IndexGraph via the Graph.indexGraph() method. An index graph is a graph in which the identifiers of the vertices are always in the range [0, n), where n is the number of vertices in the graph, and the identifiers of the edges are always in the range [0, m), where m is the number of edges in the graph. Index graphs are much more efficient than regular graphs, as simple arrays are enough to store the data (internal and additional weights) associated with the vertices/edges. When a vertex or edge is removed from an index graph, some identifiers may change, as it must maintain the invariant that the identifiers are always in the range [0, n) and [0, m). This makes the index graph less convenient to use, but much more efficient. The default graph implementation uses an index graph internally, and expose it via the Graph.indexGraph() method. Good written algorithms should accept a regular graph, retrieve its index graph, perform the heavy computation on the index graph, and translate back the result to the regular graph identifiers. Index graphs should rarely be used directly by a user.