it.unimi.dsi.webgraph.labelling
Class BitStreamArcLabelledImmutableGraph

java.lang.Object
  extended by it.unimi.dsi.webgraph.ImmutableGraph
      extended by it.unimi.dsi.webgraph.labelling.ArcLabelledImmutableGraph
          extended by it.unimi.dsi.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.

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.


Nested Class Summary
protected static class BitStreamArcLabelledImmutableGraph.BitStreamLabelledArcIterator
           
 
Nested classes/interfaces inherited from class it.unimi.dsi.webgraph.ImmutableGraph
ImmutableGraph.LoadMethod
 
Field Summary
protected  CharSequence basename
          The basename of this graph (required for offline access).
 ImmutableGraph g
          The underlying immutable graph.
static String LABEL_OFFSETS_EXTENSION
          The standard extension for the label offsets bit stream.
static String LABELS_EXTENSION
          The standard extension for the labels bit stream.
static String LABELSPEC_PROPERTY_KEY
          The standard property key for a label specification.
protected  EliasFanoMonotoneLongBigList offset
          The offset array, or null for sequential access.
protected  Label prototype
          A prototype label, used to deserialise labels and create copies.
 
Fields inherited from class it.unimi.dsi.webgraph.labelling.ArcLabelledImmutableGraph
UNDERLYINGGRAPH_PROPERTY_KEY, UNDERLYINGGRAPH_SUFFIX
 
Fields inherited from class it.unimi.dsi.webgraph.ImmutableGraph
GRAPHCLASS_PROPERTY_KEY, PROPERTIES_EXTENSION
 
Constructor Summary
protected BitStreamArcLabelledImmutableGraph(CharSequence basename, ImmutableGraph g, Label prototype, byte[] byteArray, FastMultiByteArrayInputStream labelStream, EliasFanoMonotoneLongBigList offset)
          Builds a new labelled graph using a bit stream of labels.
 
Method Summary
 CharSequence basename()
          Returns a symbolic basename for this graph (optional operation).
 BitStreamArcLabelledImmutableGraph copy()
          Returns a flyweight copy of this immutable graph.
static BitStreamArcLabelledImmutableGraph load(CharSequence basename)
           
static BitStreamArcLabelledImmutableGraph load(CharSequence basename, ProgressLogger pl)
           
protected static BitStreamArcLabelledImmutableGraph load(ImmutableGraph.LoadMethod method, CharSequence basename, ProgressLogger pl)
          Loads a labelled graph using the given method.
static BitStreamArcLabelledImmutableGraph loadOffline(CharSequence basename)
           
static BitStreamArcLabelledImmutableGraph loadOffline(CharSequence basename, ProgressLogger pl)
           
static BitStreamArcLabelledImmutableGraph loadSequential(CharSequence basename)
           
static BitStreamArcLabelledImmutableGraph loadSequential(CharSequence basename, ProgressLogger pl)
           
protected  InputBitStream newInputBitStream()
          Returns the label bit stream.
 ArcLabelledNodeIterator nodeIterator(int from)
          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.
protected  long offset(int x)
          Return the actual offset of the labels of the arcs going out of a given node.
 int outdegree(int x)
          Returns the outdegree of a node.
 Label prototype()
          Returns a prototype of the labels used by this graph.
 boolean randomAccess()
          Checks whether this graph provides random access to successor lists.
static void store(ArcLabelledImmutableGraph graph, CharSequence basename, CharSequence underlyingBasename)
           
static void store(ArcLabelledImmutableGraph graph, CharSequence basename, CharSequence underlyingBasename, ProgressLogger pl)
           
 int[] successorArray(int x)
          Returns a reference to an array containing the successors of a given node.
 ArcLabelledNodeIterator.LabelledArcIterator successors(int x)
          Returns a lazy iterator over the successors of a given node.
 
Methods inherited from class it.unimi.dsi.webgraph.labelling.ArcLabelledImmutableGraph
equals, labelArray, loadOnce, nodeIterator, toString
 
Methods inherited from class it.unimi.dsi.webgraph.ImmutableGraph
hashCode, load, loadMapped, loadMapped, outdegrees, store, store
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
 

Field Detail

LABELS_EXTENSION

public static final String LABELS_EXTENSION
The standard extension for the labels bit stream.

See Also:
Constant Field Values

LABEL_OFFSETS_EXTENSION

