Package it.unimi.dsi.webgraph.algo
Classes implementing useful algorithms on graphs.

Class Summary Class Description ApproximateNeighbourhoodFunctions Static methods and objects that manipulate approximate neighbourhood functions.BetweennessCentrality Computes the betweenness centrality using an implementation of Brandes's algorithm (Ulrik Brandes, “A Faster Algorithm for Betweenness Centrality”, Journal of Mathematical Sociology 25(2):163−177, 2001) that uses multiple parallel breadthfirst visits.ConnectedComponents Computes the connected components of a symmetric (a.k.a. undirected) graph using a parallel breadthfirst visit.EliasFanoCumulativeOutdegreeList A contentaddressable representation of the cumulative function of outdegrees that uses a strippeddown implementation of Elias–Fano's representation of monotone sequences partially taken fromEliasFanoMonotoneLongBigList
.FourSweepIterativeFringeDiameter Deprecated. GeometricCentralities Computes exactly a set of positive geometric centralitites (more precisely, closeness, Lin's, harmonic and exponential centrality) and the number of reachable nodes using multiple parallel breadthfirst visits.HyperBall Computes an approximation of the neighbourhood function, of the size of the reachable sets, and of (discounted) positive geometric centralities of a graph using HyperBall.HyperBall.AbstractDiscountFunction An abstract discount function is a facility to implement a discount function (so that only theInt2DoubleFunction.get(int)
method must be actually implemented).NeighbourhoodFunction Computes the neighbourhood function of a graph by multiple parallel breadthfirst visits.ParallelBreadthFirstVisit Performs breadthfirsts visits of a graph exploiting multicore parallelism.SampleDistanceCumulativeDistributionFunction Samples a graph via breadthfirst visits.StronglyConnectedComponents Computes the strongly connected components (and optionally the buckets) of an immutable graph.SumSweepDirectedDiameterRadius Computes the radius and/or the diameter and/or all eccentricities of a graph, using the SumSweep algorithm described by Michele Borassi, Pierluigi Crescenzi, Michel Habib, Walter A.SumSweepUndirectedDiameterRadius Computes the radius and/or the diameter and/or all eccentricities of an undirected graph, using the SumSweep algorithm described by Michele Borassi, Pierluigi Crescenzi, Michel Habib, Walter A.TopKGeometricCentrality Computes the k most central vertices according to a positive geometric centrality. 
Enum Summary Enum Description SumSweepDirectedDiameterRadius.OutputLevel The type of output requested: radius, diameter, radius and diameter, all forward eccentricities, or all (forward and backward) eccentricities.SumSweepUndirectedDiameterRadius.OutputLevel The type of output requested: radius, diameter, radius and diameter, or all eccentricities.TopKGeometricCentrality.Centrality The centralities with respect to which it is possible to find the top k nodes. 
Exception Summary Exception Description BetweennessCentrality.PathCountOverflowException An exception telling that the path count exceeded 64bit integer arithmetic.
SumSweepDirectedDiameterRadius
/SumSweepUndirectedDiameterRadius
.