|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectit.unimi.dsi.webgraph.ImmutableGraph
it.unimi.dsi.webgraph.BVGraph
public class BVGraph
An immutable graph represented using the techniques described in “The WebGraph Framework I: Compression Techniques”, by Paolo Boldi and Sebastiano Vigna, in Proc. of the Thirteenth World–Wide Web Conference, pages 595−601, 2004, ACM Press.
This class provides a flexible and configurable way to store and
access web graphs in a compressed form. Its main method can load an
ImmutableGraph
and compress it. The resulting compressed BVGraph
is described by a graph file (with extension
.graph), an offset file (with extension
.offsets) and a property file (with extension
.properties). The latter, not surprisingly, is a Java property file.
Optionally, an offset big-list file (with extension
.obl) can be created to load graphs faster.
As a rule of thumb, random access is faster using successors(int)
, whereas
while iterating using a NodeIterator
it is better to use NodeIterator.successorArray()
.
This class stores a graph as an bit stream. The bit stream format depends on a number of parameters and encodings that can be mixed orthogonally. The parameters are:
The graph file is a sequence of successor lists, one for each node. The list of node x can be thought of as a sequence of natural numbers (even though, as we will explain later, this sequence is further coded suitably as a sequence of bits):
The above data should be interpreted as follows:
As we said before, the list of integers corresponding to each successor list should be coded into a sequence of bits.
This is (ideally) done in two phases: we first modify the sequence in a suitable manner (as explained below) so to obtain
another sequence of integers (some of them might be negative). Then each single integer is coded, using a coding that can
be specified as an option; the integers that may be negative are first turned into natural numbers using Fast.int2nat(int)
.
Since the graph is stored as a bit stream, we must have some way to know where each successor list starts. This information is stored in the offset file, which contains the bit offset of each successor list (in particular, the offset of the first successor list will be zero). As a commodity, the offset file contains an additional offset pointing just after the last successor list (providing, as a side-effect, the actual bit length of the graph file). Each offset (except for the first one) is stored as a suitably coded difference from the previous offset.
The list of offsets can be additionally stored as a serialised EliasFanoMonotoneLongBigList
using a suitable command-line option. If the serialised big list is detected, it is loaded instead of parsing the offset list.
This file contains self-explaining entries that are necessary to correctly decode the graph and offset files, and moreover give some statistical information about the compressed graph (e.g., the number of bits per link).
ImmutableGraph
convention).
Fast.int2nat(int)
, but discarding zeroes (which happen in
very rare circumstance, and should be considered immaterial).
The natural way of using a graph file is to load it into a byte array and
then index its bits using the suitable offset. This class will use a byte
array for graphs smaller than Integer.MAX_VALUE
bytes,
and a FastMultiByteArrayInputStream
otherwise: in the latter case, expect a significant slowdown (as
an InputBitStream
can wrap directly
a byte array).
Offsets are loaded using an EliasFanoMonotoneLongBigList
,
which occupies exponentially less space than the graph itself (unless
your graph is pathologically sparse). There is of course a cost involved in
accessing the list with respect to accessing an array of longs.
Note that by default the EliasFanoMonotoneLongBigList
instance is
created from scratch using the file of offsets. This is a long and tedious
process, in particular with large graphs. The main method of this class
has an option that will generate such a list once for all and serialise it in a file with
extension .obl. The list will be quickly deserialised
if its modification date is later than that of the offset file.
Optionally, this class may load no offsets at all (see loadSequential(CharSequence)
. In this case, the only
way to access the graph is by creating a ImmutableGraph.nodeIterator()
.
For some applications (such as transposing a graph) it is not necessary to load the graph
file in memory. Since this class is able to enumerate the links of a graph without using random
access, it is possible not to load in memory any information at all, and obtain iterators that
directly read from the graph file. To obtain this effect, you must call loadOffline(CharSequence)
.
Another interesting alternative is memory mapping. When using loadMapped(CharSequence)
,
the graph will be mapped into memory, and the offsets loaded. The graph will provide random access and behave
as if it was loaded into memory, but of course the access will be slower.
Nested Class Summary |
---|
Nested classes/interfaces inherited from class it.unimi.dsi.webgraph.ImmutableGraph |
---|
ImmutableGraph.LoadMethod |
Field Summary | |
---|---|
protected CharSequence |
basename
The basename of the graph. |
static int |
BLOCK_COUNT_DELTA
Flag: write block counts using δ coding. |
static int |
BLOCK_COUNT_GAMMA
Flag: write block counts using γ coding (default). |
static int |
BLOCK_COUNT_UNARY
Flag: write block counts using unary coding. |
protected int |
blockCoding
The coding for copy-block lists. |
protected int |
blockCountCoding
The coding for block counts. |
static int |
BLOCKS_DELTA
Flag: write copy-block lists using δ coding. |
static int |
BLOCKS_GAMMA
Flag: write copy-block lists using γ coding (default). |
static int |
BVGRAPH_VERSION
This number classifies the present graph format. |
static int |
DEFAULT_MAX_REF_COUNT
Default backward reference maximum length. |
static int |
DEFAULT_MIN_INTERVAL_LENGTH
Default minimum interval length. |
static int |
DEFAULT_WINDOW_SIZE
Default window size. |
static int |
DEFAULT_ZETA_K
Default value of k. |
static String |
GRAPH_EXTENSION
The standard extension for the graph bit stream. |
protected byte[] |
graphMemory
The byte array storing the compressed graph, if isMemory is true and offsetType is not -1. |
protected FastMultiByteArrayInputStream |
graphStream
The multi-byte array input stream storing the compressed graph, if isMemory is false, isMapped is false and offsetType is not -1. |
protected static int |
INITIAL_SUCCESSOR_LIST_LENGTH
The initial length of an array that will contain a successor list. |
protected boolean |
isMapped
When offsetType is not -1, whether this graph is directly loaded into
graphMemory , or rather memory-mapped. |
protected boolean |
isMemory
When offsetType is not -1, whether this graph is directly loaded into
graphMemory , or rather wrapped in a FastMultiByteArrayInputStream
specified by graphStream . |
protected long |
m
The number of arcs of the graph. |
protected ByteBufferInputStream |
mappedGraphStream
The memory-mapped input stream storing the compressed graph, if isMapped is true. |
protected int |
maxRefCount
The maximum reference count. |
protected int |
minIntervalLength
The minimum interval length. |
protected int |
n
The number of nodes of the graph. |
protected static int |
NO_INTERVALS
A special value for minIntervalLength interpreted as meaning that the minimum interval length is infinity. |
static int |
OFFLINE
The offset step parameter corresponding to offline load. |
protected int |
offsetCoding
The coding for offsets. |
protected LongBigList |
offsets
This variable is null iff offsetType is zero or less
(implying that offsets have not been loaded). |
static String |
OFFSETS_BIG_LIST_EXTENSION
The standard extension for the cached LongBigList containing the graph offsets. |
static int |
OFFSETS_DELTA
Flag: write offsets using δ coding. |
static String |
OFFSETS_EXTENSION
The standard extension for the graph-offsets bit stream. |
static int |
OFFSETS_GAMMA
Flag: write offsets using γ coding (default). |
protected int |
offsetType
The offset type: 2 is memory-mapping, 1 is normal random-access loading, 0 means that we do not want to load offsets at all, -1 that the we do not want even load the graph file. |
protected int |
outdegreeCoding
The coding for outdegrees. |
protected InputBitStream |
outdegreeIbs
A bit stream wrapping graphMemory , or graphStream , used only by
outdegree(int) . |
static int |
OUTDEGREES_DELTA
Flag: write outdegrees using δ coding. |
static String |
OUTDEGREES_EXTENSION
The standard extension for the stream of node outdegrees. |
static int |
OUTDEGREES_GAMMA
Flag: write outdegrees using γ coding (default). |
protected int |
referenceCoding
The coding for references. |
static int |
REFERENCES_DELTA
Flag: write references using δ coding. |
static int |
REFERENCES_GAMMA
Flag: write references using γ coding. |
static int |
REFERENCES_UNARY
Flag: write references using unary coding (default). |
protected int |
residualCoding
The coding for residuals. |
static int |
RESIDUALS_DELTA
Flag: write residuals using δ coding. |
static int |
RESIDUALS_GAMMA
Flag: write residuals using γ coding. |
static int |
RESIDUALS_GOLOMB
Flag: write residuals using &golomb; coding. |
static int |
RESIDUALS_NIBBLE
Flag: write residuals using variable-length nibble coding. |
static int |
RESIDUALS_ZETA
Flag: write residuals using ζk coding (default). |
static int |
SEQUENTIAL
The offset step parameter corresponding to sequential load. |
protected int |
windowSize
The window size. |
protected int |
zetaK
The value of k for ζk coding (for residuals). |
Fields inherited from class it.unimi.dsi.webgraph.ImmutableGraph |
---|
GRAPHCLASS_PROPERTY_KEY, PROPERTIES_EXTENSION |
Fields inherited from interface it.unimi.dsi.webgraph.CompressionFlags |
---|
CODING_NAME, DELTA, GAMMA, GOLOMB, NIBBLE, SKEWED_GOLOMB, UNARY, ZETA |
Constructor Summary | |
---|---|
protected |
BVGraph()
|
Method Summary | |
---|---|
CharSequence |
basename()
Returns a symbolic basename for this graph (optional operation). |
BVGraph |
copy()
Returns a flyweight copy of this immutable graph. |
protected static int |
intervalize(IntArrayList x,
int minInterval,
IntArrayList left,
IntArrayList len,
IntArrayList residuals)
This method tries to express an increasing sequence of natural numbers x as a union of an increasing
sequence of intervals and an increasing sequence of residual elements. |
static BVGraph |
load(CharSequence basename)
Creates a new BVGraph by loading a compressed graph file from disk to memory, with no progress logger and
all offsets. |
static BVGraph |
load(CharSequence basename,
int offsetType)
Creates a new BVGraph by loading a compressed graph file from disk to memory, with no progress logger. |
static BVGraph |
load(CharSequence basename,
int offsetType,
ProgressLogger pl)
Creates a new BVGraph by loading a compressed graph file from disk to memory. |
static BVGraph |
load(CharSequence basename,
ProgressLogger pl)
Creates a new BVGraph by loading a compressed graph file from disk to memory, with
all offsets. |
protected BVGraph |
loadInternal(CharSequence basename,
int offsetType,
ProgressLogger pl)
Loads a compressed graph file from disk into this graph. |
static BVGraph |
loadMapped(CharSequence basename)
Creates a new BVGraph by memory-mapping a graph file. |
static BVGraph |
loadMapped(CharSequence basename,
ProgressLogger pl)
Creates a new BVGraph by memory-mapping a graph file. |
static BVGraph |
loadOffline(CharSequence basename)
Creates a new BVGraph by loading just the metadata of a compressed graph file. |
static BVGraph |
loadOffline(CharSequence basename,
ProgressLogger pl)
Creates a new BVGraph by loading just the metadata of a compressed graph file. |
static BVGraph |
loadSequential(CharSequence basename)
Creates a new BVGraph by loading a compressed graph file from disk to memory, with no progress logger and
without offsets. |
static BVGraph |
loadSequential(CharSequence basename,
ProgressLogger pl)
Creates a new BVGraph by loading a compressed graph file from disk to memory, without offsets. |
static void |
main(String[] args)
Reads an immutable graph and stores it as a BVGraph . |
int |
maxRefCount()
Returns the maximum reference count of this graph. |
NodeIterator |
nodeIterator(int from)
This method returns a node iterator for scanning the graph sequentially, starting from the given node. |
long |
numArcs()
Returns the number of arcs of this graph (optional operation). |
int |
numNodes()
Returns the number of nodes of this graph. |
int |
outdegree(int x)
Returns the outdegree of a node. |
boolean |
randomAccess()
Checks whether this graph provides random access to successor lists. |
protected int |
readBlock(InputBitStream ibs)
Reads a block from the given stream. |
protected int |
readBlockCount(InputBitStream ibs)
Reads a block count from the given stream. |
protected long |
readLongResidual(InputBitStream ibs)
Reads a long residual from the given stream. |
protected long |
readOffset(InputBitStream ibs)
Reads an offset difference from the given stream. |
protected int |
readOutdegree(InputBitStream ibs)
Reads an outdegree from the given stream. |
protected int |
readOutdegree(InputBitStream ibs,
long offset)
Reads an outdegree from the given stream at a given offset. |
protected int |
readReference(InputBitStream ibs)
Reads a reference from the given stream. |
protected int |
readResidual(InputBitStream ibs)
Reads a residual from the given stream. |
static void |
store(ImmutableGraph graph,
CharSequence basename)
Writes the given graph using a given base name, without any progress logger and with all parameters set to their default values. |
static void |
store(ImmutableGraph graph,
CharSequence basename,
int windowSize,
int maxRefCount,
int minIntervalLength,
int zetaK,
int flags)
Writes the given graph using a given base name, without any progress logger. |
static void |
store(ImmutableGraph graph,
CharSequence basename,
int windowSize,
int maxRefCount,
int minIntervalLength,
int zetaK,
int flags,
ProgressLogger pl)
Writes the given graph using a given base name. |
static void |
store(ImmutableGraph graph,
CharSequence basename,
ProgressLogger pl)
Writes the given graph using a given base name, with all parameters set to their default values. |
LazyIntIterator |
successors(int x)
Returns an iterator over the successors of a given node. |
protected LazyIntIterator |
successors(int x,
long offset,
InputBitStream ibs,
int[][] window,
int[] outd)
Given an InputBitStream wrapping a graph file, returns an iterator over the
successors of a given node x . |
int |
windowSize()
Returns the window size of this graph. |
protected int |
writeBlock(OutputBitStream obs,
int block)
Writes a block to the given stream. |
protected int |
writeBlockCount(OutputBitStream obs,
int count)
Writes a block count to the given stream. |
protected int |
writeOffset(OutputBitStream obs,
long x)
Writes an offset difference to the given stream. |
void |
writeOffsets(OutputBitStream obs,
ProgressLogger pl)
Write the offset file to a given bit stream. |
protected int |
writeOutdegree(OutputBitStream obs,
int d)
Writes an outdegree to the given stream. |
protected int |
writeReference(OutputBitStream obs,
int ref)
Writes a reference to the given stream. |
protected int |
writeResidual(OutputBitStream obs,
int residual)
Writes a residual to the given stream. |
protected int |
writeResidual(OutputBitStream obs,
long residual)
Writes a residual to the given stream. |
Methods inherited from class it.unimi.dsi.webgraph.ImmutableGraph |
---|
equals, hashCode, load, loadOnce, nodeIterator, outdegrees, store, store, successorArray, toString |
Methods inherited from class java.lang.Object |
---|
clone, finalize, getClass, notify, notifyAll, wait, wait, wait |
Field Detail |
---|
public static final int SEQUENTIAL
public static final int OFFLINE
public static final String GRAPH_EXTENSION
public static final String OFFSETS_EXTENSION
public static final String OFFSETS_BIG_LIST_EXTENSION
LongBigList
containing the graph offsets.
public static final String OUTDEGREES_EXTENSION
public static final int BVGRAPH_VERSION
protected static final int INITIAL_SUCCESSOR_LIST_LENGTH
protected static final int NO_INTERVALS
minIntervalLength
interpreted as meaning that the minimum interval length is infinity.
protected CharSequence basename
null
, but trying to load the graph with an offset
step of -1 will cause an exception.
protected int n
protected long m
protected boolean isMemory
offsetType
is not -1, whether this graph is directly loaded into
graphMemory
, or rather wrapped in a FastMultiByteArrayInputStream
specified by graphStream
.
protected boolean isMapped
offsetType
is not -1, whether this graph is directly loaded into
graphMemory
, or rather memory-mapped.
protected byte[] graphMemory
isMemory
is true and offsetType
is not -1.
This variable is loaded with a copy of the graph file, or with
a rearrangement of the latter, depending on whether offsetType
is smaller than or equal to one. If
offsetType
is -1, this variable is null
, and node iterators are generated by opening
streams directly on the graph file.
protected FastMultiByteArrayInputStream graphStream
isMemory
is false, isMapped
is false and offsetType
is not -1.
It is loaded with a copy of the graph file. If
offsetType
is -1, this variable is null
, and node iterators are generated by opening
streams directly on the graph file.
protected ByteBufferInputStream mappedGraphStream
isMapped
is true.
It is loaded with a copy of the graph file. If
offsetType
is -1, this variable is null
, and node iterators are generated by opening
streams directly on the graph file.
protected LongBigList offsets
null
iff offsetType
is zero or less
(implying that offsets have not been loaded). Otherwise, it is an
Elias–Fano monotone list containing the pointers of
the bit streams of one each offsetType
nodes.
protected int offsetType
protected int maxRefCount
public static final int DEFAULT_MAX_REF_COUNT
protected int windowSize
public static final int DEFAULT_WINDOW_SIZE
protected int minIntervalLength
public static final int DEFAULT_MIN_INTERVAL_LENGTH
protected int zetaK
public static final int DEFAULT_ZETA_K
public static final int OUTDEGREES_GAMMA
public static final int OUTDEGREES_DELTA
public static final int BLOCKS_GAMMA
public static final int BLOCKS_DELTA
public static final int RESIDUALS_GAMMA
public static final int RESIDUALS_ZETA
public static final int RESIDUALS_DELTA
public static final int RESIDUALS_NIBBLE
public static final int RESIDUALS_GOLOMB
public static final int REFERENCES_GAMMA
public static final int REFERENCES_DELTA
public static final int REFERENCES_UNARY
public static final int BLOCK_COUNT_GAMMA
public static final int BLOCK_COUNT_DELTA
public static final int BLOCK_COUNT_UNARY
public static final int OFFSETS_GAMMA
public static final int OFFSETS_DELTA
protected int outdegreeCoding
protected int blockCoding
protected int residualCoding
protected int referenceCoding
protected int blockCountCoding
protected int offsetCoding
protected InputBitStream outdegreeIbs
graphMemory
, or graphStream
, used only by
outdegree(int)
. It is declared here for efficiency reasons.
Constructor Detail |
---|
protected BVGraph()
Method Detail |
---|
public BVGraph copy()
ImmutableGraph
copy
in interface FlyweightPrototype<ImmutableGraph>
copy
in class ImmutableGraph
FlyweightPrototype
public int numNodes()
ImmutableGraph
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.
numNodes
in class ImmutableGraph
public long numArcs()
ImmutableGraph
numArcs
in class ImmutableGraph
public boolean randomAccess()
ImmutableGraph
randomAccess
in class ImmutableGraph
public CharSequence basename()
ImmutableGraph
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).
basename
in class ImmutableGraph
public int maxRefCount()
public int windowSize()
protected final long readOffset(InputBitStream ibs) throws IOException
ibs
- an offset-file input bit stream.
IOException
protected final int writeOffset(OutputBitStream obs, long x) throws IOException
obs
- an offset-file output bit stream.x
- an offset difference to be stored in the stream.
IOException
protected final int readOutdegree(InputBitStream ibs) throws IOException
ibs
- a graph-file input bit stream.
IOException
protected final int readOutdegree(InputBitStream ibs, long offset) throws IOException
ibs
- a graph-file input bit stream.offset
- the offset at which the stream must be positioned.
IOException
protected final int writeOutdegree(OutputBitStream obs, int d) throws IOException
obs
- a graph-file output bit stream.d
- an outdegree to be stored in the stream.
IOException
protected final int readReference(InputBitStream ibs) throws IOException
ibs
- a graph-file input bit stream.
IOException
protected final int writeReference(OutputBitStream obs, int ref) throws IOException
obs
- a graph-file output bit stream.ref
- the reference.
IOException
protected final int readBlockCount(InputBitStream ibs) throws IOException
ibs
- a graph-file input bit stream.
IOException
protected final int writeBlockCount(OutputBitStream obs, int count) throws IOException
obs
- a graph-file output bit stream.count
- the block count.
IOException
protected final int readBlock(InputBitStream ibs) throws IOException
ibs
- a graph-file input bit stream.
IOException
protected final int writeBlock(OutputBitStream obs, int block) throws IOException
obs
- a graph-file output bit stream.block
- the block.
IOException
protected final int readResidual(InputBitStream ibs) throws IOException
ibs
- a graph-file input bit stream.
IOException
protected final long readLongResidual(InputBitStream ibs) throws IOException
ibs
- a graph-file input bit stream.
IOException
protected final int writeResidual(OutputBitStream obs, int residual) throws IOException
obs
- a graph-file output bit stream.residual
- the residual.
IOException
protected final int writeResidual(OutputBitStream obs, long residual) throws IOException
obs
- a graph-file output bit stream.residual
- the residual.
IOException
public int outdegree(int x) throws IllegalStateException
ImmutableGraph
outdegree
in class ImmutableGraph
x
- a node.
IllegalStateException
- if called without offsets.public LazyIntIterator successors(int x)
successors
in class ImmutableGraph
x
- a node.
protected LazyIntIterator successors(int x, long offset, InputBitStream ibs, int[][] window, int[] outd) throws IllegalStateException
InputBitStream
wrapping a graph file, returns an iterator over the
successors of a given node x
.
This method can be used in two different ways:
This method may modify the offset and the outdegree caches if window
is null
.
x
- a node.offset
- the offset of x
; can be -1 if window
is not null
.ibs
- an input bit stream wrapping a graph file. After this method returns, the state of ibs
is undefined:
however, after the iterator returned is exhausted, ibs
will positioned just after the successor list of x
.window
- either null
, or a double array with the following meaning: window[(x-i) mod windowSize]
contains, for all i
between 1 (inclusive) and windowSize
(exclusive), the list of successors
of node x
−i
. If window
is not null
then ibs
must be positioned before the successor list of x
. This parameter will not be modified.outd
- if window
is not null
, this is an array with as many elements
as windowSize
; outd[(x-i) mod windowSize]
contains the outdegree of node x
−i
for i
greater than 0; at the end, this will be true also for i
equal to 0.
x
.
IllegalStateException
- if window
is null
and offsetType
is 0.public NodeIterator nodeIterator(int from)
windowSize()
previous successor lists
to speed up the iteration of graphs with significant referentiation.
nodeIterator
in class ImmutableGraph
from
- the node from which the iterator will iterate.
NodeIterator
for accessing nodes and successors sequentially.public static BVGraph load(CharSequence basename, int offsetType, ProgressLogger pl) throws IOException
BVGraph
by loading a compressed graph file from disk to memory.
basename
- the basename of the graph.offsetType
- the desired offset type (2 is memory mapping, 1 is normal random-access loading, 0 means that we do not want to load offsets at all, -1 that
the we do not want even load the graph file).pl
- a progress logger used while loading the graph, or null
.
BVGraph
containing the specified graph.
IOException
- if an I/O exception occurs while reading the graph.public static BVGraph load(CharSequence basename, int offsetType) throws IOException
BVGraph
by loading a compressed graph file from disk to memory, with no progress logger.
basename
- the basename of the graph.offsetType
- the desired offset type (2 is memory mapping, 1 is normal random-access loading, 0 means that we do not want to load offsets at all, -1 that
the we do not want even load the graph file).
BVGraph
containing the specified graph.
IOException
- if an I/O exception occurs while reading the graph.public static BVGraph load(CharSequence basename) throws IOException
BVGraph
by loading a compressed graph file from disk to memory, with no progress logger and
all offsets.
basename
- the basename of the graph.
BVGraph
containing the specified graph.
IOException
- if an I/O exception occurs while reading the graph.public static BVGraph load(CharSequence basename, ProgressLogger pl) throws IOException
BVGraph
by loading a compressed graph file from disk to memory, with
all offsets.
basename
- the basename of the graph.pl
- a progress logger used while loading the graph, or null
.
BVGraph
containing the specified graph.
IOException
- if an I/O exception occurs while reading the graph.public static BVGraph loadMapped(CharSequence basename, ProgressLogger pl) throws IOException
BVGraph
by memory-mapping a graph file.
basename
- the basename of the graph.pl
- a progress logger used while loading the offsets, or null
.
BVGraph
containing the specified graph.
IOException
- if an I/O exception occurs while memory-mapping the graph or reading the offsets.public static BVGraph loadMapped(CharSequence basename) throws IOException
BVGraph
by memory-mapping a graph file.
basename
- the basename of the graph.
BVGraph
containing the specified graph.
IOException
- if an I/O exception occurs while memory-mapping the graph or reading the offsets.public static BVGraph loadSequential(CharSequence basename, ProgressLogger pl) throws IOException
BVGraph
by loading a compressed graph file from disk to memory, without offsets.
basename
- the basename of the graph.pl
- a progress logger used while loading the graph, or null
.
BVGraph
containing the specified graph.
IOException
- if an I/O exception occurs while reading the graph.public static BVGraph loadSequential(CharSequence basename) throws IOException
BVGraph
by loading a compressed graph file from disk to memory, with no progress logger and
without offsets.
basename
- the basename of the graph.
BVGraph
containing the specified graph.
IOException
- if an I/O exception occurs while reading the graph.public static BVGraph loadOffline(CharSequence basename, ProgressLogger pl) throws IOException
BVGraph
by loading just the metadata of a compressed graph file.
basename
- the basename of the graph.pl
- a progress logger, or null
.
BVGraph
containing the specified graph.
IOException
- if an I/O exception occurs while reading the metadata.public static BVGraph loadOffline(CharSequence basename) throws IOException
BVGraph
by loading just the metadata of a compressed graph file.
basename
- the basename of the graph.
BVGraph
containing the specified graph.
IOException
- if an I/O exception occurs while reading the metadata.protected BVGraph loadInternal(CharSequence basename, int offsetType, ProgressLogger pl) throws IOException
basename
- the basename of the graph.offsetType
- the desired offset type (2 is memory-mapping, 1 is normal random-access loading, 0 means that we do not want to load offsets at all, -1 that
the we do not want even load the graph file).pl
- a progress logger used while loading the graph, or null
.
IOException
- if an I/O exception occurs while reading the graph.protected static int intervalize(IntArrayList x, int minInterval, IntArrayList left, IntArrayList len, IntArrayList residuals)
x
as a union of an increasing
sequence of intervals and an increasing sequence of residual elements. More precisely, this intervalization works
as follows: first, one looks at x
as a sequence of intervals (i.e., maximal sequences of consecutive
elements); those intervals whose length is ≥ minInterval
are stored in the lists left
(the list of left extremes) and len
(the list of lengths; the length of an integer interval is the
number of integers in that interval). The remaining integers, called residuals are stored in the
residual
list.
Note that the previous content of left
, len
and residual
is lost.
x
- the list to be intervalized (an increasing list of natural numbers).minInterval
- the least length that a maximal sequence of consecutive elements must have in order for it to
be considered as an interval.left
- the resulting list of left extremes of the intervals.len
- the resulting list of interval lengths.residuals
- the resulting list of residuals.
public static void store(ImmutableGraph graph, CharSequence basename, int windowSize, int maxRefCount, int minIntervalLength, int zetaK, int flags, ProgressLogger pl) throws IOException
graph
- a graph to be compressed.basename
- a base name.windowSize
- the window size (-1 for the default value).maxRefCount
- the maximum reference count (-1 for the default value).minIntervalLength
- the minimum interval length (-1 for the default value, NO_INTERVALS
to disable).zetaK
- the parameter used for residual ζ-coding, if used (-1 for the default value).flags
- the flag mask.pl
- a progress logger to log the state of compression, or null
if no logging is required.
IOException
- if some exception is raised while writing the graph.public static void store(ImmutableGraph graph, CharSequence basename, int windowSize, int maxRefCount, int minIntervalLength, int zetaK, int flags) throws IOException
graph
- a graph to be compressed.basename
- a base name.windowSize
- the window size (-1 for the default value).maxRefCount
- the maximum reference count (-1 for the default value).minIntervalLength
- the minimum interval length (-1 for the default value, NO_INTERVALS
to disable).zetaK
- the parameter used for residual ζ-coding, if used (-1 for the default value).flags
- the flag mask.
IOException
- if some exception is raised while writing the graph.public static void store(ImmutableGraph graph, CharSequence basename, ProgressLogger pl) throws IOException
graph
- a graph to be compressed.basename
- a base name.pl
- a progress logger to log the state of compression, or null
if no logging is required.
IOException
- if some exception is raised while writing the graph.public static void store(ImmutableGraph graph, CharSequence basename) throws IOException
graph
- a graph to be compressed.basename
- a base name.
IOException
- if some exception is raised while writing the graph.public void writeOffsets(OutputBitStream obs, ProgressLogger pl) throws IOException
obs
- the output bit stream to which offsets will be written.pl
- a progress logger, or null
.
IOException
public static void main(String[] args) throws SecurityException, IllegalAccessException, InvocationTargetException, NoSuchMethodException, IOException, JSAPException, ClassNotFoundException, InstantiationException
BVGraph
.
SecurityException
IllegalAccessException
InvocationTargetException
NoSuchMethodException
IOException
JSAPException
ClassNotFoundException
InstantiationException
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |