Package it.unimi.dsi.big.webgraph

Class ImmutableSubgraph

  • All Implemented Interfaces:
    it.unimi.dsi.lang.FlyweightPrototype<ImmutableGraph>
    public class ImmutableSubgraph
extends ImmutableGraph
    An induced subgraph of a given immutable graph.

    Warning: this class is experimental, and might be subject to changes.

    The nodes of the subgraph are specified via an LongSet or an array of integers. Of course, each node in the subgraph will have a different index than the corresponding node in the supergraph. The two methods toSupergraphNode(long) and fromSupergraphNode(long) are used to translate indices back and forth.

    An immutable subgraph is stored as a property file (which follows the convention established in ImmutableGraph), and as a node subset file. The latter must contain an (increasing) list of longs in DataOutput format representing the set of nodes of the subgraph.

    The property file, with named basename.properties, contains the following entries:

    • supergraphbasename: the basename of the supergraph. Note that this name is system-dependent: it is suggested that you use a path-free filename.
    • subgraphnodes: the filename of the node subset file, which must be an list of longs in DataInput format. If this property is not present, it is assumed to be basename.subgraphnodes.

    You can create an immutable subgraph using the public constructor, or you can load one using one of the provided load methods. Note that there is no store method, because it makes no sense to store a generic ImmutableGraph as a subgraph. There is, however, a save method that allows one to save the files related to a subgraph (the property file and the subgraph node file).

    Root graphs

    When creating tree-shaped hierarchies of subgraphs, the methods rootBasename(), fromRootNode(long) and toRootNode(long) may be used to access information about the root (i.e., the unique highest graph in the hierarchy: note that it cannot be an ImmutableSubgraph).

    Should you need to treat uniformly a generic immutable graph as an immutable subgraph, the method asImmutableSubgraph(ImmutableGraph) will return a subgraph view of the given immutable graph in which all to/from functions are identities.

    • Field Detail

      • SUBGRAPHNODES_PROPERTY_KEY

        public static final java.lang.String SUBGRAPHNODES_PROPERTY_KEY
        The standard property key for the name of the file containing the subgraph nodes.
        See Also:
        Constant Field Values

      • SUPERGRAPHBASENAME_PROPERTY_KEY

        public static final java.lang.String SUPERGRAPHBASENAME_PROPERTY_KEY
        The standard property key for the supergraph basename.
        See Also:
        Constant Field Values

      • supergraph

        protected final ImmutableGraph supergraph
        The supergraph.

      • subgraphNode

        protected final long[][] subgraphNode
        The nodes of the subgraph, in increasing order.

      • supergraphNode

        protected final long[][] supergraphNode
        A mapping from nodes of the supergraph to nodes in the subgraph (-1 for missing nodes).

      • subgraphSize

        protected final long subgraphSize
        The number of nodes in the subgraph.

      • supergraphNumNodes

        protected final long supergraphNumNodes
        The number of nodes in the supergraph.

      • basename

        protected java.lang.CharSequence basename
        The basename of this immutable subgraph, if it was loaded from disk, or null.

    • Constructor Detail

      • ImmutableSubgraph

        public ImmutableSubgraph​(ImmutableGraph supergraph,
                         long[][] subgraphNode)
        Creates a new immutable subgraph using a given backing node array.

        Note that subgraphNode is not copied: thus, it must not be modified until this subgraph is no longer in use.

        Parameters:
        supergraph - the supergraph.
        subgraphNode - an increasing array containing the nodes defining the induced subgraph.

      • ImmutableSubgraph

        protected ImmutableSubgraph​(ImmutableSubgraph immutableSubgraph)
        Creates a new immutable subgraph by copying an existing one.
        Parameters:
        immutableSubgraph - an immutable subgraph.

      • ImmutableSubgraph

        protected ImmutableSubgraph​(ImmutableGraph immutableGraph)
        Creates a new immutable subgraph by wrapping an immutable graph.
        Parameters:
        immutableGraph - an immutable graph.

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

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

      • rootBasename

        public java.lang.CharSequence rootBasename()
        Returns the basename of the root graph.
        Returns:
        the basename of the root graph.

      • toSupergraphNode

        public long toSupergraphNode​(long x)
        Returns the index of a node of this graph in its supergraph.
        Parameters:
        x - an index of a node in this graph.
        Returns:
        the index of node x in the supergraph.

      • fromSupergraphNode

        public long fromSupergraphNode​(long x)
        Returns the index of a node of the supergraph in this graph.
        Parameters:
        x - an index of a node in the supergraph.
        Returns:
        the index of node x in this graph, or a negative value if x does not belong to the subgraph.

      • toRootNode

        public long toRootNode​(long x)
        Returns the index of a node of this graph in its root graph.
        Parameters:
        x - an index of a node in this graph.
        Returns:
        the index of node x in the root graph.

      • fromRootNode

        public long fromRootNode​(long x)
        Returns the index of a node of the root graph in this graph.
        Parameters:
        x - an index of a node in the root graph.
        Returns:
        the index of node x in this graph, or a negative value if x does not belong to the root graph.

      • nodeIterator

        public NodeIterator nodeIterator​(long from)
        Description copied from class: ImmutableGraph
        Returns a node iterator for scanning the graph sequentially, starting from the given node.
        Overrides:
        nodeIterator in class ImmutableGraph
        Parameters:
        from - the node from which the iterator will iterate.
        Returns:
        a NodeIterator for accessing nodes and successors sequentially.

      • successors

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

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

      • outdegree

        public long outdegree​(long x,
                      LazyLongIterator supergraphSuccessors)

      • copy

        public ImmutableSubgraph 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

      • asImmutableSubgraph

        public static ImmutableSubgraph asImmutableSubgraph​(ImmutableGraph graph)
        Returns a subgraph view of the given immutable graph.

        The wrapper returned by this method may be used whenever immutable graphs and subgraphs must be mixed.

        Parameters:
        graph - an immutable graph.
        Returns:
        the given graph, viewed as a trivial subgraph of itself.

      • loadSequential

        @Deprecated
