Package it.unimi.dsi.big.webgraph

Class BidirectionalImmutableGraph

java.lang.Object

it.unimi.dsi.big.webgraph.ImmutableGraph

it.unimi.dsi.big.webgraph.BidirectionalImmutableGraph

All Implemented Interfaces:

it.unimi.dsi.lang.FlyweightPrototype<ImmutableGraph>

public class BidirectionalImmutableGraph
extends ImmutableGraph

A wrapper class exhibiting a graph and its transpose as a bidirectional graph. Methods such as predecessors(long), indegrees(), etc. are implemented using the transpose.

Nested Class Summary

Nested classes/interfaces inherited from class it.unimi.dsi.big.webgraph.ImmutableGraph

ImmutableGraph.LoadMethod

Field Summary

Fields

Modifier and Type	Field	Description
ImmutableGraph	backward	The transpose of forward.
ImmutableGraph	forward	A graph.

Fields inherited from class it.unimi.dsi.big.webgraph.ImmutableGraph

GRAPHCLASS_PROPERTY_KEY, NUMBER_OF_THREADS_PROPERTY, PROPERTIES_EXTENSION

Constructor Summary

Constructors

Constructor	Description
BidirectionalImmutableGraph(ImmutableGraph graph, ImmutableGraph transpose)	Creates a bidirectional immutable graph.

Method Summary

Modifier and Type	Method	Description
BidirectionalImmutableGraph	copy()	Returns a flyweight copy of this immutable graph.
boolean	hasCopiableIterators()	Whether the node iterators returned by this graph support NodeIterator.copy(long).
long	indegree(long x)	Returns the indegree of a node
it.unimi.dsi.fastutil.longs.LongIterator	indegrees()	Returns an iterator enumerating the outdegrees of the nodes of this graph.
long	numArcs()	Returns the number of arcs of this graph (optional operation).
long	numNodes()	Returns the number of nodes of this graph.
long	outdegree(long l)	Returns the outdegree of a node.
long[][]	predecessorBigArray(long x)	Returns a reference to a big array containing the predecessors of a given node.
LazyLongIterator	predecessors(long x)	Returns a lazy iterator over the successors of a given node.
boolean	randomAccess()	Checks whether this graph provides random access to successor lists.
BidirectionalImmutableGraph	simplify()	Returns a view on the simple (loopless and symmetric) version of this bidirectional graph.
long[][]	successorBigArray(long x)	Returns a reference to a big array containing the successors of a given node.
LazyLongIterator	successors(long nodeId)	Returns a lazy iterator over the successors of a given node.
BidirectionalImmutableGraph	symmetrize()	Returns a view on the symmetrized version of this bidirectional graph.
BidirectionalImmutableGraph	transpose()	Returns a view on the transpose of this bidirectional graph.

Methods inherited from class it.unimi.dsi.big.webgraph.ImmutableGraph

basename, equals, hashCode, intNumNodes, load, load, load, loadMapped, loadMapped, loadOffline, loadOffline, loadOnce, loadSequential, loadSequential, nodeIterator, nodeIterator, outdegrees, splitNodeIterators, store, store, toString, wrap, wrap

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Field Detail

forward

public final ImmutableGraph forward

A graph.

backward

public final ImmutableGraph backward

The transpose of forward.

Constructor Detail

BidirectionalImmutableGraph

public BidirectionalImmutableGraph(ImmutableGraph graph,
                                   ImmutableGraph transpose)

Creates a bidirectional immutable graph.

Parameters:

graph - a graph.

transpose - its transpose.

Method Detail

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

numArcs

public long numArcs()

Description copied from class: ImmutableGraph

Returns the number of arcs of this graph (optional operation).

Overrides:

numArcs in class ImmutableGraph

Returns:

the number of arcs.

randomAccess

public boolean randomAccess()

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.

Implementation Specification:

This methods returns true if both forward and backward provide random access.

hasCopiableIterators

public boolean hasCopiableIterators()

Whether the node iterators returned by this graph support NodeIterator.copy(long).

Overrides:

