StingerGraphs

StingerGraphs is a Julia wrapper around the STINGER library for processing streaming/dynamic graphs. This wrapper is built around the dev branch of the STINGER repository.

Contents

Installation

Pkg.clone("https://github.com/stingergraph/UnsafeAtomics.jl")
Pkg.clone("https://github.com/stingergraph/StingerGraphs.jl")
Pkg.build("StingerGraphs")

STINGER version

Default version

By default, the package will try to download and build its own version of STINGER. The version downloaded along with the package is the latest release found here. It follows the dev branch of STINGER.

Custom STINGER version

If you wish to use a different version of STINGER, you can set the environment variable STINGER_LIB_PATH with the path to the folder containing the shared library libstinger_core and libstinger_alg.

Guide

The Stinger type

The Stinger type can be used to create a new STINGER data structure. Due to the use of variable length attributes in the C STINGER data structure, we are unable to use a Julia type to directly map to a STINGER type (http://docs.julialang.org/en/release-0.4/manual/calling-c-and-fortran-code/#struct-type-correspondences). So we use the C pointer handle to interact with the STINGER library in the implementation.

Creating STINGER graphs

julia> s = Stinger() # Creates a new STINGER
StingerGraphs.Stinger(Ptr{Void} @0x000000012317e000)

We have registered finalizers with Julia that automatically frees your STINGER data structure, the next time the GC runs after it goes out of scope.

Adding and Removing edges

Use the insert_edge! and remove_edge! to add and remove edges respectively. They return the value of 1 on success.

julia> s = Stinger()
StingerGraphs.Stinger(Ptr{Void} @0x000000012317e000)
julia> insert_edge!(s, 0, 1, 4, 2, 2)
1

julia> remove_edge!(s, 0, 1, 4)
1

insert_edges! and remove_edges! can be used to add or remove multiple edges.

Iterating through the edges

Use foralledges to iterate through the edges of a vertex. The edgeparse function can help parse the edge and create a StingerEdge.

julia> foralledges(s, 1) do edge, src, etype
           direction, neighbor = edgeparse(edge)
           println("$direction, $neighbor, $etype")
       end
2, 4, 0

BFS

bfs allows BFS to be run on Stinger graphs. Serial and parallel versions of the algorithm are available. Please check the API docs for more details.

julia> s = Stinger()
StingerGraphs.Stinger(Ptr{Void} @0x000000012317e000)
julia> for i=1:5
           insert_edge!(s, 0, i, i+1, 1)
       end
julia> bfs(s, 1, 7)
7-element Array{Int64,1}:
    -2
    -1
    1
    2
    3
    4
    5

K-core

kcore runs k-core decompositions on the graph.

julia> labels, counts = kcore(s, 7)
([0, 1, 1, 1, 1, 1, 0], [0, 0, 0, 0, 0, 0, 0])

Consistency Checks

The STINGER graph can be checked for consistency using the consistency_check function. It returns true if consistent or false if inconsistent.

julia> consistency_check(s, 1) # number of vertices.
true

API Documentation

# StingerGraphs.Stinger — Type.

The Stinger type is the Julia type representing a STINGER data structure created in C. It stores the handle to the C data structure. The C data structure is automatically freed when the finalizer runs.

source

# StingerGraphs.StingerConfig — Type.

Used to set the configuration of the STINGER data structure.

source

# StingerGraphs.StingerEdge — Type.

The STINGER Edge representation.

source

# StingerGraphs.StingerVertex — Type.

The STINGER Vertex representation.

source

# StingerGraphs.bfs — Method.

bfs(alg::LevelSynchronous, s::Stinger, source::Int64, nv::Int64)

Uses the LevelSynchronous algorithm to perform a parallel BFS with the specified source node.

source

# StingerGraphs.bfs — Method.

bfs(s::Stinger, source::Int64, nv::Int64)

bfs returns a parents array of length nv. An empty array is returned on failure.

source

# StingerGraphs.bfs — Method.

bfs(s::Stinger, source::Int64)

This version is slower as it allocates the maximum possible vertices in the Stinger graph. If you know the maximum number of active vertices, call bfs(s, source, nv) which is faster.

source

# StingerGraphs.bfsdistances — Method.

bfsdistances(s::Stinger, source::Int64, nv::Int64)

Obtain both the parents array as well as the distances from source. Empty arrays are returned on failure.

source

# StingerGraphs.bfsdistances — Method.

bfsdistances(s::Stinger, source::Int64)

This version is slower as it allocates the maximum possible vertices in the Stinger graph. If you know the maximum number of active vertices, call bfsdistances(s, source, nv) which is faster.

source

# StingerGraphs.consistency_check — Method.

consistency_check(s::Stinger, nv::Int64)

Runs a consistency check on the STINGER data structure. Returns true if the check passed and false if it fails.

source

# StingerGraphs.edgeparse — Method.

edgeparse(edge::StingerEdge)

Parse the direction and neighbor given a StingerEdge. The first 2 bits of the neighbor field of the edge denotes the direction. 1 - in, 2 - out, 3 - both

source

# StingerGraphs.edgeweight — Method.

edgeweight(s::Stinger, src::Int64, dst::Int64, etype::Int64)

Return the weight of the edge between src and dst of type etype. If it doesn't exist return 0.

source

# StingerGraphs.foralledges — Method.

foralledges(f::Function, s::Stinger, v::Int64)

Iterates over all the edges edges of a vertex and applies a function to each edge. The function should take 3 arguments. f(current_edge::StingerEdge, vertexid::Int64, etype::Int64)

source

# StingerGraphs.generateconfig — Method.

generateconfig(nv::Int64; netypes::Int64=1, nvtypes::Int64=1)

Generates a config for the specified number and types of vertices and the number of edge types. The generated config attempts to maximize the number of edge blocks that can be allocated.

source

# StingerGraphs.get_nv — Method.

get_nv(x::Stinger)

Returns number of active vertices in the graph. This is based on the largest vertex ID which has a non-zero indegree or outdegree.

source

# StingerGraphs.getsuccessors — Method.

getsuccessors(s::Stinger, src::Int64)

Returns a Vector of indices representing the successors of src.

source

# StingerGraphs.getvertex — Method.

getvertex(s::Stinger, v::Int64)

Load the specified vertex from the STINGER datastructure.

source

# StingerGraphs.insert_edge! — Method.

insert_edge!(
    s::Stinger, etype::Int64, from::Int64, to::Int64, weight::Int64,
    timestamp::Int64
)

Inserts an edge of type etype from from to to into the STINGER graph s with the specified weight and timestamp. Raises an error if the operation was not successful.

source

# StingerGraphs.insert_edges! — Method.

insert_edges!(s::Stinger, edges::AbstractArray, numedges::Integer)

Inserts numedges edges into the STINGER graph s. Input format is 5×numedges (etype, src, dst, weight, times).

source

# StingerGraphs.kcore — Method.

kcore(s::Stinger, nv::Int64)

Finds the kcore of the graph. Uses the kcore_find function exposed by the C STINGER library. Returns the labels and the counts as two Vector{Int64}s.

source

# StingerGraphs.kcore — Method.

kcore(s::Stinger)

This version is slower as it makes a call to stinger_max_active_vertex, which is sequential and runs through every vertex in the graph. If you know the maximum number of active vertices, call kcore(s, nv) which is faster.

source

# StingerGraphs.kronecker — Method.

kronecker(
    scale::Int64,
    edgefactor::Int64;
    a::Float64=0.57,
    b::Float64=0.19,
    c::Float64=0.19
)

Generates edges for a Kronecker generator graph. Returns an array of 2 rows with 1st being the start edge and 2nd row having the end edge.

source

# StingerGraphs.outdegree — Method.

outdegree(s::Stinger, src::Int64)

Returns the outdegree of vertex index.

source

# StingerGraphs.remove_edge! — Method.

remove_edge!(s::Stinger, etype::Int64, from::Int64, to::Int64)

Removes the edge of type etype from from to to from the STINGER graph s. Raises an error in the edge was not found or if there was an error while removing the edge.

source

# StingerGraphs.remove_edges! — Method.

remove_edges!(s::Stinger, edges::AbstractArray, numedges::Integer)

Removes numedges from the STINGER graph s. Input format is 5×numedges (etype, src, dst, weight, times) to make consistent with insert_edges!. Only the src, dst and etype fields matter.

source

# StingerGraphs.stingerconfig — Method.

stingerconfig(
    nv, nebs=0, netypes=0, nvtypes=0, memory_size=0, no_map_none_etype=0,
    no_map_none_vtype=0, no_resize=0)

Creates a StingerConfig.

source

# Base.getindex — Method.

getindex(x::Stinger, field::StingerFields)

Obtain value of a field from the Stinger data structure. For batch_time and update_time, use get_batchtime and get_updatetime respectively.

source

# Base.setindex! — Method.

setindex!(x::Stinger, val, field::StingerFields)

Set value of a field from the Stinger data structure.

source

# StingerGraphs.loadstingergraph — Method.

loadstingergraph(s::Stinger)

Use this to get a StingerGraph representation of your Stinger graph. This representation will not be kept in sync with the graph. If you make changes, you will need to call this again to load the graph with the new attributes.

source

# StingerGraphs.storageptr — Method.

storageptr(s::Stinger)

Get a pointer to the storage array of the STINGER data structure

source