it.unimi.dsi.webgraph
Class UnionImmutableGraph

java.lang.Object
  extended by it.unimi.dsi.webgraph.ImmutableGraph
      extended by it.unimi.dsi.webgraph.UnionImmutableGraph
All Implemented Interfaces:
FlyweightPrototype<ImmutableGraph>

public class UnionImmutableGraph
extends ImmutableGraph

An immutable graph representing the union of two given 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).


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.ImmutableGraph
GRAPHCLASS_PROPERTY_KEY, PROPERTIES_EXTENSION
 
Constructor Summary
protected UnionImmutableGraph(ImmutableGraph g0, ImmutableGraph g1)
          Creates the union of two given graphs.
 
Method Summary
 UnionImmutableGraph copy()
          Returns a flyweight copy of this immutable graph.
 NodeIterator 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.
 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.
 
Methods inherited from class it.unimi.dsi.webgraph.ImmutableGraph
basename, equals, hashCode, load, load, load, loadMapped, loadMapped, loadOffline, loadOffline, loadOnce, loadSequential, loadSequential, nodeIterator, numArcs, outdegrees, store, store, successors, toString
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
 

Constructor Detail

UnionImmutableGraph

protected UnionImmutableGraph(ImmutableGraph g0,
                              ImmutableGraph g1)
Creates the union of two given graphs.

Parameters:
g0 - the first graph.
g1 - the second graph.
Method Detail

copy

public UnionImmutableGraph 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 NodeIterator nodeIterator(int from)
Description copied from class: ImmutableGraph
Returns a node iterator for scanning the graph sequentially, starting from the given node.

This implementation just calls the random-access methods (ImmutableGraph.successors(int) and ImmutableGraph.outdegree(int)). More specific implementations may choose to maintain some extra state to make the enumeration more efficient.

Overrides:
nodeIterator in class ImmutableGraph
Parameters:
from - the node from which the iterator will iterate.
Returns:
a NodeIterator for accessing nodes and successors sequentially.

numNodes

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

Specified by:
numNodes in class ImmutableGraph
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 class ImmutableGraph
Returns:
true if this graph provides random access to successor lists.

successorArray

public int[] successorArray(int x)
Description copied from class: ImmutableGraph
Returns a reference to an array containing the successors of a given node.

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.

Overrides:
successorArray in class ImmutableGraph
Parameters:
x - a node.
Returns:
an array whose first elements are the successors of the node; the array must not be modified by the caller.

outdegree

public int outdegree(int x)
Description copied from class: ImmutableGraph
Returns the outdegree of a node.

Specified by:
outdegree in class ImmutableGraph
Parameters:
x - a node.
Returns:
the outdegree of the given node.