it.unimi.dsi.webgraph
Class ASCIIGraph

java.lang.Object
  extended by it.unimi.dsi.webgraph.ImmutableGraph
      extended by it.unimi.dsi.webgraph.ImmutableSequentialGraph
          extended by it.unimi.dsi.webgraph.ASCIIGraph
All Implemented Interfaces:
FlyweightPrototype<ImmutableGraph>

public class ASCIIGraph
extends ImmutableSequentialGraph

An ImmutableGraph that corresponds to graphs stored in a human-readable ASCII format where each line contains the list of successors of a given node.

The file format is as follows: the graph is stored in a file named basename.graph-txt. The first line contains the number of nodes, n. Then, n lines follow, the i-th line containing the successors of node i in increasing order (nodes are numbered from 0 to n−1). Successors are separated by a single space.

Contrarily to other classes, the load methods of this class do not always return instances of this class. In particular, loadOffline(CharSequence) and loadOnce(InputStream) will return an instance of this class for offline access. The instance will not provide random access, but sequential access will be backed by the original text file and only one array of successor will be loaded in core memory at any time.

The load(CharSequence) method, on the other hand, will return an instance of ArrayListMutableGraph built by copying an offline instance of this class.

Using ASCIIGraph to convert your data

A simple (albeit rather inefficient) way to import data into WebGraph is using ASCII graphs. Suppose you create the following file, named example.graph-txt:

  2
  1
  0 1
  
Then, the command
  java it.unimi.dsi.webgraph.BVGraph -g ASCIIGraph example bvexample
  
will produce a compressed graph in BVGraph format with basename bvexample. Even more convenient is the loadOnce(InputStream) method, which reads from an input stream an ASCII graph and exposes it for a single traversal. It can be used, for instance, with the main method of BVGraph to generate somehow an ASCII graph and store it in compressed form on the fly. The previous example could be then rewritten as
  java it.unimi.dsi.webgraph.BVGraph -1 -g ASCIIGraph dummy bvexample <example.graph-txt
  


Nested Class Summary
 
Nested classes/interfaces inherited from class it.unimi.dsi.webgraph.ImmutableGraph
ImmutableGraph.LoadMethod
 
Field Summary
 
Fields inherited from class it.unimi.dsi.webgraph.ImmutableGraph
GRAPHCLASS_PROPERTY_KEY, PROPERTIES_EXTENSION
 
Constructor Summary
protected ASCIIGraph(CharSequence graphFile)
           
  ASCIIGraph(InputStream is)
          Creates a read-once ASCII graph.
 
Method Summary
static ImmutableGraph load(CharSequence basename)
           
static ImmutableGraph load(CharSequence basename, ProgressLogger unused)
           
static ASCIIGraph loadOffline(CharSequence basename)
           
static ASCIIGraph loadOffline(CharSequence basename, ProgressLogger unused)
           
static ASCIIGraph loadOnce(InputStream is)
           
static ImmutableGraph loadSequential(CharSequence basename)
           
static ASCIIGraph loadSequential(CharSequence basename, ProgressLogger unused)
           
static void main(String[] args)
           
 NodeIterator nodeIterator(int from)
          Returns a node iterator for scanning the graph sequentially, starting from the given node.
 int numNodes()
          Returns the number of nodes of this graph.
static void store(ImmutableGraph graph, CharSequence basename)
           
static void store(ImmutableGraph graph, CharSequence basename, ProgressLogger unused)
           
static void store(ImmutableGraph graph, int shift, CharSequence basename)
           
 
Methods inherited from class it.unimi.dsi.webgraph.ImmutableSequentialGraph
copy, outdegree, randomAccess, successorArray
 
Methods inherited from class it.unimi.dsi.webgraph.ImmutableGraph
basename, equals, hashCode, load, loadMapped, loadMapped, nodeIterator, numArcs, outdegrees, store, store, successors, toString
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
 

Constructor Detail

ASCIIGraph

protected ASCIIGraph(CharSequence graphFile)
              throws NumberFormatException,
                     IOException
Throws:
NumberFormatException
IOException

ASCIIGraph

public ASCIIGraph(InputStream is)
           throws NumberFormatException,
                  IOException
Creates a read-once ASCII graph. Instances created using this constructor can be only accessed using a single call to nodeIterator(int).

Parameters:
is - an input stream containing an ASCII graph.
Throws:
NumberFormatException
IOException
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.

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 ImmutableSequentialGraph
Parameters:
from - the node from which the iterator will iterate.
Returns:
a NodeIterator for accessing nodes and successors sequentially.

loadSequential

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

loadSequential

public static ASCIIGraph loadSequential(CharSequence basename,
                                        ProgressLogger unused)
                                 throws IOException
Throws:
IOException

loadOffline

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

loadOffline

public static ASCIIGraph loadOffline(CharSequence basename,
                                     ProgressLogger unused)
                              throws IOException
Throws:
IOException

loadOnce

public static ASCIIGraph loadOnce(InputStream is)
                           throws IOException
Throws:
IOException

load

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

load

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

store

public static void store(ImmutableGraph graph,
                         CharSequence basename,
                         ProgressLogger unused)
                  throws IOException
Throws:
IOException

store

public static void store(ImmutableGraph graph,
                         CharSequence basename)
                  throws IOException
Throws:
IOException

store

public static void store(ImmutableGraph graph,
                         int shift,
                         CharSequence basename)
                  throws IOException
Throws:
IOException

main

public static void main(String[] args)
                 throws IllegalArgumentException,
                        SecurityException,
                        IllegalAccessException,
                        InvocationTargetException,
                        NoSuchMethodException,
                        IOException,
                        JSAPException,
                        ClassNotFoundException,
                        InstantiationException
Throws:
IllegalArgumentException
SecurityException
IllegalAccessException
InvocationTargetException
NoSuchMethodException
IOException
JSAPException
ClassNotFoundException
InstantiationException