Class UnionArcLabelledImmutableGraph
- java.lang.Object
-
- it.unimi.dsi.big.webgraph.ImmutableGraph
-
- it.unimi.dsi.big.webgraph.labelling.ArcLabelledImmutableGraph
-
- it.unimi.dsi.big.webgraph.labelling.UnionArcLabelledImmutableGraph
-
- All Implemented Interfaces:
it.unimi.dsi.lang.FlyweightPrototype<ImmutableGraph>
public class UnionArcLabelledImmutableGraph extends ArcLabelledImmutableGraph
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 providedLabelMergeStrategy
.Remarks about the implementation
Due to the lack of multiple inheritance, we could not extend both
UnionImmutableGraph
andArcLabelledImmutableGraph
, 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 ofUnionImmutableGraph
.
-
-
Nested Class Summary
-
Nested classes/interfaces inherited from class it.unimi.dsi.big.webgraph.ImmutableGraph
ImmutableGraph.LoadMethod
-
-
Field Summary
-
Fields inherited from class it.unimi.dsi.big.webgraph.labelling.ArcLabelledImmutableGraph
UNDERLYINGGRAPH_PROPERTY_KEY, UNDERLYINGGRAPH_SUFFIX
-
Fields inherited from class it.unimi.dsi.big.webgraph.ImmutableGraph
GRAPHCLASS_PROPERTY_KEY, NUMBER_OF_THREADS_PROPERTY, PROPERTIES_EXTENSION
-
-
Constructor Summary
Constructors Constructor Description UnionArcLabelledImmutableGraph(ArcLabelledImmutableGraph g0, ArcLabelledImmutableGraph g1, LabelMergeStrategy labelMergeStrategy)
Creates the union of two given graphs.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description UnionArcLabelledImmutableGraph
copy()
Returns a flyweight copy of this immutable graph.boolean
hasCopiableIterators()
Whether the node iterators returned by this graph supportNodeIterator.copy(long)
.Label[][]
labelBigArray(long 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 byArcLabelledImmutableGraph.successors(long)
.ArcLabelledNodeIterator
nodeIterator(long from)
Returns a node iterator for scanning the graph sequentially, starting from the given node.long
numNodes()
Returns the number of nodes of this graph.long
outdegree(long 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.long[][]
successorBigArray(long x)
Returns a reference to a big array containing the successors of a given node.ArcLabelledNodeIterator.LabelledArcIterator
successors(long x)
Returns a lazy iterator over the successors of a given node.-
Methods inherited from class it.unimi.dsi.big.webgraph.labelling.ArcLabelledImmutableGraph
equals, load, load, loadOffline, loadOffline, loadOnce, loadSequential, loadSequential, nodeIterator, toString
-
Methods inherited from class it.unimi.dsi.big.webgraph.ImmutableGraph
basename, hashCode, intNumNodes, load, loadMapped, loadMapped, numArcs, outdegrees, splitNodeIterators, store, store, wrap, wrap
-
-
-
-
Constructor Detail
-
UnionArcLabelledImmutableGraph
public UnionArcLabelledImmutableGraph(ArcLabelledImmutableGraph g0, ArcLabelledImmutableGraph g1, LabelMergeStrategy labelMergeStrategy)
Creates the union of two given graphs.- Parameters:
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
-
copy
public UnionArcLabelledImmutableGraph copy()
Description copied from class:ImmutableGraph
Returns a flyweight copy of this immutable graph.- Specified by:
copy
in interfaceit.unimi.dsi.lang.FlyweightPrototype<ImmutableGraph>
- Specified by:
copy
in classArcLabelledImmutableGraph
- Returns:
- a flyweight copy of this immutable graph.
- See Also:
FlyweightPrototype
-
nodeIterator
public ArcLabelledNodeIterator nodeIterator(long from)
Description copied from class:ArcLabelledImmutableGraph
Returns a node iterator for scanning the graph sequentially, starting from the given node.- Overrides:
nodeIterator
in classArcLabelledImmutableGraph
- 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()
-
numNodes
public long 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 anode iterator
. This apparently bizarre behaviour is necessary to support implementations asArcListASCIIGraph
, which do not know the actual number of nodes until a traversal has been completed.- Specified by:
numNodes
in classImmutableGraph
- Returns:
- the number of nodes.
-
randomAccess
public boolean randomAccess()
Description copied from class:ImmutableGraph
Checks whether this graph provides random access to successor lists.- Specified by:
randomAccess
in classImmutableGraph
- Returns:
- true if this graph provides random access to successor lists.
-
hasCopiableIterators
public boolean hasCopiableIterators()
Description copied from class:ImmutableGraph
Whether the node iterators returned by this graph supportNodeIterator.copy(long)
.- Overrides:
hasCopiableIterators
in classImmutableGraph
- Returns:
- true if this graph provides copiable iterators.
-
successorBigArray
public long[][] successorBigArray(long x)
Description copied from class:ImmutableGraph
Returns a reference to a big array containing the successors of a given node.The returned big array may contain more entries than the outdegree of
x
. However, only those with indices from 0 (inclusive) to the outdegree ofx
(exclusive) contain valid data.- Overrides:
successorBigArray
in classImmutableGraph
- Parameters:
x
- a node.- Returns:
- a big array whose first elements are the successors of the node; the array must not be modified by the caller.
-
outdegree
public long outdegree(long x)
Description copied from class:ImmutableGraph
Returns the outdegree of a node.- Specified by:
outdegree
in classImmutableGraph
- Parameters:
x
- a node.- Returns:
- the outdegree of the given node.
-
labelBigArray
public Label[][] labelBigArray(long x)
Description copied from class:ArcLabelledImmutableGraph
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 byArcLabelledImmutableGraph.successors(long)
.The returned array may contain more entries than the outdegree of
x
. However, only those with indices from 0 (inclusive) to the outdegree ofx
(exclusive) contain valid data.- Overrides:
labelBigArray
in classArcLabelledImmutableGraph
- 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.
-
successors
public ArcLabelledNodeIterator.LabelledArcIterator successors(long x)
Description copied from class:ImmutableGraph
Returns a lazy iterator over the successors of a given node. The iteration terminates when -1 is returned.- Specified by:
successors
in classArcLabelledImmutableGraph
- Parameters:
x
- a node.- Returns:
- a lazy iterator over the successors of the node.
-
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 classArcLabelledImmutableGraph
- Returns:
- a prototype for the labels of this graph.
-
-