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.
#
StingerGraphs.StingerConfig
— Type.
Used to set the configuration of the STINGER data structure.
#
StingerGraphs.StingerEdge
— Type.
The STINGER Edge representation.
#
StingerGraphs.StingerVertex
— Type.
The STINGER Vertex representation.
#
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.
#
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.
#
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.
#
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.
#
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.
#
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.
#
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
#
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.
#
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)
#
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.
#
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.
#
StingerGraphs.getsuccessors
— Method.
getsuccessors(s::Stinger, src::Int64)
Returns a Vector
of indices representing the successors of src
.
#
StingerGraphs.getvertex
— Method.
getvertex(s::Stinger, v::Int64)
Load the specified vertex from the STINGER datastructure.
#
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.
#
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).
#
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.
#
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.
#
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.
#
StingerGraphs.outdegree
— Method.
outdegree(s::Stinger, src::Int64)
Returns the outdegree of vertex index.
#
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.
#
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.
#
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
.
#
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.
#
Base.setindex!
— Method.
setindex!(x::Stinger, val, field::StingerFields)
Set value of a field from the Stinger data structure.
#
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.
#
StingerGraphs.storageptr
— Method.
storageptr(s::Stinger)
Get a pointer to the storage array of the STINGER data structure