hasCopiableIterators in class ImmutableGraph

Returns:

true if this graph provides copiable iterators.

Implementation Specification:

This methods returns true if both forward and backward have copiable iterators.

copy

public BidirectionalImmutableGraph copy()

Description copied from class: ImmutableGraph

Returns a flyweight copy of this immutable graph.

Specified by:

copy in interface it.unimi.dsi.lang.FlyweightPrototype<ImmutableGraph>

Specified by:

copy in class ImmutableGraph

Returns:

a flyweight copy of this immutable graph.

See Also:

FlyweightPrototype

transpose

public BidirectionalImmutableGraph transpose()

Returns a view on the transpose of this bidirectional graph. Successors become predecessors, and vice-versa.

Returns:

a view on the transpose of this bidirectional graph.

API Notes:

Note that the returned BidirectionalImmutableGraph is just a view. Thus, it cannot be accessed concurrently with this bidirectional graph. If you need concurrent access, please make a copy.

symmetrize

public BidirectionalImmutableGraph symmetrize()

Returns a view on the symmetrized version of this bidirectional graph.

Returns:

the symmetrized version of this bidirectional graph.

API Notes:

Note that the returned BidirectionalImmutableGraph is just a view. Thus, it cannot be accessed concurrently with this bidirectional graph. If you need concurrent access, please make a copy.

Implementation Specification:

This methods returns the (lazy) union of forward and backward. This is equivalent to forgetting the directionality of the arcs: the successors of a node are also its predecessors.

simplify

public BidirectionalImmutableGraph simplify()

Returns a view on the simple (loopless and symmetric) version of this bidirectional graph.

Returns:

the simple (symmetric and loopless) version of this bidirectional graph.

API Notes:

Note that the returned BidirectionalImmutableGraph is just a view. Thus, it cannot be accessed concurrently with this bidirectional graph. If you need concurrent access, please make a copy.

Implementation Specification:

This methods returns the (lazy) result of Transform.simplify(ImmutableGraph, ImmutableGraph) on forward and backward. Beside forgetting directionality of the arcs, as in symmetrize(), loops are removed.

outdegree

public long outdegree(long l)

Returns the outdegree of a node.

Specified by:

outdegree in class ImmutableGraph

Parameters:

l - a node.

Returns:

the outdegree of the given node.

Implementation Specification:

This implementation just invokes ImmutableGraph.outdegree(long) on forward.

successors

public LazyLongIterator successors(long nodeId)

Returns a lazy iterator over the successors of a given node. The iteration terminates when -1 is returned.

Overrides:

successors in class ImmutableGraph

Parameters:

nodeId - a node.

Returns:

a lazy iterator over the successors of the node.

Implementation Specification:

This implementation just invokes ImmutableGraph.successors(long) on forward.

successorBigArray

public long[][] successorBigArray(long x)

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 of x (exclusive) contain valid data.

Overrides:

successorBigArray in class ImmutableGraph

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.

Implementation Specification:

This implementation just invokes ImmutableGraph.successorBigArray(long) on forward.

indegree

public long indegree(long x)

Returns the indegree of a node

Parameters:

x - a node.

Returns:

the indegree of x.

predecessors

public LazyLongIterator predecessors(long x)

Returns a lazy iterator over the successors of a given node. The iteration terminates when -1 is returned.

Parameters:

x - a node.

Returns:

a lazy iterator over the predecessors of the node.

Implementation Specification:

This implementation just invokes ImmutableGraph.successors(long) on backward.

predecessorBigArray

public long[][] predecessorBigArray(long x)

Returns a reference to a big array containing the predecessors 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 indegree of x (exclusive) contain valid data.

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.

Implementation Specification:

This implementation just invokes ImmutableGraph.successorBigArray(long) on backward.

indegrees

public it.unimi.dsi.fastutil.longs.LongIterator indegrees()

Returns an iterator enumerating the outdegrees of the nodes of this graph.

Returns:

an iterator enumerating the outdegrees of the nodes of this graph.

Implementation Specification:

This implementation just invokes ImmutableGraph.outdegrees() on backward.