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 aspredecessors(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 offorward
.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
All Methods Instance Methods Concrete Methods 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 supportNodeIterator.copy(long)
.long
indegree(long x)
Returns the indegree of a nodeit.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
-
-
-
-
Field Detail
-
forward
public final ImmutableGraph forward
A graph.
-
backward
public final ImmutableGraph backward
The transpose offorward
.
-
-
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 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
public BidirectionalImmutableGraph 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 classImmutableGraph
- 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
andbackward
. 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
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
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 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
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)
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
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()
onbackward
.
-
-