Class EFGraph

  • All Implemented Interfaces:
    it.unimi.dsi.lang.FlyweightPrototype<ImmutableGraph>

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

      Constructors 
      Modifier Constructor Description
      protected EFGraph​(java.lang.CharSequence basename, long n, long m, long upperBound, int log2Quantum, it.unimi.dsi.fastutil.longs.LongBigList graph, it.unimi.dsi.fastutil.longs.LongBigList offsets)  
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods Deprecated Methods 
      Modifier and Type Method Description
      java.lang.CharSequence basename()
      Returns a symbolic basename for this graph (optional operation).
      EFGraph copy()
      Returns a flyweight copy of this immutable graph.
      static EFGraph load​(java.lang.CharSequence basename)
      Creates a new EFGraph by loading a compressed graph file from disk to memory, with no progress logger and all offsets.
      static EFGraph load​(java.lang.CharSequence basename, it.unimi.dsi.logging.ProgressLogger pl)
      Creates a new EFGraph by loading a compressed graph file from disk to memory, with all offsets.
      protected static EFGraph loadInternal​(java.lang.CharSequence basename, boolean mapped, it.unimi.dsi.logging.ProgressLogger pl)
      Loads a compressed graph file from disk into this graph.
      static it.unimi.dsi.fastutil.longs.LongBigArrayBigList loadLongBigList​(java.lang.CharSequence filename, java.nio.ByteOrder byteOrder)
      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).
      static EFGraph loadMapped​(java.lang.CharSequence basename)
      Creates a new EFGraph by memory-mapping a graph file.
      static EFGraph loadMapped​(java.lang.CharSequence basename, it.unimi.dsi.logging.ProgressLogger pl)
      Creates a new EFGraph by memory-mapping a graph file.
      static EFGraph loadOffline​(java.lang.CharSequence basename)
      Creates a new EFGraph by loading just the metadata of a compressed graph file.
      static EFGraph loadOffline​(java.lang.CharSequence basename, it.unimi.dsi.logging.ProgressLogger pl)
      Creates a new EFGraph by loading just the metadata of a compressed graph file.
      static EFGraph loadSequential​(java.lang.CharSequence basename)
      static EFGraph loadSequential​(java.lang.CharSequence basename, it.unimi.dsi.logging.ProgressLogger pl)
      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.
      static void main​(java.lang.String[] args)  
      long numArcs()
      Returns the number of arcs of this graph (optional operation).
      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.
      long numNodes()
      Returns the number of nodes of this graph.
      long outdegree​(long x)
      Returns the outdegree of a node.
      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.
      boolean randomAccess()
      Checks whether this graph provides random access to successor lists.
      static void store​(ImmutableGraph graph, long upperBound, java.lang.CharSequence basename, int log2Quantum, int cacheSize, java.nio.ByteOrder byteOrder, it.unimi.dsi.logging.ProgressLogger pl)  
      static void store​(ImmutableGraph graph, long upperBound, java.lang.CharSequence basename, it.unimi.dsi.logging.ProgressLogger pl)  
      static void store​(ImmutableGraph graph, java.lang.CharSequence basename)  
      static void store​(ImmutableGraph graph, java.lang.CharSequence basename, int log2Quantum, int cacheSize, java.nio.ByteOrder byteOrder, it.unimi.dsi.logging.ProgressLogger pl)  
      static void store​(ImmutableGraph graph, java.lang.CharSequence basename, it.unimi.dsi.logging.ProgressLogger pl)  
      LazyLongSkippableIterator successors​(long x)
      Returns a lazy iterator over the successors of a given node.
      • Methods inherited from class java.lang.Object

        clone, finalize, getClass, notify, notifyAll, wait, wait, wait
    • Field Detail

      • GRAPH_EXTENSION

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

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

        public static final java.lang.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 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 it.unimi.dsi.fastutil.longs.LongBigList graph
        The list containing the graph.
      • offsets

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

        protected final java.lang.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 Detail

      • EFGraph

        protected EFGraph​(java.lang.CharSequence basename,
                          long n,
                          long m,
                          long upperBound,
                          int log2Quantum,
                          it.unimi.dsi.fastutil.longs.LongBigList graph,
                          it.unimi.dsi.fastutil.longs.LongBigList offsets)
    • Method Detail

      • basename

        public java.lang.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​(java.lang.CharSequence basename)
                            throws java.io.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:
        java.io.IOException - if an I/O exception occurs while reading the graph.
      • load

        public static EFGraph load​(java.lang.CharSequence basename,
                                   it.unimi.dsi.logging.ProgressLogger pl)
                            throws java.io.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:
        java.io.IOException - if an I/O exception occurs while reading the graph.
      • loadMapped

        public static EFGraph loadMapped​(java.lang.CharSequence basename)
                                  throws java.io.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:
        java.io.IOException - if an I/O exception occurs while memory-mapping the graph or reading the offsets.
      • loadMapped

        public static EFGraph loadMapped​(java.lang.CharSequence basename,
                                         it.unimi.dsi.logging.ProgressLogger pl)
                                  throws java.io.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:
        java.io.IOException - if an I/O exception occurs while memory-mapping the graph or reading the offsets.
      • loadSequential

        @Deprecated
        public static EFGraph loadSequential​(java.lang.CharSequence basename,
                                             it.unimi.dsi.logging.ProgressLogger pl)
                                      throws java.io.IOException
        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:
        java.io.IOException - if an I/O exception occurs while reading the graph.
      • loadSequential

        @Deprecated
        public static EFGraph loadSequential​(java.lang.CharSequence basename)
                                      throws java.io.IOException
        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:
        java.io.IOException - if an I/O exception occurs while reading the graph.
      • loadOffline

        public static EFGraph loadOffline​(java.lang.CharSequence basename,
                                          it.unimi.dsi.logging.ProgressLogger pl)
                                   throws java.io.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:
        java.io.IOException - if an I/O exception occurs while reading the metadata.
      • loadOffline

        public static EFGraph loadOffline​(java.lang.CharSequence basename)
                                   throws java.io.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:
        java.io.IOException - if an I/O exception occurs while reading the metadata.
      • loadLongBigList

        public static it.unimi.dsi.fastutil.longs.LongBigArrayBigList loadLongBigList​(java.lang.CharSequence filename,
                                                                                      java.nio.ByteOrder byteOrder)
                                                                               throws java.io.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:
        java.io.IOException
      • loadInternal

        protected static EFGraph loadInternal​(java.lang.CharSequence basename,
                                              boolean mapped,
                                              it.unimi.dsi.logging.ProgressLogger pl)
                                       throws java.io.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:
        java.io.IOException
      • store

        public static void store​(ImmutableGraph graph,
                                 long upperBound,
                                 java.lang.CharSequence basename,
                                 it.unimi.dsi.logging.ProgressLogger pl)
                          throws java.io.IOException
        Throws:
        java.io.IOException
      • store

        public static void store​(ImmutableGraph graph,
                                 java.lang.CharSequence basename,
                                 it.unimi.dsi.logging.ProgressLogger pl)
                          throws java.io.IOException
        Throws:
        java.io.IOException
      • store

        public static void store​(ImmutableGraph graph,
                                 java.lang.CharSequence basename)
                          throws java.io.IOException
        Throws:
        java.io.IOException
      • store

        public static void store​(ImmutableGraph graph,
                                 java.lang.CharSequence basename,
                                 int log2Quantum,
                                 int cacheSize,
                                 java.nio.ByteOrder byteOrder,
                                 it.unimi.dsi.logging.ProgressLogger pl)
                          throws java.io.IOException
        Throws:
        java.io.IOException
      • store

        public static void store​(ImmutableGraph graph,
                                 long upperBound,
                                 java.lang.CharSequence basename,
                                 int log2Quantum,
                                 int cacheSize,
                                 java.nio.ByteOrder byteOrder,
                                 it.unimi.dsi.logging.ProgressLogger pl)
                          throws java.io.IOException
        Throws:
        java.io.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 it.unimi.dsi.lang.FlyweightPrototype<ImmutableGraph>
        Specified by:
        copy in class ImmutableGraph
        Returns:
        a flyweight copy of this immutable graph.
        See Also:
        FlyweightPrototype
      • main

        public static void main​(java.lang.String[] args)
                         throws java.lang.SecurityException,
                                java.lang.IllegalAccessException,
                                java.lang.reflect.InvocationTargetException,
                                java.lang.NoSuchMethodException,
                                java.io.IOException,
                                com.martiansoftware.jsap.JSAPException,
                                java.lang.ClassNotFoundException,
                                java.lang.InstantiationException
        Throws:
        java.lang.SecurityException
        java.lang.IllegalAccessException
        java.lang.reflect.InvocationTargetException
        java.lang.NoSuchMethodException
        java.io.IOException
        com.martiansoftware.jsap.JSAPException
        java.lang.ClassNotFoundException
        java.lang.InstantiationException