Package it.unimi.dsi.webgraph

Class ImmutableSubgraph

java.lang.Object
it.unimi.dsi.webgraph.ImmutableGraph
it.unimi.dsi.webgraph.ImmutableSubgraph
All Implemented Interfaces:
FlyweightPrototype<ImmutableGraph>
Direct Known Subclasses:
DegreeRangeImmutableSubgraph
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 IntSet 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(int) and fromSupergraphNode(int) 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 integers 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 integers 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(int) and toRootNode(int) 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 Details

    • SUBGRAPHNODES_PROPERTY_KEY

      public static final 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 String SUPERGRAPHBASENAME_PROPERTY_KEY
      The standard property key for the supergraph basename.
      See Also:
      Constant Field Values

    • supergraph

      protected final ImmutableGraph supergraph
      The supergraph.

    • supergraphAsSubgraph

      protected final ImmutableSubgraph supergraphAsSubgraph
      If supergraph is an instance of ImmutableSubgraph, it is cached here.

    • subgraphNode

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

    • supergraphNode

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

    • subgraphSize

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

    • supergraphNumNodes

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

    • basename

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

  • Constructor Details

    • ImmutableSubgraph

      public ImmutableSubgraph​(ImmutableGraph supergraph, IntSet subgraphNodes)
      Creates a new immutable subgraph using a given subset of nodes.
      Parameters:
      supergraph - the supergraph.
      subgraphNodes - the set of nodes defining the induced subgraph.

    • ImmutableSubgraph

      public ImmutableSubgraph​(ImmutableGraph supergraph, int[] 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 Details