Package it.unimi.dsi.big.webgraph

Class EFGraph

java.lang.Object

it.unimi.dsi.big.webgraph.ImmutableGraph

it.unimi.dsi.big.webgraph.EFGraph

All Implemented Interfaces:

it.unimi.dsi.lang.FlyweightPrototype<ImmutableGraph>

public class EFGraph
extends ImmutableGraph

An immutable graph based on the Elias–Fano representation of monotone sequences.

Author:

Sebastiano Vigna

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
protected static class	EFGraph.Accumulator
protected static class	EFGraph.EliasFanoSuccessorReader
protected static class	EFGraph.LongWordBitReader
protected static class	EFGraph.LongWordCache
static class	EFGraph.LongWordOutputBitStream

Nested classes/interfaces inherited from class it.unimi.dsi.big.webgraph.ImmutableGraph

ImmutableGraph.LoadMethod

Field Summary

Fields

Modifier and Type	Field	Description
protected java.lang.CharSequence	basename	The basename of this graph (or possibly null).
protected long	cachedNode	If not Long.MIN_VALUE, the node whose degree is cached in cachedOutdegree.
protected long	cachedOutdegree	If cachedNode is not Long.MIN_VALUE, its cached outdegree.
protected long	cachedPointer	If cachedNode is not Long.MIN_VALUE, the position immediately after the coding of the outdegree of cachedNode.
static int	DEFAULT_CACHE_SIZE	The default size of the bit cache.
static int	DEFAULT_LOG_2_QUANTUM	The default base-two logarithm of the quantum.
static int	EFGRAPH_VERSION	This number classifies the present graph format.
protected it.unimi.dsi.fastutil.longs.LongBigList	graph	The list containing the graph.
static java.lang.String	GRAPH_EXTENSION	The standard extension for the graph longword bit stream.
protected int	log2Quantum	The base-two logarithm of the indexing quantum.
protected long	m	The number of arcs of the graph.
protected long	n	The number of nodes of the graph.
protected it.unimi.dsi.fastutil.longs.LongBigList	offsets	An Elias–Fano monotone list containing the pointers of the bit streams stored in graph.
static java.lang.String	OFFSETS_BIG_LIST_EXTENSION	The standard extension for the cached LongBigList containing the graph offsets.
static java.lang.String	OFFSETS_EXTENSION	The standard extension for the graph-offsets bit stream.
protected EFGraph.LongWordBitReader	outdegreeLongWordBitReader	A longword bit reader used to read outdegrees.
protected long	upperBound	The upper bound used during the graph construction (greater than or equal to n.

Fields inherited from class it.unimi.dsi.big.webgraph.ImmutableGraph

GRAPHCLASS_PROPERTY_KEY, NUMBER_OF_THREADS_PROPERTY, PROPERTIES_EXTENSION

Constructor Summary

Constructors

Modifier	Constructor	Description
protected	EFGraph(java.lang.CharSequence basename, long n, long m, long upperBound, int log2Quantum, it.unimi.dsi.fastutil.longs.LongBigList graph, it.unimi.dsi.fastutil.longs.LongBigList offsets)

Method Summary

Modifier and Type	Method	Description
java.lang.CharSequence	basename()	Returns a symbolic basename for this graph (optional operation).
EFGraph	copy()	Returns a flyweight copy of this immutable graph.
static EFGraph	load(java.lang.CharSequence basename)	Creates a new EFGraph by loading a compressed graph file from disk to memory, with no progress logger and all offsets.
static EFGraph	load(java.lang.CharSequence basename, it.unimi.dsi.logging.ProgressLogger pl)	Creates a new EFGraph by loading a compressed graph file from disk to memory, with all offsets.
protected static EFGraph	loadInternal(java.lang.CharSequence basename, boolean mapped, it.unimi.dsi.logging.ProgressLogger pl)	Loads a compressed graph file from disk into this graph.
static it.unimi.dsi.fastutil.longs.LongBigArrayBigList	loadLongBigList(java.lang.CharSequence filename, java.nio.ByteOrder byteOrder)	Commodity method for loading a big list of binary longs with specified endianness into a long big array which just delegates to EFGraph.loadLongBigList(CharSequence, ByteOrder).
static EFGraph	loadMapped(java.lang.CharSequence basename)	Creates a new EFGraph by memory-mapping a graph file.
static EFGraph	loadMapped(java.lang.CharSequence basename, it.unimi.dsi.logging.ProgressLogger pl)	Creates a new EFGraph by memory-mapping a graph file.
static EFGraph	loadOffline(java.lang.CharSequence basename)	Creates a new EFGraph by loading just the metadata of a compressed graph file.
static EFGraph	loadOffline(java.lang.CharSequence basename, it.unimi.dsi.logging.ProgressLogger pl)	Creates a new EFGraph by loading just the metadata of a compressed graph file.
static EFGraph	loadSequential(java.lang.CharSequence basename)	Deprecated. Use loadOffline(CharSequence) or loadMapped(CharSequence) instead.
static EFGraph	loadSequential(java.lang.CharSequence basename, it.unimi.dsi.logging.ProgressLogger pl)	Deprecated. Use loadOffline(CharSequence, ProgressLogger) or loadMapped(CharSequence, ProgressLogger) instead.
static int	lowerBits(long length, long upperBound)	Returns the number of lower bits for the Elias–Fano encoding of a list of given length, upper bound and strictness.
static void	main(java.lang.String[] args)
long	numArcs()	Returns the number of arcs of this graph (optional operation).
static long	numberOfPointers(long length, long upperBound, int log2Quantum)	Returns the number of forward or skip pointers to the Elias–Fano encoding of a list of given length, upper bound and strictness.
long	numNodes()	Returns the number of nodes of this graph.
long	outdegree(long x)	Returns the outdegree of a node.
static int	pointerSize(long length, long upperBound)	Returns the size in bits of forward or skip pointers to the Elias–Fano encoding of a list of given length, upper bound and strictness.
boolean	randomAccess()	Checks whether this graph provides random access to successor lists.
static void	store(ImmutableGraph graph, long upperBound, java.lang.CharSequence basename, int log2Quantum, int cacheSize, java.nio.ByteOrder byteOrder, it.unimi.dsi.logging.ProgressLogger pl)
static void	store(ImmutableGraph graph, long upperBound, java.lang.CharSequence basename, it.unimi.dsi.logging.ProgressLogger pl)
static void	store(ImmutableGraph graph, java.lang.CharSequence basename)
static void	store(ImmutableGraph graph, java.lang.CharSequence basename, int log2Quantum, int cacheSize, java.nio.ByteOrder byteOrder, it.unimi.dsi.logging.ProgressLogger pl)
static void	store(ImmutableGraph graph, java.lang.CharSequence basename, it.unimi.dsi.logging.ProgressLogger pl)
LazyLongSkippableIterator	successors(long x)	Returns a lazy iterator over the successors of a given node.

Methods inherited from class it.unimi.dsi.big.webgraph.ImmutableGraph

equals, hasCopiableIterators, hashCode, intNumNodes, load, loadOnce, nodeIterator, nodeIterator, outdegrees, splitNodeIterators, store, store, successorBigArray, toString, wrap, wrap

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Field Detail

GRAPH_EXTENSION

public static final java.lang.String GRAPH_EXTENSION

The standard extension for the graph longword bit stream.

See Also:

Constant Field Values

OFFSETS_EXTENSION

public static final java.lang.String OFFSETS_EXTENSION

The standard extension for the graph-offsets bit stream.

See Also:

Constant Field Values

OFFSETS_BIG_LIST_EXTENSION

public static final java.lang.String OFFSETS_BIG_LIST_EXTENSION

The standard extension for the cached LongBigList containing the graph offsets.

See Also:

Constant Field Values

DEFAULT_CACHE_SIZE

public static final int DEFAULT_CACHE_SIZE

The default size of the bit cache.

See Also:

Constant Field Values

EFGRAPH_VERSION

public static final int EFGRAPH_VERSION

This number classifies the present graph format. When new features require introducing binary incompatibilities, this number is bumped so to ensure that old classes do not try to read graphs they cannot understand.

See Also:

Constant Field Values

DEFAULT_LOG_2_QUANTUM

public static final int DEFAULT_LOG_2_QUANTUM

The default base-two logarithm of the quantum.

See Also:

Constant Field Values

n

protected final long n

The number of nodes of the graph.

upperBound

protected final long upperBound

The upper bound used during the graph construction (greater than or equal to n.

m

protected final long m

The number of arcs of the graph.

graph

protected final it.unimi.dsi.fastutil.longs.LongBigList graph

The list containing the graph.

offsets

protected final it.unimi.dsi.fastutil.longs.LongBigList offsets

An Elias–Fano monotone list containing the pointers of the bit streams stored in graph.

basename

protected final java.lang.CharSequence basename

The basename of this graph (or possibly null).

outdegreeLongWordBitReader

protected final EFGraph.LongWordBitReader outdegreeLongWordBitReader

A longword bit reader used to read outdegrees.

log2Quantum

protected final int log2Quantum

The base-two logarithm of the indexing quantum.

cachedNode

protected long cachedNode

If not Long.MIN_VALUE, the node whose degree is cached in cachedOutdegree.

cachedOutdegree

protected long cachedOutdegree

If cachedNode is not Long.MIN_VALUE, its cached outdegree.

cachedPointer

protected long cachedPointer

If cachedNode is not Long.MIN_VALUE, the position immediately after the coding of the outdegree of cachedNode.

Constructor Detail

EFGraph

protected EFGraph(java.lang.CharSequence basename,
                  long n,
                  long m,
                  long upperBound,
                  int log2Quantum,
                  it.unimi.dsi.fastutil.longs.LongBigList graph,
                  it.unimi.dsi.fastutil.longs.LongBigList offsets)

Method Detail

basename

public java.lang.CharSequence basename()

Description copied from class: ImmutableGraph

Returns a symbolic basename for this graph (optional operation).

Implementors of this class may provide a basename (usually a pathname from which various files storing the graph are stemmed). This method is optional because it is sometimes unmeaningful (e.g., for one-off anonymous classes).

Overrides:

basename in class ImmutableGraph

Returns:

the basename.

lowerBits

public static int lowerBits(long length,
                            long upperBound)

Returns the number of lower bits for the Elias–Fano encoding of a list of given length, upper bound and strictness.

Parameters:

length - the number of elements of the list.

upperBound - an upper bound for the elements of the list.

Returns:

the number of bits for the Elias–Fano encoding of a list with the specified parameters.

pointerSize

public static int pointerSize(long length,
                              long upperBound)

Returns the size in bits of forward or skip pointers to the Elias–Fano encoding of a list of given length, upper bound and strictness.

Parameters:

length - the number of elements of the list.

upperBound - an upper bound for the elements of the list.

Returns:

the size of bits of forward or skip pointers the Elias–Fano encoding of a list with the specified parameters.

numberOfPointers

public static long numberOfPointers(long length,
                                    long upperBound,
                                    int log2Quantum)

Returns the number of forward or skip pointers to the Elias–Fano encoding of a list of given length, upper bound and strictness.

Parameters:

length - the number of elements of the list.

upperBound - an upper bound for the elements of the list.

log2Quantum - the logarithm of the quantum size.

Returns:

an upper bound on the number of skip pointers or the (exact) number of forward pointers.

load

public static EFGraph load(java.lang.CharSequence basename)
                    throws java.io.IOException

Creates a new EFGraph by loading a compressed graph file from disk to memory, with no progress logger and all offsets.

Parameters:

basename - the basename of the graph.

Returns:

a EFGraph containing the specified graph.

Throws:

java.io.IOException - if an I/O exception occurs while reading the graph.

load

public static EFGraph load(java.lang.CharSequence basename,
                           it.unimi.dsi.logging.ProgressLogger pl)
                    throws java.io.IOException

Creates a new EFGraph by loading a compressed graph file from disk to memory, with all offsets.

Parameters:

basename - the basename of the graph.

pl - a progress logger used while loading the graph, or null.

Returns:

a EFGraph containing the specified graph.

Throws:

java.io.IOException - if an I/O exception occurs while reading the graph.

loadMapped

public static EFGraph loadMapped(java.lang.CharSequence basename)
                          throws java.io.IOException

Creates a new EFGraph by memory-mapping a graph file.

Parameters:

basename - the basename of the graph.

Returns:

an EFGraph containing the specified graph.

Throws:

java.io.IOException - if an I/O exception occurs while memory-mapping the graph or reading the offsets.

loadMapped

public static EFGraph loadMapped(java.lang.CharSequence basename,
                                 it.unimi.dsi.logging.ProgressLogger pl)
                          throws java.io.IOException

Creates a new EFGraph by memory-mapping a graph file.

Parameters:

basename - the basename of the graph.

pl - a progress logger used while loading the offsets, or null.

Returns:

an EFGraph containing the specified graph.

Throws:

java.io.IOException - if an I/O exception occurs while memory-mapping the graph or reading the offsets.

loadSequential

@Deprecated
public static EFGraph loadSequential(java.lang.CharSequence basename,
                                     it.unimi.dsi.logging.ProgressLogger pl)
                              throws java.io.IOException

Deprecated.

Use loadOffline(CharSequence, ProgressLogger) or loadMapped(CharSequence, ProgressLogger) instead.

Creates a new EFGraph by loading a compressed graph file from disk to memory, without offsets.

Parameters:

basename - the basename of the graph.

pl - a progress logger used while loading the graph, or null.

Returns:

a EFGraph containing the specified graph.

Throws:

java.io.IOException - if an I/O exception occurs while reading the graph.

loadSequential

@Deprecated
public static EFGraph loadSequential(java.lang.CharSequence basename)
                              throws java.io.IOException

Deprecated.

Use loadOffline(CharSequence) or loadMapped(CharSequence) instead.

Creates a new EFGraph by loading a compressed graph file from disk to memory, with no progress logger and without offsets.

Parameters:

basename - the basename of the graph.

Returns:

a EFGraph containing the specified graph.

Throws:

java.io.IOException - if an I/O exception occurs while reading the graph.

loadOffline

public static EFGraph loadOffline(java.lang.CharSequence basename,
                                  it.unimi.dsi.logging.ProgressLogger pl)
                           throws java.io.IOException

Creates a new EFGraph by loading just the metadata of a compressed graph file.

Parameters:

basename - the basename of the graph.

pl - a progress logger, or null.

Returns:

a EFGraph containing the specified graph.

Throws:

java.io.IOException - if an I/O exception occurs while reading the metadata.

loadOffline

public static EFGraph loadOffline(java.lang.CharSequence basename)
                           throws java.io.IOException

Creates a new EFGraph by loading just the metadata of a compressed graph file.

Parameters:

basename - the basename of the graph.

Returns:

a EFGraph containing the specified graph.

Throws:

java.io.IOException - if an I/O exception occurs while reading the metadata.

loadLongBigList

public static it.unimi.dsi.fastutil.longs.LongBigArrayBigList loadLongBigList(java.lang.CharSequence filename,
                                                                              java.nio.ByteOrder byteOrder)
                                                                       throws java.io.IOException

Commodity method for loading a big list of binary longs with specified endianness into a long big array which just delegates to EFGraph.loadLongBigList(CharSequence, ByteOrder).

Parameters:

filename - the file containing the longs.

byteOrder - the endianness of the longs.

Returns:

a big list of longs containing the longs in filename.

Throws:

java.io.IOException

loadInternal

protected static EFGraph loadInternal(java.lang.CharSequence basename,
                                      boolean mapped,
                                      it.unimi.dsi.logging.ProgressLogger pl)
                               throws java.io.IOException

Loads a compressed graph file from disk into this graph. Note that this method should be called only on a newly created graph.

Parameters:

basename - the basename of the graph.

mapped - whether we want to memory-map the file.

pl - a progress logger used while loading the graph, or null.

Returns:

this graph.

Throws:

java.io.IOException

store

public static void store(ImmutableGraph graph,
                         long upperBound,
                         java.lang.CharSequence basename,
                         it.unimi.dsi.logging.ProgressLogger pl)
                  throws java.io.IOException

Throws:

java.io.IOException

store

public static void store(ImmutableGraph graph,
                         java.lang.CharSequence basename,
                         it.unimi.dsi.logging.ProgressLogger pl)
                  throws java.io.IOException

Throws:

java.io.IOException

store

public static void store(ImmutableGraph graph,
                         java.lang.CharSequence basename)
                  throws java.io.IOException

Throws:

java.io.IOException

store

public static void store(ImmutableGraph graph,
                         java.lang.CharSequence basename,
                         int log2Quantum,
                         int cacheSize,
                         java.nio.ByteOrder byteOrder,
                         it.unimi.dsi.logging.ProgressLogger pl)
                  throws java.io.IOException

Throws:

java.io.IOException

store

public static void store(ImmutableGraph graph,
                         long upperBound,
                         java.lang.CharSequence basename,
                         int log2Quantum,
                         int cacheSize,
                         java.nio.ByteOrder byteOrder,
                         it.unimi.dsi.logging.ProgressLogger pl)
                  throws java.io.IOException

Throws:

java.io.IOException

numNodes

public long numNodes()

Description copied from class: ImmutableGraph

Returns the number of nodes of this graph.

Albeit this method is not optional, it is allowed that this method throws an UnsupportedOperationException if this graph has never been entirely traversed using a node iterator. This apparently bizarre behaviour is necessary to support implementations as ArcListASCIIGraph, which do not know the actual number of nodes until a traversal has been completed.

Specified by:

numNodes in class ImmutableGraph

Returns:

the number of nodes.

numArcs

public long numArcs()

Description copied from class: ImmutableGraph

Returns the number of arcs of this graph (optional operation).

Overrides:

numArcs in class ImmutableGraph

Returns:

the number of arcs.

randomAccess

public boolean randomAccess()

Description copied from class: ImmutableGraph

Checks whether this graph provides random access to successor lists.

Specified by:

randomAccess in class ImmutableGraph

Returns:

true if this graph provides random access to successor lists.

outdegree

public long outdegree(long x)

Description copied from class: ImmutableGraph

Returns the outdegree of a node.

Specified by:

outdegree in class ImmutableGraph

Parameters:

x - a node.

Returns:

the outdegree of the given node.

successors

public LazyLongSkippableIterator successors(long x)

Description copied from class: ImmutableGraph

Returns a lazy iterator over the successors of a given node. The iteration terminates when -1 is returned.

Overrides:

successors in class ImmutableGraph

Parameters:

x - a node.

Returns:

a lazy iterator over the successors of the node.

copy

public EFGraph copy()

Description copied from class: ImmutableGraph

Returns a flyweight copy of this immutable graph.

Specified by:

copy in interface it.unimi.dsi.lang.FlyweightPrototype<ImmutableGraph>

Specified by:

copy in class ImmutableGraph

Returns:

a flyweight copy of this immutable graph.

See Also:

FlyweightPrototype

main

public static void main(java.lang.String[] args)
                 throws java.lang.SecurityException,
                        java.lang.IllegalAccessException,
                        java.lang.reflect.InvocationTargetException,
                        java.lang.NoSuchMethodException,
                        java.io.IOException,
                        com.martiansoftware.jsap.JSAPException,
                        java.lang.ClassNotFoundException,
                        java.lang.InstantiationException

Throws:

java.lang.SecurityException

java.lang.IllegalAccessException

java.lang.reflect.InvocationTargetException

java.lang.NoSuchMethodException

java.io.IOException

com.martiansoftware.jsap.JSAPException

java.lang.ClassNotFoundException

java.lang.InstantiationException