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 breadth-first visits.
ConnectedComponents	Computes the connected components of a symmetric (a.k.a. undirected) graph using a parallel breadth-first visit.
EliasFanoCumulativeOutdegreeList	A content-addressable representation of the cumulative function of outdegrees that uses a stripped-down implementation of Elias–Fano's representation of monotone sequences partially taken from EliasFanoMonotoneLongBigList.
FourSweepIterativeFringeDiameter	Deprecated. Superseded by SumSweepDirectedDiameterRadius/SumSweepUndirectedDiameterRadius.
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 breadth-first 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 the Int2DoubleFunction.get(int) method must be actually implemented).
NeighbourhoodFunction	Computes the neighbourhood function of a graph by multiple parallel breadth-first visits.
ParallelBreadthFirstVisit	Performs breadth-firsts visits of a graph exploiting multicore parallelism.
SampleDistanceCumulativeDistributionFunction	Samples a graph via breadth-first 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 64-bit integer arithmetic.