Package it.unimi.dsi.webgraph.algo

Class SampleDistanceCumulativeDistributionFunction

java.lang.Object

it.unimi.dsi.webgraph.algo.SampleDistanceCumulativeDistributionFunction

public class SampleDistanceCumulativeDistributionFunction
extends Object

Samples a graph via breadth-first visits.

Performance issues

This class uses an instance of ParallelBreadthFirstVisit to ensure a high degree of parallelism (see its documentation for memory requirements).

Constructor Summary

Constructors

Constructor	Description
SampleDistanceCumulativeDistributionFunction()

Method Summary

Modifier and Type	Method	Description
static void	main(String[] arg)
protected static int[][]	sample(ImmutableGraph graph, int k, boolean naive, int threads)	Samples a graph via breadth-first visits.
protected static int[][]	sample(ImmutableGraph graph, int k, int threads)	Samples a graph via breadth-first visits.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

SampleDistanceCumulativeDistributionFunction

public SampleDistanceCumulativeDistributionFunction()

Method Details

sample

protected static int[][] sample(ImmutableGraph graph,
int k,
int threads)

Samples a graph via breadth-first visits.

This method will estimate the cumulative distribution function of distances of a strongly connected graph. to which a randomly extracted node belongs. If there is more than one connected component, a warning will be given, specifying the size of the component. An IllegalStateException will be thrown if the algorithm detects that the graph is not strongly connected, but this is not guaranteed to happen.

Parameters:

graph - a graph.

k - a number of samples.

threads - the requested number of threads (0 for Runtime.availableProcessors()).

Returns:

an array of samples.

sample

protected static int[][] sample(ImmutableGraph graph,
int k,
boolean naive,
int threads)

Samples a graph via breadth-first visits.

This method will estimate the cumulative distribution function of distances of a strongly connected graph. If there is more than one connected component, a warning will be given, specifying the size of the component. An IllegalStateException will be thrown if the algorithm detects that the graph is not strongly connected, but this is not guaranteed to happen.

Parameters:

graph - a graph.

k - a number of samples.

naive - sample naively: do not stop sampling even when detecting the lack of strong connection.

threads - the requested number of threads (0 for Runtime.availableProcessors()).

Returns:

an array of samples.

main

public static void main(String[] arg)
                 throws IOException,
JSAPException

Throws:

IOException

JSAPException