it.unimi.dsi.webgraph
Class ImmutableSubgraph

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

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.


Nested Class Summary
 
Nested classes/interfaces inherited from class it.unimi.dsi.webgraph.ImmutableGraph
ImmutableGraph.LoadMethod
 
Field Summary
protected  CharSequence basename
          The basename of this immutable subgraph, if it was loaded from disk, or null.
protected  int[] subgraphNode
          The nodes of the subgraph, in increasing order.
static String SUBGRAPHNODES_PROPERTY_KEY
          The standard property key for the name of the file containing the subgraph nodes.
protected  int subgraphSize
          The number of nodes in the subgraph.
protected  ImmutableGraph supergraph
          The supergraph.
protected  ImmutableSubgraph supergraphAsSubgraph
          If supergraph is an instance of ImmutableSubgraph, it is cached here.
static String SUPERGRAPHBASENAME_PROPERTY_KEY
          The standard property key for the supergraph basename.
protected  int[] supergraphNode
          A mapping from nodes of the supergraph to nodes in the subgraph (-1 for missing nodes).
protected  int supergraphNumNodes
          The number of nodes in the supergraph.
 
Fields inherited from class it.unimi.dsi.webgraph.ImmutableGraph
GRAPHCLASS_PROPERTY_KEY, PROPERTIES_EXTENSION
 
Constructor Summary
protected ImmutableSubgraph(ImmutableGraph immutableGraph)
          Creates a new immutable subgraph by wrapping an immutable graph.
  ImmutableSubgraph(ImmutableGraph supergraph, int[] subgraphNode)
          Creates a new immutable subgraph using a given backing node array.
  ImmutableSubgraph(ImmutableGraph supergraph, IntSet subgraphNodes)
          Creates a new immutable subgraph using a given subset of nodes.
protected ImmutableSubgraph(ImmutableSubgraph immutableSubgraph)
          Creates a new immutable subgraph by copying an existing one.
 
Method Summary
static ImmutableSubgraph asImmutableSubgraph(ImmutableGraph graph)
          Returns a subgraph view of the given immutable graph.
 CharSequence basename()
          Returns a symbolic basename for this graph (optional operation).
 ImmutableSubgraph copy()
          Returns a flyweight copy of this immutable graph.
 int fromRootNode(int x)
          Returns the index of a node of the root graph in this graph.
 int fromSupergraphNode(int x)
          Returns the index of a node of the supergraph in this graph.
static ImmutableGraph load(CharSequence basename)
           
static ImmutableGraph load(CharSequence basename, ProgressLogger pl)
           
protected static ImmutableGraph load(ImmutableGraph.LoadMethod method, CharSequence basename, ProgressLogger pl)
          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.
static ImmutableGraph loadOffline(CharSequence basename)
           
static ImmutableGraph loadOffline(CharSequence basename, ProgressLogger pl)
           
static ImmutableGraph loadSequential(CharSequence basename)
           
static ImmutableGraph loadSequential(CharSequence basename, ProgressLogger pl)
           
static void main(String[] args)
           
 NodeIterator nodeIterator(int from)
          Returns a node iterator for scanning the graph sequentially, starting from the given node.
 long numArcs()
          Returns the number of arcs of this graph (optional operation).
 int numNodes()
          Returns the number of nodes of this graph.
 int outdegree(int x)
          Returns the outdegree of a node.
 int outdegree(int x, LazyIntIterator supergraphSuccessors)
           
 boolean randomAccess()
          Checks whether this graph provides random access to successor lists.
 CharSequence rootBasename()
          Returns the basename of the root graph.
 void save(CharSequence basename)
           
 void save(CharSequence basename, ProgressLogger pl)
          Saves this immutable subgraph with a given basename.
static void store(ImmutableGraph graph, CharSequence basename)
          Throws an UnsupportedOperationException.
static void store(ImmutableGraph graph, CharSequence basename, ProgressLogger pm)
          Throws an UnsupportedOperationException.
 LazyIntIterator successors(int x)
          Returns a lazy iterator over the successors of a given node.
 int toRootNode(int x)
          Returns the index of a node of this graph in its root graph.
 int toSupergraphNode(int x)
          Returns the index of a node of this graph in its supergraph.
 
Methods inherited from class it.unimi.dsi.webgraph.ImmutableGraph
equals, hashCode, load, loadMapped, loadMapped, loadOnce, nodeIterator, outdegrees, store, store, successorArray, toString
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
 

Field Detail

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 Detail

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 Detail

numNodes

public int 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 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 CharSequence rootBasename()
Returns the basename of the root graph.

Returns:
the basename of the root graph.

toSupergraphNode

public int toSupergraphNode(int 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 int fromSupergraphNode(int 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 int toRootNode(int 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 int fromRootNode(int 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(int from)
Description copied from class: ImmutableGraph
Returns a node iterator for scanning the graph sequentially, starting from the given node.

This implementation just calls the random-access methods (ImmutableGraph.successors(int) and ImmutableGraph.outdegree(int)). More specific implementations may choose to maintain some extra state to make the enumeration more efficient.

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 LazyIntIterator successors(int x)
Description copied from class: ImmutableGraph
Returns a lazy iterator over the successors of a given node. The iteration terminates when -1 is returned.

This implementation just wraps the array returned by ImmutableGraph.successorArray(int). Subclasses are encouraged to override this implementation.

The semantics of this method has been significantly modified in WebGraph 2.0 to take advantage of the new, faster lazy architecture.

Overrides:
successors in class ImmutableGraph
Parameters:
x - a node.
Returns:
a lazy iterator over the successors of the node.

outdegree

public int outdegree(int 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 int outdegree(int x,
                     LazyIntIterator supergraphSuccessors)

copy

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

public static ImmutableGraph loadSequential(CharSequence basename)
                                     throws IOException
Throws:
IOException

loadSequential

public static ImmutableGraph loadSequential(CharSequence basename,
                                            ProgressLogger pl)
                                     throws IOException
Throws:
IOException

loadOffline

public static ImmutableGraph loadOffline(CharSequence basename)
                                  throws IOException
Throws:
IOException

loadOffline

public static ImmutableGraph loadOffline(CharSequence basename,
                                         ProgressLogger pl)
                                  throws IOException
Throws:
IOException

load

public static ImmutableGraph load(CharSequence basename)
                           throws IOException
Throws:
IOException

load

public static ImmutableGraph load(CharSequence basename,
                                  ProgressLogger pl)
                           throws IOException
Throws:
IOException

load

protected static ImmutableGraph load(ImmutableGraph.LoadMethod method,
                                     CharSequence basename,
                                     ProgressLogger pl)
                              throws 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:
IOException

store

public static void store(ImmutableGraph graph,
                         CharSequence basename,
                         ProgressLogger pm)
Throws an UnsupportedOperationException.


store

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


save

public void save(CharSequence basename,
                 ProgressLogger pl)
          throws 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:
IOException

save

public void save(CharSequence basename)
          throws IOException
Throws:
IOException

main

public static void main(String[] args)
                 throws IllegalArgumentException,
                        SecurityException,
                        JSAPException,
                        UnsupportedEncodingException,
                        FileNotFoundException
Throws:
IllegalArgumentException
SecurityException
JSAPException
UnsupportedEncodingException
FileNotFoundException