|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectit.unimi.dsi.webgraph.ImmutableGraph
it.unimi.dsi.webgraph.labelling.ArcLabelledImmutableGraph
it.unimi.dsi.webgraph.labelling.BitStreamArcLabelledImmutableGraph
public class BitStreamArcLabelledImmutableGraph
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.
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 for an instance of this class must contain the following entries:
ImmutableGraph
can identify this class;
ImmutableGraph
;
it.unimi.dsi.webgraph.labelling.FixedWidthIntLabel(FOO,10)
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.
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 |
---|
public static final String LABELS_EXTENSION
public static final String LABEL_OFFSETS_EXTENSION
public static final String LABELSPEC_PROPERTY_KEY
public final ImmutableGraph g
protected final Label prototype
protected final CharSequence basename
protected final EliasFanoMonotoneLongBigList offset
null
for sequential access.
Constructor Detail |
---|
protected BitStreamArcLabelledImmutableGraph(CharSequence basename, ImmutableGraph g, Label prototype, byte[] byteArray, FastMultiByteArrayInputStream labelStream, EliasFanoMonotoneLongBigList offset)
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 |
---|
public BitStreamArcLabelledImmutableGraph copy()
ImmutableGraph
copy
in interface FlyweightPrototype<ImmutableGraph>
copy
in class ArcLabelledImmutableGraph
FlyweightPrototype
protected InputBitStream newInputBitStream() throws FileNotFoundException
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.
FileNotFoundException
public CharSequence basename()
ImmutableGraph
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).
basename
in class ImmutableGraph
protected long offset(int x)
x
- a node.
x
.public ArcLabelledNodeIterator.LabelledArcIterator successors(int x)
ImmutableGraph
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.
successors
in class ArcLabelledImmutableGraph
x
- a node.
public int[] successorArray(int x)
ImmutableGraph
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.
successorArray
in class ImmutableGraph
x
- a node.
public int numNodes()
ImmutableGraph
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.
numNodes
in class ImmutableGraph
public long numArcs()
ImmutableGraph
numArcs
in class ImmutableGraph
public boolean randomAccess()
ImmutableGraph
randomAccess
in class ImmutableGraph
public int outdegree(int x)
ImmutableGraph
outdegree
in class ImmutableGraph
x
- a node.
public static BitStreamArcLabelledImmutableGraph loadSequential(CharSequence basename) throws IOException
IOException
public static BitStreamArcLabelledImmutableGraph loadSequential(CharSequence basename, ProgressLogger pl) throws IOException
IOException
public static BitStreamArcLabelledImmutableGraph loadOffline(CharSequence basename) throws IOException
IOException
public static BitStreamArcLabelledImmutableGraph loadOffline(CharSequence basename, ProgressLogger pl) throws IOException
IOException
public static BitStreamArcLabelledImmutableGraph load(CharSequence basename) throws IOException
IOException
public static BitStreamArcLabelledImmutableGraph load(CharSequence basename, ProgressLogger pl) throws IOException
IOException
protected static BitStreamArcLabelledImmutableGraph load(ImmutableGraph.LoadMethod method, CharSequence basename, ProgressLogger pl) throws IOException
method
- a load method.basename
- the basename of the graph.pl
- a progress logger.
IOException
public ArcLabelledNodeIterator nodeIterator(int from)
ArcLabelledImmutableGraph
This implementation strengthens that provided in ImmutableGraph
, but
calls the labelled random-access method ArcLabelledImmutableGraph.successors(int)
.
nodeIterator
in class ArcLabelledImmutableGraph
from
- the node from which the iterator will iterate.
ArcLabelledNodeIterator
for accessing nodes, successors and their labels sequentially.ImmutableGraph.nodeIterator()
public Label prototype()
ArcLabelledImmutableGraph
prototype
in class ArcLabelledImmutableGraph
public static void store(ArcLabelledImmutableGraph graph, CharSequence basename, CharSequence underlyingBasename) throws IOException
IOException
public static void store(ArcLabelledImmutableGraph graph, CharSequence basename, CharSequence underlyingBasename, ProgressLogger pl) throws IOException
IOException
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |