Graph Formats

We support the adjacency graph format used by the Problem Based Benchmark suite and Ligra.

The adjacency graph format starts with a sequence of offsets one for each vertex, followed by a sequence of directed edges ordered by their source vertex. The offset for a vertex i refers to the location of the start of a contiguous block of out edges for vertex i in the sequence of edges. The block continues until the offset of the next vertex, or the end if i is the last vertex. All vertices and offsets are 0 based and represented in decimal. The specific format is as follows:

AdjacencyGraph

<n>

<m>

<o0>

<o1>

...

<o(n-1)>

<e0>

<e1>

...

<e(m-1)>

This file is represented as plain text.

Weighted graphs are represented in the weighted adjacency graph format. The file should start with the string "WeightedAdjacencyGraph". The m edge weights should be stored after all of the edge targets in the .adj file.

Using SNAP graphs

Graphs from the SNAP dataset collection are commonly used for graph algorithm benchmarks. We provide a tool that converts the most common SNAP graph format to the adjacency graph format that GBBS accepts. Usage example:

# Download a graph from the SNAP collection.

wget https://snap.stanford.edu/data/wiki-Vote.txt.gz

gzip --decompress ${PWD}/wiki-Vote.txt.gz

# Run the SNAP-to-adjacency-graph converter.

# Run with Bazel:

bazel run //utils:snap_converter -- -s -i ${PWD}/wiki-Vote.txt -o <output file>

# Or run with Make:

# cd utils

# make snap_converter

# ./snap_converter -s -i <input file> -o <output file>