Package it.unimi.dsi.big.webgraph

Class ASCIIGraph

java.lang.Object

it.unimi.dsi.big.webgraph.ImmutableGraph

it.unimi.dsi.big.webgraph.ImmutableSequentialGraph

it.unimi.dsi.big.webgraph.ASCIIGraph

All Implemented Interfaces:

it.unimi.dsi.lang.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 a wrapped instance of ArrayListMutableGraph built by copying a wrapped 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.big.webgraph.ImmutableGraph

ImmutableGraph.LoadMethod

Field Summary

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
	ASCIIGraph(java.io.InputStream is)	Creates a read-once ASCII graph.
protected	ASCIIGraph(java.lang.CharSequence graphFile)

Method Summary

Modifier and Type	Method	Description
static ImmutableGraph	load(java.lang.CharSequence basename)
static ImmutableGraph	load(java.lang.CharSequence basename, it.unimi.dsi.logging.ProgressLogger unused)
static ASCIIGraph	loadMapped(java.lang.CharSequence basename)
static ASCIIGraph	loadMapped(java.lang.CharSequence basename, it.unimi.dsi.logging.ProgressLogger unused)
static ASCIIGraph	loadOffline(java.lang.CharSequence basename)
static ASCIIGraph	loadOffline(java.lang.CharSequence basename, it.unimi.dsi.logging.ProgressLogger unused)
static ASCIIGraph	loadOnce(java.io.InputStream is)
static ImmutableGraph	loadSequential(java.lang.CharSequence basename)	Deprecated.
static ASCIIGraph	loadSequential(java.lang.CharSequence basename, it.unimi.dsi.logging.ProgressLogger unused)	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	numNodes()	Returns the number of nodes of this graph.
static void	store(ImmutableGraph graph, java.lang.CharSequence basename)
static void	store(ImmutableGraph graph, java.lang.CharSequence basename, it.unimi.dsi.logging.ProgressLogger unused)

Methods inherited from class it.unimi.dsi.big.webgraph.ImmutableSequentialGraph

copy, outdegree, randomAccess, successorBigArray

Methods inherited from class it.unimi.dsi.big.webgraph.ImmutableGraph

basename, equals, hasCopiableIterators, hashCode, intNumNodes, load, nodeIterator, numArcs, outdegrees, splitNodeIterators, store, store, successors, toString, wrap, wrap

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

ASCIIGraph

protected ASCIIGraph(java.lang.CharSequence graphFile)
              throws java.lang.NumberFormatException,
                     java.io.IOException

Throws:

java.lang.NumberFormatException

java.io.IOException

ASCIIGraph

public ASCIIGraph(java.io.InputStream is)
           throws java.lang.NumberFormatException,
                  java.io.IOException

Creates a read-once ASCII graph. Instances created using this constructor can be only accessed using a single call to nodeIterator(long).

Parameters:

is - an input stream containing an ASCII graph.

Throws:

java.lang.NumberFormatException

java.io.IOException

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 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(long from)

Description copied from class: ImmutableGraph

Returns a node iterator for scanning the graph sequentially, starting from the given node.

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

@Deprecated
public static ImmutableGraph loadSequential(java.lang.CharSequence basename)
                                     throws java.io.IOException

Deprecated.

Throws:

java.io.IOException

loadSequential

@Deprecated
public static ASCIIGraph loadSequential(java.lang.CharSequence basename,
                                        it.unimi.dsi.logging.ProgressLogger unused)
                                 throws java.io.IOException

Deprecated.

Throws:

java.io.IOException

loadOffline

public static ASCIIGraph loadOffline(java.lang.CharSequence basename)
                              throws java.io.IOException

Throws:

java.io.IOException

loadOffline

public static ASCIIGraph loadOffline(java.lang.CharSequence basename,
                                     it.unimi.dsi.logging.ProgressLogger unused)
                              throws java.io.IOException

Throws:

java.io.IOException

loadMapped

public static ASCIIGraph loadMapped(java.lang.CharSequence basename)
                             throws java.io.IOException

Throws:

java.io.IOException

loadMapped

public static ASCIIGraph loadMapped(java.lang.CharSequence basename,
                                    it.unimi.dsi.logging.ProgressLogger unused)
                             throws java.io.IOException

Throws:

java.io.IOException

loadOnce

public static ASCIIGraph loadOnce(java.io.InputStream is)
                           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 unused)
                           throws java.io.IOException

Throws:

java.io.IOException

store

public static void store(ImmutableGraph graph,
                         java.lang.CharSequence basename,
                         it.unimi.dsi.logging.ProgressLogger unused)
                  throws java.io.IOException

Throws:

java.io.IOException

store

public static void store(ImmutableGraph graph,
                         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,
                        java.lang.IllegalAccessException,
                        java.lang.reflect.InvocationTargetException,
                        java.lang.NoSuchMethodException,
                        java.io.IOException,
                        com.martiansoftware.jsap.JSAPException,
                        java.lang.ClassNotFoundException,
                        java.lang.InstantiationException

Throws:

java.lang.IllegalArgumentException

java.lang.SecurityException

java.lang.IllegalAccessException

java.lang.reflect.InvocationTargetException

java.lang.NoSuchMethodException

java.io.IOException

com.martiansoftware.jsap.JSAPException

java.lang.ClassNotFoundException

java.lang.InstantiationException