Package it.unimi.dsi.webgraph

Class EFGraph

java.lang.Object

it.unimi.dsi.webgraph.ImmutableGraph

it.unimi.dsi.webgraph.EFGraph

All Implemented Interfaces:

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.webgraph.ImmutableGraph

ImmutableGraph.LoadMethod

Field Summary

Fields

Modifier and Type	Field	Description
protected CharSequence	basename	The basename of this graph (or possibly null).
protected int	cachedNode	If not Integer.MIN_VALUE, the node whose degree is cached in cachedOutdegree.
protected int	cachedOutdegree	If cachedNode is not Integer.MIN_VALUE, its cached outdegree.
protected long	cachedPointer	If cachedNode is not Integer.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 LongBigList	graph	The list containing the graph.
static 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 int	n	The number of nodes of the graph.
protected LongBigList	offsets	An Elias–Fano monotone list containing the pointers of the bit streams stored in graph.
static String	OFFSETS_BIG_LIST_EXTENSION	The standard extension for the cached LongBigList containing the graph offsets.
static 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 int	upperBound	The upper bound used during the graph construction (greater than or equal to n.

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

GRAPHCLASS_PROPERTY_KEY, NUMBER_OF_THREADS_PROPERTY, PROPERTIES_EXTENSION

Constructor Summary

Constructors

Modifier	Constructor	Description
protected	EFGraph(CharSequence basename, int n, long m, int upperBound, int log2Quantum, LongBigList graph, LongBigList offsets)

Method Summary

Modifier and Type	Method	Description
CharSequence	basename()	Returns a symbolic basename for this graph (optional operation).
EFGraph	copy()	Returns a flyweight copy of this immutable graph.
boolean	hasCopiableIterators()	Whether the node iterators returned by this graph support NodeIterator.copy(int).
static EFGraph	load(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(CharSequence basename, ProgressLogger pl)	Creates a new EFGraph by loading a compressed graph file from disk to memory, with all offsets.
protected static EFGraph	loadInternal(CharSequence basename, boolean mapped, ProgressLogger pl)	Loads a compressed graph file from disk into this graph.
static LongBigArrayBigList	loadLongBigList(CharSequence filename, ByteOrder byteOrder)	Commodity method for loading a big list of binary longs with specified endianness into a long big array.
static EFGraph	loadMapped(CharSequence basename)	Creates a new EFGraph by memory-mapping a graph file.
static EFGraph	loadMapped(CharSequence basename, ProgressLogger pl)	Creates a new EFGraph by memory-mapping a graph file.
static EFGraph	loadOffline(CharSequence basename)	Creates a new EFGraph by loading just the metadata of a compressed graph file.
static EFGraph	loadOffline(CharSequence basename, ProgressLogger pl)	Creates a new EFGraph by loading just the metadata of a compressed graph file.
static EFGraph	loadSequential(CharSequence basename)	Deprecated. Use loadOffline(CharSequence) or loadMapped(CharSequence) instead.
static EFGraph	loadSequential(CharSequence basename, 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(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.
int	numNodes()	Returns the number of nodes of this graph.
int	outdegree(int 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, int upperBound, CharSequence basename, int log2Quantum, int cacheSize, ByteOrder byteOrder, ProgressLogger pl)
static void	store(ImmutableGraph graph, int upperBound, CharSequence basename, ProgressLogger pl)
static void	store(ImmutableGraph graph, CharSequence basename)
static void	store(ImmutableGraph graph, CharSequence basename, int log2Quantum, int cacheSize, ByteOrder byteOrder, ProgressLogger pl)
static void	store(ImmutableGraph graph, CharSequence basename, ProgressLogger pl)
LazyIntSkippableIterator	successors(int x)	Returns a lazy iterator over the successors of a given node.

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

equals, hashCode, load, loadOnce, nodeIterator, nodeIterator, outdegrees, splitNodeIterators, store, store, successorArray, toString

Methods inherited from class java.lang.Object

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

Field Details

GRAPH_EXTENSION

public static final String GRAPH_EXTENSION

The standard extension for the graph longword bit stream.

See Also:

Constant Field Values

OFFSETS_EXTENSION

public static final String OFFSETS_EXTENSION

The standard extension for the graph-offsets bit stream.

See Also:

Constant Field Values

OFFSETS_BIG_LIST_EXTENSION

public static final 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 int n

The number of nodes of the graph.

upperBound

protected final int 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 LongBigList graph

The list containing the graph.

offsets

protected final LongBigList offsets

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

basename

protected final 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 int cachedNode

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

cachedOutdegree

protected int cachedOutdegree

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

cachedPointer

protected long cachedPointer

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

Constructor Details

EFGraph

protected EFGraph(CharSequence basename,
int n,
long m,
int upperBound,
int log2Quantum,
LongBigList graph,
LongBigList offsets)

Method Details

basename

public CharSequence basename()

Description copied from class: ImmutableGraph

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

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(CharSequence basename)
                    throws 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:

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

load

public static EFGraph load(CharSequence basename,
ProgressLogger pl)
                    throws 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:

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

loadMapped

public static EFGraph loadMapped(CharSequence basename)
                          throws 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:

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

loadMapped

public static EFGraph loadMapped(CharSequence basename,
ProgressLogger pl)
                          throws 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:

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

loadSequential

@Deprecated
public static EFGraph loadSequential(CharSequence basename,
ProgressLogger pl)
                              throws 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:

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

loadSequential

@Deprecated
public static EFGraph loadSequential(CharSequence basename)
                              throws 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:

IOException

loadOffline

public static EFGraph loadOffline(CharSequence basename,
ProgressLogger pl)
                           throws 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:

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

loadOffline

public static EFGraph loadOffline(CharSequence basename)
                           throws 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:

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

loadLongBigList

public static LongBigArrayBigList loadLongBigList(CharSequence filename,
ByteOrder byteOrder)
                                           throws IOException

Commodity method for loading a big list of binary longs with specified endianness into a long big array.

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:

IOException

loadInternal

protected static EFGraph loadInternal(CharSequence basename,
boolean mapped,
ProgressLogger pl)
                               throws 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:

IOException

store

public static void store(ImmutableGraph graph,
int upperBound,
CharSequence basename,
ProgressLogger pl)
                  throws IOException

Throws:

IOException

store

public static void store(ImmutableGraph graph,
CharSequence basename,
ProgressLogger pl)
                  throws IOException

Throws:

IOException

store

public static void store(ImmutableGraph graph,
CharSequence basename)
                  throws IOException

Throws:

IOException

store

public static void store(ImmutableGraph graph,
CharSequence basename,
int log2Quantum,
int cacheSize,
ByteOrder byteOrder,
ProgressLogger pl)
                  throws IOException

Throws:

IOException

store

public static void store(ImmutableGraph graph,
int upperBound,
CharSequence basename,
int log2Quantum,
int cacheSize,
ByteOrder byteOrder,
ProgressLogger pl)
                  throws IOException

Throws:

IOException

numNodes

public int 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.

hasCopiableIterators

public boolean hasCopiableIterators()

Description copied from class: ImmutableGraph

Whether the node iterators returned by this graph support NodeIterator.copy(int).

Overrides:

hasCopiableIterators in class ImmutableGraph

Returns:

true if this graph provides copiable iterators.

outdegree

public int outdegree(int 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 LazyIntSkippableIterator successors(int 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 FlyweightPrototype<ImmutableGraph>

Specified by:

copy in class ImmutableGraph

Returns:

a flyweight copy of this immutable graph.

See Also:

FlyweightPrototype

main

public static void main(String[] args)
                 throws SecurityException,
IllegalAccessException,
InvocationTargetException,
NoSuchMethodException,
IOException,
JSAPException,
ClassNotFoundException,
InstantiationException

Throws:

SecurityException

IllegalAccessException

InvocationTargetException

NoSuchMethodException

IOException

JSAPException

ClassNotFoundException

InstantiationException