public static final String LABEL_OFFSETS_EXTENSION
The standard extension for the label offsets bit stream.

See Also:
Constant Field Values

LABELSPEC_PROPERTY_KEY

public static final String LABELSPEC_PROPERTY_KEY
The standard property key for a label specification.

See Also:
Constant Field Values

g

public final ImmutableGraph g
The underlying immutable graph.


prototype

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


basename

protected final CharSequence basename
The basename of this graph (required for offline access).


offset

protected final EliasFanoMonotoneLongBigList offset
The offset array, or null for sequential access.

Constructor Detail

BitStreamArcLabelledImmutableGraph

protected BitStreamArcLabelledImmutableGraph(CharSequence basename,
                                             ImmutableGraph g,
                                             Label prototype,
                                             byte[] byteArray,
                                             FastMultiByteArrayInputStream labelStream,
                                             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

copy

public BitStreamArcLabelledImmutableGraph copy()
Description copied from class: ImmutableGraph
Returns a flyweight copy of this immutable graph.

Specified by:
copy in interface FlyweightPrototype<ImmutableGraph>
Specified by:
copy in class ArcLabelledImmutableGraph
Returns:
a flyweight copy of this immutable graph.
See Also:
FlyweightPrototype

newInputBitStream

protected InputBitStream newInputBitStream()
                                    throws 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:
FileNotFoundException

basename

public 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(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.

successors

public ArcLabelledNodeIterator.LabelledArcIterator successors(int x)
Description copied from class: ImmutableGraph
Returns a lazy iterator over the successors of a given node. The iteration terminates when -1 is returned.

This implementation just wraps the array returned by ImmutableGraph.successorArray(int). Subclasses are encouraged to override this implementation.

The semantics of this method has been significantly modified in WebGraph 2.0 to take advantage of the new, faster lazy architecture.

Specified by:
successors in class ArcLabelledImmutableGraph
Parameters:
x - a node.
Returns:
a lazy iterator over the successors of the node.

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.

This implementation just unwraps the iterator returned by ImmutableGraph.successors(int). Subclasses are encouraged to override this implementation.

Warning: all implementations must guarantee that a distinct array is returned for each node. The caller, in turn, must treat the array as a read-only object.

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

public static BitStreamArcLabelledImmutableGraph loadSequential(CharSequence basename)
                                                         throws IOException
Throws:
IOException

loadSequential

public static BitStreamArcLabelledImmutableGraph loadSequential(CharSequence basename,
                                                                ProgressLogger pl)
                                                         throws IOException
Throws:
IOException

loadOffline

public static BitStreamArcLabelledImmutableGraph loadOffline(CharSequence basename)
                                                      throws IOException
Throws:
IOException

loadOffline

public static BitStreamArcLabelledImmutableGraph loadOffline(CharSequence basename,
                                                             ProgressLogger pl)
                                                      throws IOException
Throws:
IOException

load

public static BitStreamArcLabelledImmutableGraph load(CharSequence basename)
                                               throws IOException
Throws:
IOException

load

public static BitStreamArcLabelledImmutableGraph load(CharSequence basename,
                                                      ProgressLogger pl)
                                               throws IOException
Throws:
IOException

load

protected static BitStreamArcLabelledImmutableGraph load(ImmutableGraph.LoadMethod method,
                                                         CharSequence basename,
                                                         ProgressLogger pl)
                                                  throws 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:
IOException

nodeIterator

public ArcLabelledNodeIterator nodeIterator(int from)
Description copied from class: ArcLabelledImmutableGraph
Returns a node iterator for scanning the graph sequentially, starting from the given node.

This implementation strengthens that provided in ImmutableGraph, but calls the labelled random-access method ArcLabelledImmutableGraph.successors(int).

Overrides:
nodeIterator in class ArcLabelledImmutableGraph
Parameters:
from - the node from which the iterator will iterate.
Returns:
an ArcLabelledNodeIterator for accessing nodes, successors and their labels sequentially.
See Also:
ImmutableGraph.nodeIterator()

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,
                         CharSequence basename,
                         CharSequence underlyingBasename)
                  throws IOException
Throws:
IOException

store

public static void store(ArcLabelledImmutableGraph graph,
                         CharSequence basename,
                         CharSequence underlyingBasename,
                         ProgressLogger pl)
                  throws IOException
Throws:
IOException