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:
FlyweightPrototype<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
Modifier and TypeFieldDescriptionfinal ImmutableGraph
The transpose offorward
.final ImmutableGraph
A graph.Fields inherited from class it.unimi.dsi.big.webgraph.ImmutableGraph
GRAPHCLASS_PROPERTY_KEY, NUMBER_OF_THREADS_PROPERTY, PROPERTIES_EXTENSION

Constructor Summary
ConstructorDescriptionBidirectionalImmutableGraph
(ImmutableGraph graph, ImmutableGraph transpose) Creates a bidirectional immutable graph. 
Method Summary
Modifier and TypeMethodDescriptioncopy()
Returns a flyweight copy of this immutable graph.boolean
Whether the node iterators returned by this graph supportNodeIterator.copy(long)
.long
indegree
(long x) Returns the indegree of a nodeReturns 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.predecessors
(long x) Returns a lazy iterator over the successors of a given node.boolean
Checks whether this graph provides random access to successor lists.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.successors
(long nodeId) Returns a lazy iterator over the successors of a given node.Returns a view on the symmetrized version of this bidirectional graph.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

Field Details

forward
A graph. 
backward
The transpose offorward
.


Constructor Details

BidirectionalImmutableGraph
Creates a bidirectional immutable graph. Parameters:
graph
 a graph.transpose
 its transpose.


Method Details

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.

numArcs
public long numArcs()Description copied from class:ImmutableGraph
Returns the number of arcs of this graph (optional operation). Overrides:
numArcs
in classImmutableGraph
 Returns:
 the number of arcs.

randomAccess
public boolean randomAccess()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.
 Implementation Specification:
 This methods returns true if both
forward
andbackward
provide random access.

hasCopiableIterators
public boolean hasCopiableIterators()Whether the node iterators returned by this graph supportNodeIterator.copy(long)
. Overrides:
hasCopiableIterators
in classImmutableGraph
 Returns:
 true if this graph provides copiable iterators.
 Implementation Specification:
 This methods returns true if both
forward
andbackward
have copiable iterators.

copy
Description copied from class:ImmutableGraph
Returns a flyweight copy of this immutable graph. Specified by:
copy
in interfaceFlyweightPrototype<ImmutableGraph>
 Specified by:
copy
in classImmutableGraph
 Returns:
 a flyweight copy of this immutable graph.
 See Also:

transpose
Returns a view on the transpose of this bidirectional graph. Successors become predecessors, and viceversa. 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
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
andbackward
. This is equivalent to forgetting the directionality of the arcs: the successors of a node are also its predecessors.

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
andbackward
. Beside forgetting directionality of the arcs, as insymmetrize()
, loops are removed.

outdegree
public long outdegree(long l) Returns the outdegree of a node. Specified by:
outdegree
in classImmutableGraph
 Parameters:
l
 a node. Returns:
 the outdegree of the given node.
 Implementation Specification:
 This implementation just invokes
ImmutableGraph.outdegree(long)
onforward
.

successors
Returns a lazy iterator over the successors of a given node. The iteration terminates when 1 is returned. Overrides:
successors
in classImmutableGraph
 Parameters:
nodeId
 a node. Returns:
 a lazy iterator over the successors of the node.
 Implementation Specification:
 This implementation just invokes
ImmutableGraph.successors(long)
onforward
.

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 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.
 Implementation Specification:
 This implementation just invokes
ImmutableGraph.successorBigArray(long)
onforward
.

indegree
public long indegree(long x) Returns the indegree of a node Parameters:
x
 a node. Returns:
 the indegree of
x
.

predecessors
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)
onbackward
.

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 ofx
(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)
onbackward
.

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()
onbackward
.
