Class ImmutableSubgraph
- All Implemented Interfaces:
it.unimi.dsi.lang.FlyweightPrototype<ImmutableGraph>
- Direct Known Subclasses:
DegreeRangeImmutableSubgraph
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 inDataInputformat. If this property is not present, it is assumed to bebasename.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.
-
Nested Class Summary
Nested classes/interfaces inherited from class it.unimi.dsi.webgraph.ImmutableGraph
ImmutableGraph.LoadMethod -
Field Summary
FieldsModifier and TypeFieldDescriptionprotected CharSequenceThe basename of this immutable subgraph, if it was loaded from disk, ornull.protected final int[]The nodes of the subgraph, in increasing order.static final StringThe standard property key for the name of the file containing the subgraph nodes.protected final intThe number of nodes in the subgraph.protected final ImmutableGraphThe supergraph.protected final ImmutableSubgraphIfsupergraphis an instance ofImmutableSubgraph, it is cached here.static final StringThe standard property key for the supergraph basename.protected final int[]A mapping from nodes of the supergraph to nodes in the subgraph (-1 for missing nodes).protected final intThe number of nodes in the supergraph.Fields inherited from class it.unimi.dsi.webgraph.ImmutableGraph
GRAPHCLASS_PROPERTY_KEY, NUMBER_OF_THREADS_PROPERTY, PROPERTIES_EXTENSION -
Constructor Summary
ConstructorsModifierConstructorDescriptionprotectedImmutableSubgraph(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, it.unimi.dsi.fastutil.ints.IntSet subgraphNodes) Creates a new immutable subgraph using a given subset of nodes.protectedImmutableSubgraph(ImmutableSubgraph immutableSubgraph) Creates a new immutable subgraph by copying an existing one. -
Method Summary
Modifier and TypeMethodDescriptionstatic ImmutableSubgraphReturns a subgraph view of the given immutable graph.basename()Returns a symbolic basename for this graph (optional operation).copy()Returns a flyweight copy of this immutable graph.intfromRootNode(int x) Returns the index of a node of the root graph in this graph.intfromSupergraphNode(int x) Returns the index of a node of the supergraph in this graph.booleanWhether the node iterators returned by this graph supportNodeIterator.copy(int).protected static ImmutableGraphload(ImmutableGraph.LoadMethod method, CharSequence basename, it.unimi.dsi.logging.ProgressLogger pl) Creates a new immutable subgraph by loading the supergraph, delegating the actual loading to the class specified in thesupergraphclassproperty within the property file (namedbasename.properties), and loading the subgraph array in memory.static ImmutableGraphload(CharSequence basename) static ImmutableGraphload(CharSequence basename, it.unimi.dsi.logging.ProgressLogger pl) static ImmutableGraphloadMapped(CharSequence basename) static ImmutableGraphloadMapped(CharSequence basename, it.unimi.dsi.logging.ProgressLogger pl) static ImmutableGraphloadOffline(CharSequence basename) static ImmutableGraphloadOffline(CharSequence basename, it.unimi.dsi.logging.ProgressLogger pl) static ImmutableGraphloadSequential(CharSequence basename) Deprecated.static ImmutableGraphloadSequential(CharSequence basename, it.unimi.dsi.logging.ProgressLogger pl) Deprecated.static voidnodeIterator(int from) Returns a node iterator for scanning the graph sequentially, starting from the given node.longnumArcs()Returns the number of arcs of this graph (optional operation).intnumNodes()Returns the number of nodes of this graph.intoutdegree(int x) Returns the outdegree of a node.intoutdegree(int x, LazyIntIterator supergraphSuccessors) booleanChecks whether this graph provides random access to successor lists.Returns the basename of the root graph.voidsave(CharSequence basename) voidsave(CharSequence basename, it.unimi.dsi.logging.ProgressLogger pl) Saves this immutable subgraph with a given basename.static voidstore(ImmutableGraph graph, CharSequence basename) Throws anUnsupportedOperationException.static voidstore(ImmutableGraph graph, CharSequence basename, it.unimi.dsi.logging.ProgressLogger pm) Throws anUnsupportedOperationException.successors(int x) Returns a lazy iterator over the successors of a given node.inttoRootNode(int x) Returns the index of a node of this graph in its root graph.inttoSupergraphNode(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, loadOnce, nodeIterator, outdegrees, splitNodeIterators, store, store, successorArray, toString
-
Field Details
-
SUBGRAPHNODES_PROPERTY_KEY
The standard property key for the name of the file containing the subgraph nodes.- See Also:
-
SUPERGRAPHBASENAME_PROPERTY_KEY
The standard property key for the supergraph basename.- See Also:
-
supergraph
The supergraph. -
supergraphAsSubgraph
Ifsupergraphis an instance ofImmutableSubgraph, it is cached here. -
subgraphNode
protected final int[] subgraphNodeThe nodes of the subgraph, in increasing order. -
supergraphNode
protected final int[] supergraphNodeA mapping from nodes of the supergraph to nodes in the subgraph (-1 for missing nodes). -
subgraphSize
protected final int subgraphSizeThe number of nodes in the subgraph. -
supergraphNumNodes
protected final int supergraphNumNodesThe number of nodes in the supergraph. -
basename
The basename of this immutable subgraph, if it was loaded from disk, ornull.
-
-
Constructor Details
-
ImmutableSubgraph
public ImmutableSubgraph(ImmutableGraph supergraph, it.unimi.dsi.fastutil.ints.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
Creates a new immutable subgraph using a given backing node array.Note that
subgraphNodeis 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
Creates a new immutable subgraph by copying an existing one.- Parameters:
immutableSubgraph- an immutable subgraph.
-
ImmutableSubgraph
Creates a new immutable subgraph by wrapping an immutable graph.- Parameters:
immutableGraph- an immutable graph.
-
-
Method Details
-
numNodes
public int numNodes()Description copied from class:ImmutableGraphReturns the number of nodes of this graph.Albeit this method is not optional, it is allowed that this method throws an
UnsupportedOperationExceptionif this graph has never been entirely traversed using anode iterator. This apparently bizarre behaviour is necessary to support implementations asArcListASCIIGraph, which do not know the actual number of nodes until a traversal has been completed.- Specified by:
numNodesin classImmutableGraph- Returns:
- the number of nodes.
-
numArcs
public long numArcs()Description copied from class:ImmutableGraphReturns the number of arcs of this graph (optional operation).- Overrides:
numArcsin classImmutableGraph- Returns:
- the number of arcs.
-
randomAccess
public boolean randomAccess()Description copied from class:ImmutableGraphChecks whether this graph provides random access to successor lists.- Specified by:
randomAccessin classImmutableGraph- Returns:
- true if this graph provides random access to successor lists.
-
hasCopiableIterators
public boolean hasCopiableIterators()Description copied from class:ImmutableGraphWhether the node iterators returned by this graph supportNodeIterator.copy(int).- Overrides:
hasCopiableIteratorsin classImmutableGraph- Returns:
- true if this graph provides copiable iterators.
-
basename
Description copied from class:ImmutableGraphReturns a symbolic basename for this graph (optional operation).- Overrides:
basenamein classImmutableGraph- Returns:
- the basename.
-
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
xin 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
xin this graph, or a negative value ifxdoes 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
xin 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
xin this graph, or a negative value ifxdoes not belong to the root graph.
-
nodeIterator
Description copied from class:ImmutableGraphReturns a node iterator for scanning the graph sequentially, starting from the given node.- Overrides:
nodeIteratorin classImmutableGraph- Parameters:
from- the node from which the iterator will iterate.- Returns:
- a
NodeIteratorfor accessing nodes and successors sequentially.
-
successors
Description copied from class:ImmutableGraphReturns a lazy iterator over the successors of a given node. The iteration terminates when -1 is returned.- Overrides:
successorsin classImmutableGraph- Parameters:
x- a node.- Returns:
- a lazy iterator over the successors of the node.
-
outdegree
public int outdegree(int x) Description copied from class:ImmutableGraphReturns the outdegree of a node.- Specified by:
outdegreein classImmutableGraph- Parameters:
x- a node.- Returns:
- the outdegree of the given node.
-
outdegree
-
copy
Description copied from class:ImmutableGraphReturns a flyweight copy of this immutable graph.- Specified by:
copyin interfaceit.unimi.dsi.lang.FlyweightPrototype<ImmutableGraph>- Specified by:
copyin classImmutableGraph- Returns:
- a flyweight copy of this immutable graph.
- See Also:
-
asImmutableSubgraph
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.- Throws:
IOException
-
loadSequential
@Deprecated public static ImmutableGraph loadSequential(CharSequence basename, it.unimi.dsi.logging.ProgressLogger pl) throws IOException Deprecated.- Throws:
IOException
-
loadOffline
- Throws:
IOException
-
loadOffline
public static ImmutableGraph loadOffline(CharSequence basename, it.unimi.dsi.logging.ProgressLogger pl) throws IOException - Throws:
IOException
-
load
- Throws:
IOException
-
load
public static ImmutableGraph load(CharSequence basename, it.unimi.dsi.logging.ProgressLogger pl) throws IOException - Throws:
IOException
-
loadMapped
public static ImmutableGraph loadMapped(CharSequence basename, it.unimi.dsi.logging.ProgressLogger pl) throws IOException - Throws:
IOException
-
loadMapped
- Throws:
IOException
-
load
protected static ImmutableGraph load(ImmutableGraph.LoadMethod method, CharSequence basename, it.unimi.dsi.logging.ProgressLogger pl) throws IOException Creates a new immutable subgraph by loading the supergraph, delegating the actual loading to the class specified in thesupergraphclassproperty within the property file (namedbasename.properties), and loading the subgraph array in memory. The exact load method to be used depends on themethodargument.- Parameters:
method- the method to be used to load the supergraph.basename- the basename of the graph.pl- the progress logger; it can benull.- Returns:
- an immutable subgraph containing the specified graph.
- Throws:
IOException
-
store
public static void store(ImmutableGraph graph, CharSequence basename, it.unimi.dsi.logging.ProgressLogger pm) Throws anUnsupportedOperationException. -
store
Throws anUnsupportedOperationException. -
save
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, ornull.- Throws:
IOException
-
save
- Throws:
IOException
-
main
public static void main(String[] args) throws IllegalArgumentException, SecurityException, com.martiansoftware.jsap.JSAPException, UnsupportedEncodingException, FileNotFoundException - Throws:
IllegalArgumentExceptionSecurityExceptioncom.martiansoftware.jsap.JSAPExceptionUnsupportedEncodingExceptionFileNotFoundException
-