Package it.unimi.dsi.big.webgraph

Class ArcListASCIIGraph

java.lang.Object

it.unimi.dsi.big.webgraph.ImmutableGraph

it.unimi.dsi.big.webgraph.ImmutableSequentialGraph

it.unimi.dsi.big.webgraph.ArcListASCIIGraph

All Implemented Interfaces:

it.unimi.dsi.lang.FlyweightPrototype<ImmutableGraph>

Direct Known Subclasses:

ShiftedByOneArcListASCIIGraph

public class ArcListASCIIGraph
extends ImmutableSequentialGraph

An ImmutableGraph that corresponds to graphs stored in a human-readable ASCII format were each line contains an arc.

The file format is very simple: each line contains an arc specified as two nodes separated by whitespace (but we suggest exactly one TAB character). Sources must be in increasing order, but targets can be in any order. The constructor provides an additional parameter, called shift, which will be added to all node indices. The default is 0, but for lists that number nodes starting from 1 it can be set to -1. Actually, the class ShiftedByOneArcListASCIIGraph can be used in place of this class for setting the shift to -1 without specifying additional parameters.

Contrarily to other classes, the load methods of this class do not always return instances of this class. In particular, loadOnce(InputStream) will return an instance of this class for read-once access. The instance will not provide offline or random access, but read-once access will be backed by the original input stream and only the successors of a single node 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: thus, it is limited to non-big graphs.

Using ArcListASCIIGraph to convert your data

A simple (albeit rather inefficient) way to import data into WebGraph is using ASCII graphs specified by arc lists. Suppose you create the following file, named example.arcs:

  0 1
  1 2
  2 1
  

Then, the command

  java it.unimi.dsi.webgraph.BVGraph -g ArcListASCIIGraph example.arcs bvexample
  

will produce a compressed graph in BVGraph format with basename bvexample. Even more convenient, and extremely more efficient, is the loadOnce(InputStream) method, which reads from an input stream an arc-list 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 arc-list 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 ArcListASCIIGraph dummy bvexample <example.arcs
  

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

Constructor	Description
ArcListASCIIGraph(InputStream is, int shift)	Creates a read-once arc-list ASCII graph.

Method Summary

Modifier and Type	Method	Description
static ImmutableGraph	load(CharSequence basename)
static ImmutableGraph	load(CharSequence basename, it.unimi.dsi.logging.ProgressLogger unused)
static ImmutableGraph	loadMapped(CharSequence basename)
static ImmutableGraph	loadMapped(CharSequence basename, it.unimi.dsi.logging.ProgressLogger unused)
static ImmutableGraph	loadOffline(CharSequence basename)
static ImmutableGraph	loadOffline(CharSequence basename, it.unimi.dsi.logging.ProgressLogger unused)
static ArcListASCIIGraph	loadOnce(InputStream is)
static ArcListASCIIGraph	loadOnce(InputStream is, int shift)
static ImmutableGraph	loadSequential(CharSequence basename)	Deprecated.
static ImmutableGraph	loadSequential(CharSequence basename, it.unimi.dsi.logging.ProgressLogger unused)	Deprecated.
static void	main(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, CharSequence basename)
static void	store(ImmutableGraph graph, CharSequence basename, int shift)	Stores an arc-list ASCII graph with a given shift.
static void	store(ImmutableGraph graph, 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 Details

ArcListASCIIGraph

public ArcListASCIIGraph(InputStream is,
 int shift)
                  throws NumberFormatException,
IOException

Creates a read-once arc-list 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 arc-list ASCII graph.

Throws:

NumberFormatException

IOException

Method Details

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(CharSequence basename)
                                     throws IOException

Deprecated.

Throws:

IOException

loadSequential

@Deprecated
public static ImmutableGraph loadSequential(CharSequence basename,
 it.unimi.dsi.logging.ProgressLogger unused)
                                     throws IOException

Deprecated.

Throws:

IOException

loadOffline

public static ImmutableGraph loadOffline(CharSequence basename)
                                  throws IOException

Throws:

IOException

loadOffline

public static ImmutableGraph loadOffline(CharSequence basename,
 it.unimi.dsi.logging.ProgressLogger unused)
                                  throws IOException

Throws:

IOException

loadMapped

public static ImmutableGraph loadMapped(CharSequence basename)
                                 throws IOException

Throws:

IOException

loadMapped

public static ImmutableGraph loadMapped(CharSequence basename,
 it.unimi.dsi.logging.ProgressLogger unused)
                                 throws IOException

Throws:

IOException

loadOnce

public static ArcListASCIIGraph loadOnce(InputStream is)
                                  throws IOException

Throws:

IOException

loadOnce

public static ArcListASCIIGraph loadOnce(InputStream is,
 int shift)
                                  throws IOException

Throws:

IOException

load

public static ImmutableGraph load(CharSequence basename)
                           throws IOException

Throws:

IOException

load

public static ImmutableGraph load(CharSequence basename,
 it.unimi.dsi.logging.ProgressLogger unused)
                           throws IOException

Throws:

IOException

store

public static void store(ImmutableGraph graph,
 CharSequence basename,
 it.unimi.dsi.logging.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,
 CharSequence basename,
 int shift)
                  throws IOException

Stores an arc-list ASCII graph with a given shift.

Parameters:

graph - a graph to be stored.

basename - the name of the output file.

shift - a shift that will be added to each node; note that is the opposite of the shift that will have to be used to load the generated file.

Throws:

IOException

main

public static void main(String[] args)
                 throws IllegalArgumentException,
SecurityException,
IllegalAccessException,
InvocationTargetException,
NoSuchMethodException,
IOException,
com.martiansoftware.jsap.JSAPException

Throws:

IllegalArgumentException

SecurityException

IllegalAccessException

InvocationTargetException

NoSuchMethodException

IOException

com.martiansoftware.jsap.JSAPException