Class BitStreamArcLabelledImmutableGraph

  • All Implemented Interfaces:
    it.unimi.dsi.lang.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.

    • Field Detail

      • LABELS_EXTENSION

        public static final java.lang.String LABELS_EXTENSION
        The standard extension for the labels bit stream.
        See Also:
        Constant Field Values
      • LABEL_OFFSETS_EXTENSION

        public static final java.lang.String LABEL_OFFSETS_EXTENSION
        The standard extension for the label offsets bit stream.
        See Also:
        Constant Field Values
      • LABEL_OFFSETS_BIG_LIST_EXTENSION

        public static final java.lang.String LABEL_OFFSETS_BIG_LIST_EXTENSION
        The standard extension for the cached LongBigList containing the label offsets.
        See Also:
        Constant Field Values
      • LABELSPEC_PROPERTY_KEY

        public static final java.lang.String LABELSPEC_PROPERTY_KEY
        The standard property key for a label specification.
        See Also:
        Constant Field Values
      • prototype

        protected final Label prototype
        A prototype label, used to deserialise labels and create copies.
      • basename

        protected final java.lang.CharSequence basename
        The basename of this graph (required for offline access).
      • offset

        protected final it.unimi.dsi.fastutil.longs.LongBigList offset
        The offset array, or null for sequential access.
    • Constructor Detail

      • BitStreamArcLabelledImmutableGraph

        protected BitStreamArcLabelledImmutableGraph​(java.lang.CharSequence basename,
                                                     ImmutableGraph g,
                                                     Label prototype,
                                                     byte[] byteArray,
                                                     it.unimi.dsi.fastutil.io.FastMultiByteArrayInputStream labelStream,
                                                     it.unimi.dsi.io.ByteBufferInputStream mappedLabelStream,
                                                     it.unimi.dsi.fastutil.longs.LongBigList offset)
        Builds a new labelled graph using a bit stream of labels.
        Parameters:
        basename - the basename of the graph (mandatory for offline access).
        g - the underlying immutable graph.
        prototype - a label instance.
        byteArray - a byte array containing the bit stream of labels, or null for offile access or large file access.
        labelStream - if byteArray is null, this stream is used as the bit stream of labels.
        mappedLabelStream - if byteArray and labelStream are null, this memory-mapped stream is used as the bit stream of labels.
        offset - the offset array for random access, or null.
    • Method Detail

      • newInputBitStream

        protected it.unimi.dsi.io.InputBitStream newInputBitStream()
                                                            throws java.io.FileNotFoundException
        Returns the label bit stream.

        This method takes care of creating the bit stream from the right source—the byte array, the stream of multiple byte arrays or the label file itself.

        Returns:
        the label bit stream.
        Throws:
        java.io.FileNotFoundException
      • 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.
      • offset

        protected long offset​(long x)
        Return the actual offset of the labels of the arcs going out of a given node.
        Parameters:
        x - a node.
        Returns:
        the offset of the labels of the arcs going out of x.
      • successorBigArray

        public long[][] successorBigArray​(long x)
        Description copied from class: ImmutableGraph
        Returns a reference to a big array containing the successors of a given node.

        The returned big array may contain more entries than the outdegree of x. However, only those with indices from 0 (inclusive) to the outdegree of x (exclusive) contain valid data.

        Overrides:
        successorBigArray in class ImmutableGraph
        Parameters:
        x - a node.
        Returns:
        a big array whose first elements are the successors of the node; the array must not be modified by the caller.
      • 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.
      • loadSequential

        @Deprecated
        public static BitStreamArcLabelledImmutableGraph loadSequential​(java.lang.CharSequence basename)
                                                                 throws java.io.IOException
        Deprecated.
        Throws:
        java.io.IOException
      • loadSequential

        @Deprecated
        public static BitStreamArcLabelledImmutableGraph loadSequential​(java.lang.CharSequence basename,
                                                                        it.unimi.dsi.logging.ProgressLogger pl)
                                                                 throws java.io.IOException
        Deprecated.
        Throws:
        java.io.IOException
      • loadOffline

        public static BitStreamArcLabelledImmutableGraph loadOffline​(java.lang.CharSequence basename,
                                                                     it.unimi.dsi.logging.ProgressLogger pl)
                                                              throws java.io.IOException
        Throws:
        java.io.IOException
      • loadMapped

        public static BitStreamArcLabelledImmutableGraph loadMapped​(java.lang.CharSequence basename,
                                                                    it.unimi.dsi.logging.ProgressLogger pl)
                                                             throws java.io.IOException
        Throws:
        java.io.IOException
      • load

        public static BitStreamArcLabelledImmutableGraph load​(java.lang.CharSequence basename,
                                                              it.unimi.dsi.logging.ProgressLogger pl)
                                                       throws java.io.IOException
        Throws:
        java.io.IOException
      • load

        protected static BitStreamArcLabelledImmutableGraph load​(ImmutableGraph.LoadMethod method,
                                                                 java.lang.CharSequence basename,
                                                                 it.unimi.dsi.logging.ProgressLogger pl)
                                                          throws java.io.IOException
        Loads a labelled graph using the given method and offset step.

        If offsetStep is larger than 1 and the the underlying graph is a BVGraph, the value will be passed to BVGraph.load(CharSequence, int, ProgressLogger).

        Parameters:
        method - a load method.
        basename - the basename of the graph.
        pl - a progress logger.
        Returns:
        a graph labelled using a bit stream.
        Throws:
        java.io.IOException
      • prototype

        public Label prototype()
        Description copied from class: ArcLabelledImmutableGraph
        Returns a prototype of the labels used by this graph. The prototype can be used to produce new copies, but must not be modified by the caller.
        Specified by:
        prototype in class ArcLabelledImmutableGraph
        Returns:
        a prototype for the labels of this graph.
      • store

        public static void store​(ArcLabelledImmutableGraph graph,
                                 java.lang.CharSequence basename,
                                 java.lang.CharSequence underlyingBasename)
                          throws java.io.IOException
        Throws:
        java.io.IOException
      • store

        public static void store​(ArcLabelledImmutableGraph graph,
                                 java.lang.CharSequence basename,
                                 java.lang.CharSequence underlyingBasename,
                                 it.unimi.dsi.logging.ProgressLogger pl)
                          throws java.io.IOException
        Throws:
        java.io.IOException
      • main

        public static void main​(java.lang.String[] args)
                         throws com.martiansoftware.jsap.JSAPException,
                                java.io.IOException
        Reads an arc-labelled immutable graph and stores it as a BitStreamArcLabelledImmutableGraph.
        Throws:
        com.martiansoftware.jsap.JSAPException
        java.io.IOException