|
|||||||||
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.UnionArcLabelledImmutableGraph
public class UnionArcLabelledImmutableGraph
An arc-labelled immutable graph representing the union of two given such graphs.
Here by “union” we mean that an arc will belong to the union iff it belongs to at least one of the two graphs (the number of
nodes of the union is taken to be the maximum among the number of nodes of each graph). Labels are assumed to have the same
prototype in both graphs, and are treated as follows: if an arc is present in but one graph, its label in the resulting
graph is going to be the label of the arc in the graph where it comes from; if an arc is present in both graphs, the labels
are combined using a provided LabelMergeStrategy
.
Due to the lack of multiple inheritance, we could not extend both UnionImmutableGraph
and ArcLabelledImmutableGraph
, hence we forcedly decided to extend the latter. The possibility of using delegation
on the former was also discarded because the code for reading and merging labels is so tightly coupled with the rest that it
would have been essentially useless (and even dangerous) to delegate the iteration methods. As a result, some of the code of this
class is actually almost a duplicate of the code of UnionImmutableGraph
.
Nested Class Summary |
---|
Nested classes/interfaces inherited from class it.unimi.dsi.webgraph.ImmutableGraph |
---|
ImmutableGraph.LoadMethod |
Field Summary |
---|
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 | |
---|---|
UnionArcLabelledImmutableGraph(ArcLabelledImmutableGraph g0,
ArcLabelledImmutableGraph g1,
LabelMergeStrategy labelMergeStrategy)
Creates the union of two given graphs. |
Method Summary | |
---|---|
UnionArcLabelledImmutableGraph |
copy()
Returns a flyweight copy of this immutable graph. |
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 ArcLabelledImmutableGraph.successors(int) . |
ArcLabelledNodeIterator |
nodeIterator(int from)
Returns a node iterator for scanning the graph sequentially, starting from the given node. |
int |
numNodes()
Returns the number of nodes of this graph. |
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. |
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, load, load, loadOffline, loadOffline, loadOnce, loadSequential, loadSequential, nodeIterator, toString |
Methods inherited from class it.unimi.dsi.webgraph.ImmutableGraph |
---|
basename, hashCode, load, loadMapped, loadMapped, numArcs, outdegrees, store, store |
Methods inherited from class java.lang.Object |
---|
clone, finalize, getClass, notify, notifyAll, wait, wait, wait |
Constructor Detail |
---|
public UnionArcLabelledImmutableGraph(ArcLabelledImmutableGraph g0, ArcLabelledImmutableGraph g1, LabelMergeStrategy labelMergeStrategy)
g0
- the first graph.g1
- the second graph.labelMergeStrategy
- the strategy used to merge labels when the same arc is present in both graphs.Method Detail |
---|
public UnionArcLabelledImmutableGraph copy()
ImmutableGraph
copy
in interface FlyweightPrototype<ImmutableGraph>
copy
in class ArcLabelledImmutableGraph
FlyweightPrototype
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 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 boolean randomAccess()
ImmutableGraph
randomAccess
in class ImmutableGraph
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 outdegree(int x)
ImmutableGraph
outdegree
in class ImmutableGraph
x
- a node.
public Label[] labelArray(int x)
ArcLabelledImmutableGraph
ArcLabelledImmutableGraph.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 ArcLabelledImmutableGraph.successors(int)
and
writes in a newly allocated array copies of the labels returned by ArcLabelledNodeIterator.LabelledArcIterator.label()
.
labelArray
in class ArcLabelledImmutableGraph
x
; the array must not be modified by the caller.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 Label prototype()
ArcLabelledImmutableGraph
prototype
in class ArcLabelledImmutableGraph
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |