|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectit.unimi.dsi.webgraph.ImmutableGraph
it.unimi.dsi.webgraph.ImmutableSubgraph
public class ImmutableSubgraph
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).
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 |
---|
public static final String SUBGRAPHNODES_PROPERTY_KEY
public static final String SUPERGRAPHBASENAME_PROPERTY_KEY
protected final ImmutableGraph supergraph
protected final ImmutableSubgraph supergraphAsSubgraph
supergraph
is an instance of ImmutableSubgraph
, it is cached here.
protected final int[] subgraphNode
protected final int[] supergraphNode
protected final int subgraphSize
protected final int supergraphNumNodes
protected CharSequence basename
null
.
Constructor Detail |
---|
public ImmutableSubgraph(ImmutableGraph supergraph, IntSet subgraphNodes)
supergraph
- the supergraph.subgraphNodes
- the set of nodes defining the induced subgraph.public ImmutableSubgraph(ImmutableGraph supergraph, int[] subgraphNode)
Note that subgraphNode
is not copied: thus, it must not
be modified until this subgraph is no longer in use.
supergraph
- the supergraph.subgraphNode
- an increasing array containing the nodes defining the induced subgraph.protected ImmutableSubgraph(ImmutableSubgraph immutableSubgraph)
immutableSubgraph
- an immutable subgraph.protected ImmutableSubgraph(ImmutableGraph immutableGraph)
immutableGraph
- an immutable graph.Method Detail |
---|
public int numNodes()
ImmutableGraph
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.
numNodes
in class ImmutableGraph
public long numArcs()
ImmutableGraph
numArcs
in class ImmutableGraph
public boolean randomAccess()
ImmutableGraph
randomAccess
in class ImmutableGraph
public CharSequence basename()
ImmutableGraph
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).
basename
in class ImmutableGraph
public CharSequence rootBasename()
public int toSupergraphNode(int x)
x
- an index of a node in this graph.
x
in the supergraph.public int fromSupergraphNode(int x)
x
- an index of a node in the supergraph.
x
in this graph, or a negative value if x
does not belong to the subgraph.public int toRootNode(int x)
x
- an index of a node in this graph.
x
in the root graph.public int fromRootNode(int x)
x
- an index of a node in the root graph.
x
in this graph, or a negative value if x
does not belong to the root graph.public NodeIterator nodeIterator(int from)
ImmutableGraph
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.
nodeIterator
in class ImmutableGraph
from
- the node from which the iterator will iterate.
NodeIterator
for accessing nodes and successors sequentially.public LazyIntIterator successors(int x)
ImmutableGraph
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.
successors
in class ImmutableGraph
x
- a node.
public int outdegree(int x)
ImmutableGraph
outdegree
in class ImmutableGraph
x
- a node.
public int outdegree(int x, LazyIntIterator supergraphSuccessors)
public ImmutableSubgraph copy()
ImmutableGraph
copy
in interface FlyweightPrototype<ImmutableGraph>
copy
in class ImmutableGraph
FlyweightPrototype
public static ImmutableSubgraph asImmutableSubgraph(ImmutableGraph graph)
The wrapper returned by this method may be used whenever immutable graphs and subgraphs must be mixed.
graph
- an immutable graph.
public static ImmutableGraph loadSequential(CharSequence basename) throws IOException
IOException
public static ImmutableGraph loadSequential(CharSequence basename, ProgressLogger pl) throws IOException
IOException
public static ImmutableGraph loadOffline(CharSequence basename) throws IOException
IOException
public static ImmutableGraph loadOffline(CharSequence basename, ProgressLogger pl) throws IOException
IOException
public static ImmutableGraph load(CharSequence basename) throws IOException
IOException
public static ImmutableGraph load(CharSequence basename, ProgressLogger pl) throws IOException
IOException
protected static ImmutableGraph load(ImmutableGraph.LoadMethod method, CharSequence basename, ProgressLogger pl) throws IOException
method
argument.
method
- the method to be used to load the supergraph.basename
- the basename of the graph.pl
- the progress logger; it can be null
.
IOException
public static void store(ImmutableGraph graph, CharSequence basename, ProgressLogger pm)
UnsupportedOperationException
.
public static void store(ImmutableGraph graph, CharSequence basename)
UnsupportedOperationException
.
public void save(CharSequence basename, ProgressLogger pl) throws IOException
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.
basename
- the basename to be used to save the subgraph.pl
- a progress logger, or null
.
IOException
public void save(CharSequence basename) throws IOException
IOException
public static void main(String[] args) throws IllegalArgumentException, SecurityException, JSAPException, UnsupportedEncodingException, FileNotFoundException
IllegalArgumentException
SecurityException
JSAPException
UnsupportedEncodingException
FileNotFoundException
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |