Package it.unimi.dsi.webgraph.labelling

Main classes implementing labelling for immutable graphs. A labelled immutable graph is a graph endowed with labels, on its arcs and/or on its nodes; currently, only arc labelling is implemented (since node labelling can be easily dealt with outside of the WebGraph framework, anyway).

Warning: this package is experimental.

Labels

A label is just an instance of a class implementing the Label interface: essentially, for maximum versatility, is a set of key/value pairs, where keys are strings and values can be essentially anything; in most simple cases, though, labels will be made by a single key/value pair (and the key will be, of course, irrelevant). All arcs of the same graph will have labels of the same class, and for this reason labels offer a Label.copy() method that allows the prototype design pattern to be used.

The only requirement for the serialisation of labels is that every label can be written as a self-delimiting bit sequence (via the Label.toBitStream(it.unimi.dsi.io.OutputBitStream,int) method); essentially, two kinds of label exists: fixed-width labels (that write themselves using always the same, fixed number of bits) or variable-width labels; you can know whether a label has fixed width or not by calling Label.fixedWidth() (this method will return -1 if the width is variable).

As an example, single-attribute integer label classes are implemented, one using fixed width and another using γ-coding.

Labelled graphs

An arc-labelled immutable graphs is an immutable graphs with labels on its arcs; it rewrites the immutable graphs methods covariantly so that, for example, when one iterates on the successors of a node using ArcLabelledImmutableGraph.successors(int) not a simple IntIterator is returned (iterating over the nodes that are successors of the given node), but rather a ArcLabelledNodeIterator.LabelledArcIterator (that returns every time a node/label pair).

Even though different implementations of arc-labelled immutable graphs may exist, we provide one (BitStreamArcLabelledImmutableGraph) that assumes that an immutable graph has been provided and that labels have been written onto a label file in the same order as the arcs of the immutable graph would be returned by the ArcLabelledImmutableGraph.nodeIterator() method. An additional offset file must be provided that allows one to know the offset (in bit) within the label file where the labels of the arcs going out of a given node start. These data are generated using the store() methods whose implementation is suggested in the class documentation of ArcLabelledImmutableGraph.

Interface Summary

Interface	Description
ArcLabelledNodeIterator.LabelledArcIterator	An iterator returning successor and the labels of the arcs toward them.
ArcRelabelledImmutableGraph.LabelConversionStrategy	A way to convert a label into another label.
Label	A set of attributes that can be used to decorate a node or an arc of a graph.
LabelMergeStrategy	A way to merge two labels into one; the actual merge is performed by the LabelMergeStrategy.merge(Label, Label) method.
LabelSemiring	A semiring used to compose labels.

Class Summary

Class	Description
AbstractIntLabel	An abstract (single-attribute) integer label.
AbstractIntListLabel	An abstract (single-attribute) list-of-integers label.
AbstractLabel	An abstract implementation throwing an IllegalArgumentException on all primitive-type methods.
ArcLabelledImmutableGraph	An abstract implementation of a graph labelled on its arcs.
ArcLabelledImmutableSequentialGraph	An abstract arc-labelled immutable graph that throws an UnsupportedOperationException on all random-access methods.
ArcLabelledNodeIterator	An iterator returning nodes, their successors and labels on the arcs.
ArcRelabelledImmutableGraph	Exhibits an arc-labelled immutable graph as another arc-labelled immutable graph changing only the kind of labels.
BitStreamArcLabelledImmutableGraph	A labelled graph storing its labels as a bit stream.
BitStreamArcLabelledImmutableGraph.BitStreamLabelledArcIterator
FixedWidthIntLabel	An integer represented in fixed width.
FixedWidthIntListLabel	A list of integers represented in fixed width.
GammaCodedIntLabel	A natural number represented in γ coding.
IntegerLabelFilter	A filter for labelled graphs preserving those arcs whose integer labels are in a specified set.
Labels
UnionArcLabelledImmutableGraph	An arc-labelled immutable graph representing the union of two given such graphs.