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.

    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.

    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
      • 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.sux4j.util.EliasFanoMonotoneLongBigList 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.sux4j.util.EliasFanoMonotoneLongBigList 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 offline access or large file access.
        labelStream - if byteArray is null, this 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).
        Overrides:
        basename in class ImmutableGraph
        Returns:
        the basename.
      • offset

        protected long offset​(int 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.
      • successorArray

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

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