Package it.unimi.dsi.big.webgraph.labelling

Class BitStreamArcLabelledImmutableGraph

java.lang.Object
it.unimi.dsi.big.webgraph.ImmutableGraph
it.unimi.dsi.big.webgraph.labelling.ArcLabelledImmutableGraph
it.unimi.dsi.big.webgraph.labelling.BitStreamArcLabelledImmutableGraph
All Implemented Interfaces:
FlyweightPrototype<ImmutableGraph>
public class BitStreamArcLabelledImmutableGraph extends ArcLabelledImmutableGraph
A labelled graph storing its labels as a bit stream.

Instances of this class wrap a given immutable graph and a bit stream. Given a prototype Label, the bit stream is then considered as containing all labels of all arcs as returned by a complete enumeration (made using ArcLabelledImmutableGraph.nodeIterator()). The overall graph is described by a label file (with extension .labels), an offset file (with extension .labeloffsets) and a property file (with extension .properties). The latter, not surprisingly, is a Java property file. Optionally, a label offset big-list file (with extension .labelobl) can be created to load label offsets faster.

The Label and Offset Files

Since the labels are stored as a bit stream, we must have some way to know where the labels related to the successors of each node start. This information is stored in the offset file, which contains the bit offset of the list of labels of the arcs going out of each node (in particular, the offset of the first list will be zero). As a commodity, the offset file contains an additional offset pointing just after the last list (providing, as a side-effect, the actual bit length of the label file). Each offset (except for the first one) is stored as a γ-coded difference from the previous offset.

Note that by default the EliasFanoMonotoneLongBigList instance is created from scratch using the file of label offsets. This is a long and tedious process, in particular with large label files. 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 .labelobl. The list will be quickly deserialised if this file is present.

The Property File

The property file for an instance of this class must contain the following entries:

graphclass
the name of this class; it is necessary so that load methods in ImmutableGraph can identify this class;
underlyinggraph
the basename (relative to the name of the property file, unless it is absolute) of the underlying ImmutableGraph;
labelspec
a string describing a constructor call for a label class; an example is
it.unimi.dsi.webgraph.labelling.FixedWidthIntLabel(FOO,10)
parameters are separated by a comma, and no quoting or escaping is allowed (see Label for details about string-based constructors).

The load() method of this class takes care of looking at the property file, loading the underlying immutable graph, and setting up either sequential or random access to the bit stream containing the labels. If just sequential access is required, the offsets are not loaded into memory, and if just offline access is required, bit stream is never loaded into memory.

Saving labels

The store(ArcLabelledImmutableGraph, CharSequence, CharSequence) and store(ArcLabelledImmutableGraph, CharSequence, CharSequence, ProgressLogger) methods will save the labels of an instance of this graph as expected, that is, the bitstream and its offsets will be saved with the extensions described above.