it.unimi.dsi.webgraph.labelling
Class ArcLabelledImmutableGraph

java.lang.Object
  extended by it.unimi.dsi.webgraph.ImmutableGraph
      extended by it.unimi.dsi.webgraph.labelling.ArcLabelledImmutableGraph
All Implemented Interfaces:
FlyweightPrototype<ImmutableGraph>
Direct Known Subclasses:
ArcLabelledImmutableSequentialGraph, ArcRelabelledImmutableGraph, BitStreamArcLabelledImmutableGraph, UnionArcLabelledImmutableGraph

public abstract class ArcLabelledImmutableGraph
extends ImmutableGraph

An abstract implementation of a graph labelled on its arcs.

The main purpose of this class is that of override covariantly the return type of nodeIterator() and nodeIterator(int) so that it is an ArcLabelledNodeIterator, and the return type of all static load methods and of copy() so that it is an ArcLabelledImmutableGraph (the methods themselves just delegate to the corresponding method in ImmutableGraph).

The only additional instance methods are labelArray(int) and prototype().

Saving labels

A subclass of this class may implement

These methods must save the labels of the given arc-labelled graph using the first given character sequence as a basename, and a suitable property file using the second given basename. Note that the graph will not be saved—use the store() method of an ImmutableGraph implementation for that purpose.

For istance, assuming g is an arc-labelled graph the idiomatic way of storing it on disk using BVGraph for the underlying graph and BitStreamArcLabelledImmutableGraph for the labels is

 BVGraph.store( g, "foo" );
 BitStreamArcLabelledImmutableGraph.store( g, "bar", "foo" );
 

Underlying graphs

Often, implementations of this class will just wrap an underlying graph (i.e., an instance of ImmutableGraph). In that case, we suggest that if the implementation uses property files the basename of the underlying graph is specified using the property key UNDERLYINGGRAPH_PROPERTY_KEY. If the basename must be generated starting from the arc-labelled graph basename, we suggest to just add at the end the string UNDERLYINGGRAPH_SUFFIX.


Nested Class Summary
 
Nested classes/interfaces inherited from class it.unimi.dsi.webgraph.ImmutableGraph
ImmutableGraph.LoadMethod
 
Field Summary
static String UNDERLYINGGRAPH_PROPERTY_KEY
          The standard property key for the underlying graph.
static String UNDERLYINGGRAPH_SUFFIX
          The standard suffix added to basenames in order to give a basename to the underlying graph, when needed.
 
Fields inherited from class it.unimi.dsi.webgraph.ImmutableGraph
GRAPHCLASS_PROPERTY_KEY, PROPERTIES_EXTENSION
 
Constructor Summary
ArcLabelledImmutableGraph()
           
 
Method Summary
abstract  ArcLabelledImmutableGraph copy()
          Returns a flyweight copy of this immutable graph.
 boolean equals(Object x)
          Compare this immutable graph to another object.
 Label[] labelArray(int x)
          Returns a reference to an array containing the labels of the arcs going out of a given node in the same order as the order in which the corresponding successors are returned by successors(int).
static ArcLabelledImmutableGraph load(CharSequence basename)
           
static ArcLabelledImmutableGraph load(CharSequence basename, ProgressLogger pl)
           
static ArcLabelledImmutableGraph loadOffline(CharSequence basename)
           
static ArcLabelledImmutableGraph loadOffline(CharSequence basename, ProgressLogger pl)
           
static ArcLabelledImmutableGraph loadOnce(InputStream is)
           
static ArcLabelledImmutableGraph loadSequential(CharSequence basename)
           
static ArcLabelledImmutableGraph loadSequential(CharSequence basename, ProgressLogger pl)
           
 ArcLabelledNodeIterator nodeIterator()
          Returns a node iterator for scanning the graph sequentially, starting from the first node.
 ArcLabelledNodeIterator nodeIterator(int from)
          Returns a node iterator for scanning the graph sequentially, starting from the given node.
abstract  Label prototype()
          Returns a prototype of the labels used by this graph.
abstract  ArcLabelledNodeIterator.LabelledArcIterator successors(int x)
          Returns a lazy iterator over the successors of a given node.
 String toString()
           
 
Methods inherited from class it.unimi.dsi.webgraph.ImmutableGraph
basename, hashCode, load, loadMapped, loadMapped, numArcs, numNodes, outdegree, outdegrees, randomAccess, store, store, successorArray
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
 

Field Detail

UNDERLYINGGRAPH_PROPERTY_KEY

public static final String UNDERLYINGGRAPH_PROPERTY_KEY
The standard property key for the underlying graph. All implementations decorating with labels an underlying graph are strongly encouraged to use this property name to specify the basename of the underlying graph.

See Also:
Constant Field Values

UNDERLYINGGRAPH_SUFFIX

public static final String UNDERLYINGGRAPH_SUFFIX
The standard suffix added to basenames in order to give a basename to the underlying graph, when needed.

See Also:
Constant Field Values
Constructor Detail

ArcLabelledImmutableGraph

public ArcLabelledImmutableGraph()
Method Detail

copy

public abstract ArcLabelledImmutableGraph 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 ImmutableGraph
Returns:
a flyweight copy of this immutable graph.
See Also:
FlyweightPrototype

nodeIterator

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

Overrides:
nodeIterator in class ImmutableGraph
Returns:
a NodeIterator for accessing nodes and successors sequentially.

nodeIterator

public ArcLabelledNodeIterator nodeIterator(int from)
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 successors(int).

Overrides:
nodeIterator in class ImmutableGraph
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()

successors

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

Overrides:
successors in class ImmutableGraph
Parameters:
x - a node.
Returns:
a lazy iterator over the successors of the node.

prototype

public abstract Label prototype()
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.

Returns:
a prototype for the labels of this graph.

labelArray

public Label[] labelArray(int x)
Returns a reference to an array containing the labels of the arcs going out of a given node in the same order as the order in which the corresponding successors are returned by successors(int).

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 unwrap the iterator returned by successors(int) and writes in a newly allocated array copies of the labels returned by ArcLabelledNodeIterator.LabelledArcIterator.label().

Returns:
an array whose first elements are the labels of the arcs going out of x; the array must not be modified by the caller.

loadSequential

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

loadSequential

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

loadOffline

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

loadOffline

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

load

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

load

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

loadOnce

public static ArcLabelledImmutableGraph loadOnce(InputStream is)
                                          throws IOException
Throws:
IOException

toString

public String toString()
Overrides:
toString in class ImmutableGraph

equals

public boolean equals(Object x)
Description copied from class: ImmutableGraph
Compare this immutable graph to another object.

Overrides:
equals in class ImmutableGraph
Returns:
true iff the given object is an immutable graph of the same size, and the successor list of every node of this graph is equal to the successor list of the corresponding node of o.