Class ImmutableSubgraph
- java.lang.Object
-
- it.unimi.dsi.big.webgraph.ImmutableGraph
-
- it.unimi.dsi.big.webgraph.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 methodstoSupergraphNode(long)
andfromSupergraphNode(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 inDataOutput
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 inDataInput
format. 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 genericImmutableGraph
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)
andtoRootNode(long)
may be used to access information about the root (i.e., the unique highest graph in the hierarchy: note that it cannot be anImmutableSubgraph
).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.big.webgraph.ImmutableGraph
ImmutableGraph.LoadMethod
-
-
Field Summary
Fields Modifier and Type Field Description protected java.lang.CharSequence
basename
The basename of this immutable subgraph, if it was loaded from disk, ornull
.protected long[][]
subgraphNode
The nodes of the subgraph, in increasing order.static java.lang.String
SUBGRAPHNODES_PROPERTY_KEY
The standard property key for the name of the file containing the subgraph nodes.protected long
subgraphSize
The number of nodes in the subgraph.protected ImmutableGraph
supergraph
The supergraph.protected ImmutableSubgraph
supergraphAsSubgraph
Ifsupergraph
is an instance ofImmutableSubgraph
, it is cached here.static java.lang.String
SUPERGRAPHBASENAME_PROPERTY_KEY
The standard property key for the supergraph basename.protected long[][]
supergraphNode
A mapping from nodes of the supergraph to nodes in the subgraph (-1 for missing nodes).protected long
supergraphNumNodes
The number of nodes in the supergraph.-
Fields inherited from class it.unimi.dsi.big.webgraph.ImmutableGraph
GRAPHCLASS_PROPERTY_KEY, NUMBER_OF_THREADS_PROPERTY, PROPERTIES_EXTENSION
-
-
Constructor Summary
Constructors Modifier Constructor Description protected
ImmutableSubgraph(ImmutableGraph immutableGraph)
Creates a new immutable subgraph by wrapping an immutable graph.ImmutableSubgraph(ImmutableGraph supergraph, long[][] subgraphNode)
Creates a new immutable subgraph using a given backing node array.protected
ImmutableSubgraph(ImmutableSubgraph immutableSubgraph)
Creates a new immutable subgraph by copying an existing one.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Deprecated Methods Modifier and Type Method Description static ImmutableSubgraph
asImmutableSubgraph(ImmutableGraph graph)
Returns a subgraph view of the given immutable graph.java.lang.CharSequence
basename()
Returns a symbolic basename for this graph (optional operation).ImmutableSubgraph
copy()
Returns a flyweight copy of this immutable graph.long
fromRootNode(long x)
Returns the index of a node of the root graph in this graph.long
fromSupergraphNode(long x)
Returns the index of a node of the supergraph in this graph.boolean
hasCopiableIterators()
Whether the node iterators returned by this graph supportNodeIterator.copy(long)
.protected static ImmutableGraph
load(ImmutableGraph.LoadMethod method, java.lang.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 thesupergraphclass
property within the property file (namedbasename.properties
), and loading the subgraph array in memory.static ImmutableGraph
load(java.lang.CharSequence basename)
static ImmutableGraph
load(java.lang.CharSequence basename, it.unimi.dsi.logging.ProgressLogger pl)
static ImmutableGraph
loadMapped(java.lang.CharSequence basename)
static ImmutableGraph
loadMapped(java.lang.CharSequence basename, it.unimi.dsi.logging.ProgressLogger pl)
static ImmutableGraph
loadOffline(java.lang.CharSequence basename)
static ImmutableGraph
loadOffline(java.lang.CharSequence basename, it.unimi.dsi.logging.ProgressLogger pl)
static ImmutableGraph
loadSequential(java.lang.CharSequence basename)
Deprecated.static ImmutableGraph
loadSequential(java.lang.CharSequence basename, it.unimi.dsi.logging.ProgressLogger pl)
Deprecated.static void
main(java.lang.String[] args)
NodeIterator
nodeIterator(long 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).long
numNodes()
Returns the number of nodes of this graph.long
outdegree(long x)
Returns the outdegree of a node.long
outdegree(long x, LazyLongIterator supergraphSuccessors)
boolean
randomAccess()
Checks whether this graph provides random access to successor lists.java.lang.CharSequence
rootBasename()
Returns the basename of the root graph.void
save(java.lang.CharSequence basename)
void
save(java.lang.CharSequence basename, it.unimi.dsi.logging.ProgressLogger pl)
Saves this immutable subgraph with a given basename.static void
store(ImmutableGraph graph, java.lang.CharSequence basename)
Throws anUnsupportedOperationException
.static void
store(ImmutableGraph graph, java.lang.CharSequence basename, it.unimi.dsi.logging.ProgressLogger pm)
Throws anUnsupportedOperationException
.LazyLongIterator
successors(long x)
Returns a lazy iterator over the successors of a given node.long
toRootNode(long x)
Returns the index of a node of this graph in its root graph.long
toSupergraphNode(long x)
Returns the index of a node of this graph in its supergraph.-
Methods inherited from class it.unimi.dsi.big.webgraph.ImmutableGraph
equals, hashCode, intNumNodes, load, loadOnce, nodeIterator, outdegrees, splitNodeIterators, store, store, successorBigArray, toString, wrap, wrap
-
-
-
-
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.
-
supergraphAsSubgraph
protected final ImmutableSubgraph supergraphAsSubgraph
Ifsupergraph
is an instance ofImmutableSubgraph
, it is cached here.
-
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, ornull
.
-
-
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 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:
numNodes
in classImmutableGraph
- 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 classImmutableGraph
- 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 classImmutableGraph
- Returns:
- true if this graph provides random access to successor lists.
-
hasCopiableIterators
public boolean hasCopiableIterators()
Description copied from class:ImmutableGraph
Whether the node iterators returned by this graph supportNodeIterator.copy(long)
.- Overrides:
hasCopiableIterators
in classImmutableGraph
- Returns:
- true if this graph provides copiable iterators.
-
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 classImmutableGraph
- 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 ifx
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 ifx
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 classImmutableGraph
- 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 classImmutableGraph
- 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 classImmutableGraph
- 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 interfaceit.unimi.dsi.lang.FlyweightPrototype<ImmutableGraph>
- Specified by:
copy
in classImmutableGraph
- 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 thesupergraphclass
property within the property file (namedbasename.properties
), and loading the subgraph array in memory. The exact load method to be used depends on themethod
argument.- 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:
java.io.IOException
-
store
public static void store(ImmutableGraph graph, java.lang.CharSequence basename, it.unimi.dsi.logging.ProgressLogger pm)
Throws anUnsupportedOperationException
.
-
store
public static void store(ImmutableGraph graph, java.lang.CharSequence basename)
Throws anUnsupportedOperationException
.
-
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, ornull
.- 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
-
-