Class EFGraph

All Implemented Interfaces:
FlyweightPrototype<ImmutableGraph>

public class EFGraph
extends ImmutableGraph
An immutable graph based on the Elias–Fano representation of monotone sequences.
Author:
Sebastiano Vigna
  • Field Details

    • GRAPH_EXTENSION

      public static final String GRAPH_EXTENSION
      The standard extension for the graph longword bit stream.
      See Also:
      Constant Field Values
    • OFFSETS_EXTENSION

      public static final String OFFSETS_EXTENSION
      The standard extension for the graph-offsets bit stream.
      See Also:
      Constant Field Values
    • OFFSETS_BIG_LIST_EXTENSION

      public static final String OFFSETS_BIG_LIST_EXTENSION
      The standard extension for the cached LongBigList containing the graph offsets.
      See Also:
      Constant Field Values
    • DEFAULT_CACHE_SIZE

      public static final int DEFAULT_CACHE_SIZE
      The default size of the bit cache.
      See Also:
      Constant Field Values
    • EFGRAPH_VERSION

      public static final int EFGRAPH_VERSION
      This number classifies the present graph format. When new features require introducing binary incompatibilities, this number is bumped so to ensure that old classes do not try to read graphs they cannot understand.
      See Also:
      Constant Field Values
    • DEFAULT_LOG_2_QUANTUM

      public static final int DEFAULT_LOG_2_QUANTUM
      The default base-two logarithm of the quantum.
      See Also:
      Constant Field Values
    • n

      protected final int n
      The number of nodes of the graph.
    • upperBound

      protected final int upperBound
      The upper bound used during the graph construction (greater than or equal to n.
    • m

      protected final long m
      The number of arcs of the graph.
    • graph

      protected final LongBigList graph
      The list containing the graph.
    • offsets

      protected final LongBigList offsets
      An Elias–Fano monotone list containing the pointers of the bit streams stored in graph.
    • basename

      protected final CharSequence basename
      The basename of this graph (or possibly null).
    • outdegreeLongWordBitReader

      protected final EFGraph.LongWordBitReader outdegreeLongWordBitReader
      A longword bit reader used to read outdegrees.
    • log2Quantum

      protected final int log2Quantum
      The base-two logarithm of the indexing quantum.
    • cachedNode

      protected int cachedNode
      If not Integer.MIN_VALUE, the node whose degree is cached in cachedOutdegree.
    • cachedOutdegree

      protected int cachedOutdegree
      If cachedNode is not Integer.MIN_VALUE, its cached outdegree.
    • cachedPointer

      protected long cachedPointer
      If cachedNode is not Integer.MIN_VALUE, the position immediately after the coding of the outdegree of cachedNode.
  • Constructor Details

  • Method Details