public static ImmutableGraph loadSequential​(java.lang.CharSequence basename)
                                     throws java.io.IOException
        Deprecated.
        Throws:
        java.io.IOException

      • loadSequential

        @Deprecated
public static ImmutableGraph loadSequential​(java.lang.CharSequence basename,
                                            it.unimi.dsi.logging.ProgressLogger pl)
                                     throws java.io.IOException
        Deprecated.
        Throws:
        java.io.IOException

      • loadOffline

        public static ImmutableGraph loadOffline​(java.lang.CharSequence basename)
                                  throws java.io.IOException
        Throws:
        java.io.IOException

      • loadOffline

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

      • load

        public static ImmutableGraph load​(java.lang.CharSequence basename)
                           throws java.io.IOException
        Throws:
        java.io.IOException

      • load

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

      • loadMapped

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

      • loadMapped

        public static ImmutableGraph loadMapped​(java.lang.CharSequence basename)
                                 throws java.io.IOException
        Throws:
        java.io.IOException

      • load

        protected static ImmutableGraph load​(ImmutableGraph.LoadMethod method,
                                     java.lang.CharSequence basename,
                                     it.unimi.dsi.logging.ProgressLogger pl)
                              throws java.io.IOException
        Creates a new immutable subgraph by loading the supergraph, delegating the actual loading to the class specified in the supergraphclass property within the property file (named basename.properties), and loading the subgraph array in memory. The exact load method to be used depends on the method argument.
        Parameters:
        method - the method to be used to load the supergraph.
        basename - the basename of the graph.
        pl - the progress logger; it can be null.
        Returns:
        an immutable subgraph containing the specified graph.
        Throws:
        java.io.IOException

      • store

        public static void store​(ImmutableGraph graph,
                         java.lang.CharSequence basename,
                         it.unimi.dsi.logging.ProgressLogger pm)
        Throws an UnsupportedOperationException.

      • store

        public static void store​(ImmutableGraph graph,
                         java.lang.CharSequence basename)
        Throws an UnsupportedOperationException.

      • save

        public void save​(java.lang.CharSequence basename,
                 it.unimi.dsi.logging.ProgressLogger pl)
          throws java.io.IOException
        Saves this immutable subgraph with a given basename.

        Note that this method will not save the supergraph, but only the subgraph files, that is, the subgraph property file (with extension .properties) and the file containing the subgraph nodes (with extension .nodes). A reference to the supergraph basename will be stored in the property file.

        Parameters:
        basename - the basename to be used to save the subgraph.
        pl - a progress logger, or null.
        Throws:
        java.io.IOException

      • save

        public void save​(java.lang.CharSequence basename)
          throws java.io.IOException
        Throws:
        java.io.IOException

      • main

        public static void main​(java.lang.String[] args)
                 throws java.lang.IllegalArgumentException,
                        java.lang.SecurityException,
                        com.martiansoftware.jsap.JSAPException,
                        java.io.UnsupportedEncodingException,
                        java.io.FileNotFoundException
        Throws:
        java.lang.IllegalArgumentException
        java.lang.SecurityException
        com.martiansoftware.jsap.JSAPException
        java.io.UnsupportedEncodingException
        java.io.FileNotFoundException