Package it.unimi.dsi.webgraph.algo
package it.unimi.dsi.webgraph.algo
Classes implementing useful algorithms on graphs.
-
ClassDescriptionStatic methods and objects that manipulate approximate neighbourhood functions.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.An exception telling that the path count exceeded 64-bit integer arithmetic.Computes the connected components of a symmetric (a.k.a. undirected) graph using a parallel breadth-first visit.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
.Deprecated.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.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.An abstract discount function is a facility to implement a discount function (so that only theInt2DoubleFunction.get(int)
method must be actually implemented).Computes the neighbourhood function of a graph by multiple parallel breadth-first visits.Performs breadth-firsts visits of a graph exploiting multicore parallelism.Samples a graph via breadth-first visits.Computes the strongly connected components (and optionally the buckets) of an immutable graph.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.The type of output requested: radius, diameter, radius and diameter, all forward eccentricities, or all (forward and backward) eccentricities.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.The type of output requested: radius, diameter, radius and diameter, or all eccentricities.Computes the k most central vertices according to a positive geometric centrality.The centralities with respect to which it is possible to find the top k nodes.
SumSweepDirectedDiameterRadius
/SumSweepUndirectedDiameterRadius
.