Package it.unimi.dsi.webgraph
Class EFGraph
java.lang.Object
it.unimi.dsi.webgraph.ImmutableGraph
it.unimi.dsi.webgraph.EFGraph
- All Implemented Interfaces:
it.unimi.dsi.lang.FlyweightPrototype<ImmutableGraph>
An immutable graph based on the Elias–Fano representation of monotone sequences.
- Author:
- Sebastiano Vigna
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprotected static final classprotected static final classprotected static final classprotected static final classstatic final classNested classes/interfaces inherited from class it.unimi.dsi.webgraph.ImmutableGraph
ImmutableGraph.LoadMethod -
Field Summary
FieldsModifier and TypeFieldDescriptionprotected final CharSequenceThe basename of this graph (or possiblynull).protected intIf notInteger.MIN_VALUE, the node whose degree is cached incachedOutdegree.protected intIfcachedNodeis notInteger.MIN_VALUE, its cached outdegree.protected longIfcachedNodeis notInteger.MIN_VALUE, the position immediately after the coding of the outdegree ofcachedNode.static final intThe default size of the bit cache.static final intThe default base-two logarithm of the quantum.static final intThis number classifies the present graph format.protected final it.unimi.dsi.fastutil.longs.LongBigListThe list containing the graph.static final StringThe standard extension for the graph longword bit stream.protected final intThe base-two logarithm of the indexing quantum.protected final longThe number of arcs of the graph.protected final intThe number of nodes of the graph.protected final it.unimi.dsi.fastutil.longs.LongBigListAn Elias–Fano monotone list containing the pointers of the bit streams stored ingraph.static final StringThe standard extension for the cachedLongBigListcontaining the graph offsets.static final StringThe standard extension for the graph-offsets bit stream.protected final EFGraph.LongWordBitReaderA longword bit reader used to read outdegrees.protected final intThe upper bound used during the graph construction (greater than or equal ton.Fields inherited from class it.unimi.dsi.webgraph.ImmutableGraph
GRAPHCLASS_PROPERTY_KEY, NUMBER_OF_THREADS_PROPERTY, PROPERTIES_EXTENSION -
Constructor Summary
ConstructorsModifierConstructorDescriptionprotectedEFGraph(CharSequence basename, int n, long m, int upperBound, int log2Quantum, it.unimi.dsi.fastutil.longs.LongBigList graph, it.unimi.dsi.fastutil.longs.LongBigList offsets) -
Method Summary
Modifier and TypeMethodDescriptionbasename()Returns a symbolic basename for this graph (optional operation).copy()Returns a flyweight copy of this immutable graph.booleanWhether the node iterators returned by this graph supportNodeIterator.copy(int).static EFGraphload(CharSequence basename) Creates a newEFGraphby loading a compressed graph file from disk to memory, with no progress logger and all offsets.static EFGraphload(CharSequence basename, it.unimi.dsi.logging.ProgressLogger pl) Creates a newEFGraphby loading a compressed graph file from disk to memory, with all offsets.protected static EFGraphloadInternal(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.LongBigArrayBigListloadLongBigList(CharSequence filename, ByteOrder byteOrder) Commodity method for loading a big list of binary longs with specified endianness into a long big array.static EFGraphloadMapped(CharSequence basename) Creates a newEFGraphby memory-mapping a graph file.static EFGraphloadMapped(CharSequence basename, it.unimi.dsi.logging.ProgressLogger pl) Creates a newEFGraphby memory-mapping a graph file.static EFGraphloadOffline(CharSequence basename) Creates a newEFGraphby loading just the metadata of a compressed graph file.static EFGraphloadOffline(CharSequence basename, it.unimi.dsi.logging.ProgressLogger pl) Creates a newEFGraphby loading just the metadata of a compressed graph file.static EFGraphloadSequential(CharSequence basename) Deprecated.static EFGraphloadSequential(CharSequence basename, it.unimi.dsi.logging.ProgressLogger pl) Deprecated.static intlowerBits(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 voidlongnumArcs()Returns the number of arcs of this graph (optional operation).static longnumberOfPointers(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.intnumNodes()Returns the number of nodes of this graph.intoutdegree(int x) Returns the outdegree of a node.static intpointerSize(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.booleanChecks whether this graph provides random access to successor lists.static voidstore(ImmutableGraph graph, int upperBound, CharSequence basename, int log2Quantum, int cacheSize, ByteOrder byteOrder, it.unimi.dsi.logging.ProgressLogger pl) static voidstore(ImmutableGraph graph, int upperBound, CharSequence basename, it.unimi.dsi.logging.ProgressLogger pl) static voidstore(ImmutableGraph graph, CharSequence basename) static voidstore(ImmutableGraph graph, CharSequence basename, int log2Quantum, int cacheSize, ByteOrder byteOrder, it.unimi.dsi.logging.ProgressLogger pl) static voidstore(ImmutableGraph graph, CharSequence basename, it.unimi.dsi.logging.ProgressLogger pl) 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
-
Field Details
-
GRAPH_EXTENSION
The standard extension for the graph longword bit stream.- See Also:
-
OFFSETS_EXTENSION
The standard extension for the graph-offsets bit stream.- See Also:
-
OFFSETS_BIG_LIST_EXTENSION
The standard extension for the cachedLongBigListcontaining the graph offsets.- See Also:
-
DEFAULT_CACHE_SIZE
public static final int DEFAULT_CACHE_SIZEThe default size of the bit cache.- See Also:
-
EFGRAPH_VERSION
public static final int EFGRAPH_VERSIONThis 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:
-
DEFAULT_LOG_2_QUANTUM
public static final int DEFAULT_LOG_2_QUANTUMThe default base-two logarithm of the quantum.- See Also:
-
n
protected final int nThe number of nodes of the graph. -
upperBound
protected final int upperBoundThe upper bound used during the graph construction (greater than or equal ton. -
m
protected final long mThe number of arcs of the graph. -
graph
protected final it.unimi.dsi.fastutil.longs.LongBigList graphThe list containing the graph. -
offsets
protected final it.unimi.dsi.fastutil.longs.LongBigList offsetsAn Elias–Fano monotone list containing the pointers of the bit streams stored ingraph. -
basename
The basename of this graph (or possiblynull). -
outdegreeLongWordBitReader
A longword bit reader used to read outdegrees. -
log2Quantum
protected final int log2QuantumThe base-two logarithm of the indexing quantum. -
cachedNode
protected int cachedNodeIf notInteger.MIN_VALUE, the node whose degree is cached incachedOutdegree. -
cachedOutdegree
protected int cachedOutdegreeIfcachedNodeis notInteger.MIN_VALUE, its cached outdegree. -
cachedPointer
protected long cachedPointerIfcachedNodeis notInteger.MIN_VALUE, the position immediately after the coding of the outdegree ofcachedNode.
-
-
Constructor Details
-
EFGraph
protected EFGraph(CharSequence basename, int n, long m, int upperBound, int log2Quantum, it.unimi.dsi.fastutil.longs.LongBigList graph, it.unimi.dsi.fastutil.longs.LongBigList offsets)
-
-
Method Details
-
basename
Description copied from class:ImmutableGraphReturns a symbolic basename for this graph (optional operation).- Overrides:
basenamein classImmutableGraph- 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
Creates a newEFGraphby 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
EFGraphcontaining the specified graph. - Throws:
IOException- if an I/O exception occurs while reading the graph.
-
load
public static EFGraph load(CharSequence basename, it.unimi.dsi.logging.ProgressLogger pl) throws IOException Creates a newEFGraphby 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, ornull.- Returns:
- a
EFGraphcontaining the specified graph. - Throws:
IOException- if an I/O exception occurs while reading the graph.
-
loadMapped
Creates a newEFGraphby memory-mapping a graph file.- Parameters:
basename- the basename of the graph.- Returns:
- an
EFGraphcontaining 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, it.unimi.dsi.logging.ProgressLogger pl) throws IOException Creates a newEFGraphby memory-mapping a graph file.- Parameters:
basename- the basename of the graph.pl- a progress logger used while loading the offsets, ornull.- Returns:
- an
EFGraphcontaining 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, it.unimi.dsi.logging.ProgressLogger pl) throws IOException Deprecated.Creates a newEFGraphby 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, ornull.- Returns:
- a
EFGraphcontaining the specified graph. - Throws:
IOException- if an I/O exception occurs while reading the graph.
-
loadSequential
Deprecated.UseloadOffline(CharSequence)orloadMapped(CharSequence)instead.Creates a newEFGraphby 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
EFGraphcontaining the specified graph. - Throws:
IOException
-
loadOffline
public static EFGraph loadOffline(CharSequence basename, it.unimi.dsi.logging.ProgressLogger pl) throws IOException Creates a newEFGraphby loading just the metadata of a compressed graph file.- Parameters:
basename- the basename of the graph.pl- a progress logger, ornull.- Returns:
- a
EFGraphcontaining the specified graph. - Throws:
IOException- if an I/O exception occurs while reading the metadata.
-
loadOffline
Creates a newEFGraphby loading just the metadata of a compressed graph file.- Parameters:
basename- the basename of the graph.- Returns:
- a
EFGraphcontaining the specified graph. - Throws:
IOException- if an I/O exception occurs while reading the metadata.
-
loadLongBigList
public static it.unimi.dsi.fastutil.longs.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, it.unimi.dsi.logging.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, ornull.- Returns:
- this graph.
- Throws:
IOException
-
store
public static void store(ImmutableGraph graph, int upperBound, CharSequence basename, it.unimi.dsi.logging.ProgressLogger pl) throws IOException - Throws:
IOException
-
store
public static void store(ImmutableGraph graph, CharSequence basename, it.unimi.dsi.logging.ProgressLogger pl) throws IOException - Throws:
IOException
-
store
- Throws:
IOException
-
store
public static void store(ImmutableGraph graph, CharSequence basename, int log2Quantum, int cacheSize, ByteOrder byteOrder, it.unimi.dsi.logging.ProgressLogger pl) throws IOException - Throws:
IOException
-
store
public static void store(ImmutableGraph graph, int upperBound, CharSequence basename, int log2Quantum, int cacheSize, ByteOrder byteOrder, it.unimi.dsi.logging.ProgressLogger pl) throws IOException - Throws:
IOException
-
numNodes
public int numNodes()Description copied from class:ImmutableGraphReturns the number of nodes of this graph.Albeit this method is not optional, it is allowed that this method throws an
UnsupportedOperationExceptionif this graph has never been entirely traversed using anode iterator. This apparently bizarre behaviour is necessary to support implementations asArcListASCIIGraph, which do not know the actual number of nodes until a traversal has been completed.- Specified by:
numNodesin classImmutableGraph- Returns:
- the number of nodes.
-
numArcs
public long numArcs()Description copied from class:ImmutableGraphReturns the number of arcs of this graph (optional operation).- Overrides:
numArcsin classImmutableGraph- Returns:
- the number of arcs.
-
randomAccess
public boolean randomAccess()Description copied from class:ImmutableGraphChecks whether this graph provides random access to successor lists.- Specified by:
randomAccessin classImmutableGraph- Returns:
- true if this graph provides random access to successor lists.
-
hasCopiableIterators
public boolean hasCopiableIterators()Description copied from class:ImmutableGraphWhether the node iterators returned by this graph supportNodeIterator.copy(int).- Overrides:
hasCopiableIteratorsin classImmutableGraph- Returns:
- true if this graph provides copiable iterators.
-
outdegree
public int outdegree(int x) Description copied from class:ImmutableGraphReturns the outdegree of a node.- Specified by:
outdegreein classImmutableGraph- Parameters:
x- a node.- Returns:
- the outdegree of the given node.
-
successors
Description copied from class:ImmutableGraphReturns a lazy iterator over the successors of a given node. The iteration terminates when -1 is returned.- Overrides:
successorsin classImmutableGraph- Parameters:
x- a node.- Returns:
- a lazy iterator over the successors of the node.
-
copy
Description copied from class:ImmutableGraphReturns a flyweight copy of this immutable graph.- Specified by:
copyin interfaceit.unimi.dsi.lang.FlyweightPrototype<ImmutableGraph>- Specified by:
copyin classImmutableGraph- Returns:
- a flyweight copy of this immutable graph.
- See Also:
-
main
public static void main(String[] args) throws SecurityException, IllegalAccessException, InvocationTargetException, NoSuchMethodException, IOException, com.martiansoftware.jsap.JSAPException, ClassNotFoundException, InstantiationException - Throws:
SecurityExceptionIllegalAccessExceptionInvocationTargetExceptionNoSuchMethodExceptionIOExceptioncom.martiansoftware.jsap.JSAPExceptionClassNotFoundExceptionInstantiationException
-
loadOffline(CharSequence)orloadMapped(CharSequence)instead.