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

  • Field Details

  • Constructor Details

    • BidirectionalImmutableGraph

      public BidirectionalImmutableGraph(ImmutableGraph graph, ImmutableGraph transpose)
      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 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 FlyweightPrototype<ImmutableGraph>
      Specified by:
      copy in class ImmutableGraph
      Returns:
      a flyweight copy of this immutable graph.
      See Also:

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