Package it.unimi.dsi.big.webgraph

Class EFGraph

java.lang.Object
it.unimi.dsi.big.webgraph.ImmutableGraph
it.unimi.dsi.big.webgraph.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:

    • OFFSETS_EXTENSION

      public static final String OFFSETS_EXTENSION
      The standard extension for the graph-offsets bit stream.
      See Also:

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

    • DEFAULT_CACHE_SIZE

      public static final int DEFAULT_CACHE_SIZE
      The default size of the bit cache.
      See Also:

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

    • DEFAULT_LOG_2_QUANTUM

      public static final int DEFAULT_LOG_2_QUANTUM
      The default base-two logarithm of the quantum.
      See Also:

    • n

      protected final long n
      The number of nodes of the graph.

    • upperBound

      protected final long 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 long cachedNode
      If not Long.MIN_VALUE, the node whose degree is cached in cachedOutdegree.

    • cachedOutdegree

      protected long cachedOutdegree
      If cachedNode is not Long.MIN_VALUE, its cached outdegree.

    • cachedPointer

      protected long cachedPointer
      If cachedNode is not Long.MIN_VALUE, the position immediately after the coding of the outdegree of cachedNode.

  • Constructor Details

  • Method Details

    • basename

      public CharSequence basename()
      Description copied from class: ImmutableGraph
      Returns a symbolic basename for this graph (optional operation).

      Implementors of this class may provide a basename (usually a pathname from which various files storing the graph are stemmed). This method is optional because it is sometimes unmeaningful (e.g., for one-off anonymous classes).

      Overrides:
      basename in class ImmutableGraph
      Returns:
      the basename.

    • lowerBits

      public static int lowerBits(long length, long upperBound)
      Returns the number of lower bits for the Elias–Fano encoding of a list of given length, upper bound and strictness.
      Parameters:
      length - the number of elements of the list.
      upperBound - an upper bound for the elements of the list.
      Returns:
      the number of bits for the Elias–Fano encoding of a list with the specified parameters.

    • pointerSize

      public static int pointerSize(long length, long upperBound)
      Returns the size in bits of forward or skip pointers to the Elias–Fano encoding of a list of given length, upper bound and strictness.
      Parameters:
      length - the number of elements of the list.
      upperBound - an upper bound for the elements of the list.
      Returns:
      the size of bits of forward or skip pointers the Elias–Fano encoding of a list with the specified parameters.

    • numberOfPointers

      public static long numberOfPointers(long length, long upperBound, int log2Quantum)
      Returns the number of forward or skip pointers to the Elias–Fano encoding of a list of given length, upper bound and strictness.
      Parameters:
      length - the number of elements of the list.
      upperBound - an upper bound for the elements of the list.
      log2Quantum - the logarithm of the quantum size.
      Returns:
      an upper bound on the number of skip pointers or the (exact) number of forward pointers.

    • load

      public static EFGraph load(CharSequence basename) throws IOException
      Creates a new EFGraph by loading a compressed graph file from disk to memory, with no progress logger and all offsets.
      Parameters:
      basename - the basename of the graph.
      Returns:
      a EFGraph containing the specified graph.
      Throws:
      IOException - if an I/O exception occurs while reading the graph.

    • load

      public static EFGraph load(CharSequence basename, ProgressLogger pl) throws IOException
      Creates a new EFGraph by loading a compressed graph file from disk to memory, with all offsets.
      Parameters:
      basename - the basename of the graph.
      pl - a progress logger used while loading the graph, or null.
      Returns:
      a EFGraph containing the specified graph.
      Throws:
      IOException - if an I/O exception occurs while reading the graph.

    • loadMapped

      public static EFGraph loadMapped(CharSequence basename) throws IOException
      Creates a new EFGraph by memory-mapping a graph file.
      Parameters:
      basename - the basename of the graph.
      Returns:
      an EFGraph containing the specified graph.
      Throws:
      IOException - if an I/O exception occurs while memory-mapping the graph or reading the offsets.

    • loadMapped

      public static EFGraph loadMapped(CharSequence basename, ProgressLogger pl) throws IOException
      Creates a new EFGraph by memory-mapping a graph file.
      Parameters:
      basename - the basename of the graph.
      pl - a progress logger used while loading the offsets, or null.
      Returns:
      an EFGraph containing the specified graph.
      Throws:
      IOException - if an I/O exception occurs while memory-mapping the graph or reading the offsets.

    • loadSequential

      @Deprecated public static EFGraph loadSequential(CharSequence basename, ProgressLogger pl) throws IOException
      Deprecated.
      Use loadOffline(CharSequence, ProgressLogger) or loadMapped(CharSequence, ProgressLogger) instead.
      Creates a new EFGraph by loading a compressed graph file from disk to memory, without offsets.
      Parameters:
      basename - the basename of the graph.
      pl - a progress logger used while loading the graph, or null.
      Returns:
      a EFGraph containing the specified graph.
      Throws:
      IOException - if an I/O exception occurs while reading the graph.

    • loadSequential

      @Deprecated public static EFGraph loadSequential(CharSequence basename) throws IOException
      Deprecated.
      Use loadOffline(CharSequence) or loadMapped(CharSequence) instead.
      Creates a new EFGraph by loading a compressed graph file from disk to memory, with no progress logger and without offsets.
      Parameters:
      basename - the basename of the graph.
      Returns:
      a EFGraph containing the specified graph.
      Throws:
      IOException - if an I/O exception occurs while reading the graph.

    • loadOffline

      public static EFGraph loadOffline(CharSequence basename, ProgressLogger pl) throws IOException
      Creates a new EFGraph by loading just the metadata of a compressed graph file.
      Parameters:
      basename - the basename of the graph.
      pl - a progress logger, or null.
      Returns:
      a EFGraph containing the specified graph.
      Throws:
      IOException - if an I/O exception occurs while reading the metadata.

    • loadOffline

      public static EFGraph loadOffline(CharSequence basename) throws IOException
      Creates a new EFGraph by loading just the metadata of a compressed graph file.
      Parameters:
      basename - the basename of the graph.
      Returns:
      a EFGraph containing the specified graph.
      Throws:
      IOException - if an I/O exception occurs while reading the metadata.

    • loadLongBigList

      public static LongBigArrayBigList loadLongBigList(CharSequence filename, ByteOrder byteOrder) throws IOException
      Commodity method for loading a big list of binary longs with specified endianness into a long big array which just delegates to EFGraph.loadLongBigList(CharSequence, ByteOrder).
      Parameters:
      filename - the file containing the longs.
      byteOrder - the endianness of the longs.
      Returns:
      a big list of longs containing the longs in filename.
      Throws:
      IOException

    • loadInternal

      protected static EFGraph loadInternal(CharSequence basename, boolean mapped, ProgressLogger pl) throws IOException
      Loads a compressed graph file from disk into this graph. Note that this method should be called only on a newly created graph.
      Parameters:
      basename - the basename of the graph.
      mapped - whether we want to memory-map the file.
      pl - a progress logger used while loading the graph, or null.
      Returns:
      this graph.
      Throws:
      IOException

    • store

      public static void store(ImmutableGraph graph, long upperBound, CharSequence basename, ProgressLogger pl) throws IOException
      Throws:
      IOException

    • store

      public static void store(ImmutableGraph graph, CharSequence basename, ProgressLogger pl) throws IOException
      Throws:
      IOException

    • store

      public static void store(ImmutableGraph graph, CharSequence basename) throws IOException
      Throws:
      IOException

    • store

      public static void store(ImmutableGraph graph, CharSequence basename, int log2Quantum, int cacheSize, ByteOrder byteOrder, ProgressLogger pl) throws IOException
      Throws:
      IOException

    • store

      public static void store(ImmutableGraph graph, long upperBound, CharSequence basename, int log2Quantum, int cacheSize, ByteOrder byteOrder, ProgressLogger pl) throws IOException
      Throws:
      IOException

    • 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()
      Description copied from class: ImmutableGraph
      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.

    • outdegree

      public long outdegree(long x)
      Description copied from class: ImmutableGraph
      Returns the outdegree of a node.
      Specified by:
      outdegree in class ImmutableGraph
      Parameters:
      x - a node.
      Returns:
      the outdegree of the given node.

    • successors

      public LazyLongSkippableIterator successors(long x)
      Description copied from class: ImmutableGraph
      Returns a lazy iterator over the successors of a given node. The iteration terminates when -1 is returned.
      Overrides:
      successors in class ImmutableGraph
      Parameters:
      x - a node.
      Returns:
      a lazy iterator over the successors of the node.

    • copy

      public EFGraph 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:

    • main

      public static void main(String[] args) throws SecurityException, IllegalAccessException, InvocationTargetException, NoSuchMethodException, IOException, JSAPException, ClassNotFoundException, InstantiationException
      Throws:
      SecurityException
      IllegalAccessException
      InvocationTargetException
      NoSuchMethodException
      IOException
      JSAPException
      ClassNotFoundException
      InstantiationException