Graph File Formats

Table of Contents

• EdgeList File Format
• AdjacencyList File Format
• Working with Files
  • Reading and Writing
  • Local Access

The STAG library supports two simple file formats for storing graphs on disk: EdgeList and AdjacencyList.

EdgeList File Format

In an EdgeList file, each line in the file corresponds to one edge in the graph. A line consists of two node IDs which should be integers and optionally an edge weight which can be a real number. The IDs and weight should be separated with spaces.

For example, here is a simple EdgeList file.

# This is a comment
0 1
1 2
2 0

This file defines a graph on three nodes (0, 1, and 2) with three edges: (0, 1), (1, 2), and (0, 2). Here is another example, which specifies edge weights.

# The third number on each row is the weight of the edge.
0 1 0.5
1 2 1
2 0 3

AdjacencyList File Format

In an AdjacencyList file, each line in the file corresponds to one node in the graph. A line consists of the node ID, followed by a list of adjacent nodes. The node IDs at the beginning of each line must be sorted in increasing order. For example, here is a simple AdjacencyList file.

# This is a comment
0: 1 2
1: 0 3 2
2: 0 1
3: 1

In this example, the node with ID 1 has edges to nodes 0, 2, and 3. All edges are taken to have weight 1. The following example shows how to specify the weight of each edge.

# The number after each colon is the weight of the edge.
0: 1:0.5 2:0.5
1: 0:0.5 2:1
2: 0:0.5 1:1

Here, the node with ID 1 has an edge of weight 0.5 to node 0 and an edge of weight 1 to node 2.

Working with Files

Reading and Writing

The stag.graphio module provides several methods for reading, writing and converting between EdgeList and AdjacencyList files. For example, the following code will read an AdjacencyList file and create a stag.graph.Graph object.

import stag.graphio
import stag.graph
 
# Load the graph from the file
filename = "mygraph.al"
my_graph = stag.graphio.load_adjacencylist(filename)
 
# Display the adjacency matrix of the graph
print(my_graph.adjacency())

The following example will generate a random graph and save it as an edgelist.

import stag.graph
import stag.graphio
import stag.random
 
# Create a random graph
my_graph = stag.random.erdos_renyi(100, 0.1)
 
# Save the graph
filename = "mygraph.edgelist"
stag.graphio.save_edgelist(my_graph, filename)

The stag.graphio.edgelist_to_adjacencylist and stag.graphio.adjacencylist_to_edgelist methods allow for conversion between the two file formats.

Local Access

When working with huge graphs, the stag.graph.AdjacencyListLocalGraph object provides a way to query a graph locally without loading the entire graph into memory. For example, the following code will query the neighbours of the node with ID 100.

import stag.graph
 
# Create the local graph object
filename = "mygraph.adjacencylist"
my_graph = stag.graph.AdjacencyListLocalGraph(filename)
 
# Display the neighbors of node 100
neighbors = my_graph.neighbors_unweighted(100)
print(neighbors)

One of the most useful applications of the stag.graph.AdjacencyListLocalGraph object is for local clustering. The following example finds a cluster containing node 100.

import stag.graph
import stag.cluster
 
# Create the local graph object
filename = "mygraph.adjacencylist"
my_graph = stag.graph.AdjacencyListLocalGraph(filename)
 
# Find and display a cluster
node_id = 100
target_volume = 1000
cluster = stag.cluster.local_cluster(my_graph, node_id, target_volume)
print(cluster)