SimpleValueGraphs.jl

SimpleValueGraphs is a Graphs.jl compatible package for graphs with multiple, homogeneous vertex, edge and graph metadata. In particular it provides:

• an abstract interface for graphs with metadata
• concrete implementations of mutable graphs with metadata

Compared to SimpleWeightedGraphs.jl it has the following advantages:

• vertex and graph metadata
• multiple edge metadata
• faster structural modifications of graphs

Compared to MetaGraphs.jl it has the following advantages:

• faster access and modifications of metadata
• better type stability when accessing metadata

Example

using SimpleValueGraphs

using Graphs: smallgraph
using Plots
using GraphRecipes: graphplot
using Colors: RGB, Color

# Load a Graphs.SimpleGraph
gs = smallgraph(:house)

# Convert to a ValGraph with vertex and edge values
gv = ValGraph(gs;
    # Two names vertex values:
    # - color: A random color
    # - label: The vertex identifier as a string
    vertexval_types=(color=Color, label=String),
    vertexval_init=v -> (rand(RGB), string(v)),
    # One unnamed edge value:
    # A string s -- d from source to destination of each edge
    edgeval_types=(String, ),
    edgeval_init=(s, d) -> ("$s -- $d",)
)

# Plot this graph using the vertex and edge values
graphplot(gv;
    nodecolor = [get_vertexval(gv, v, :color) for v in vertices(gv)],
    names = [get_vertexval(gv, v, :label) for v in vertices(gv)],
    edgelabel=weights(gv; zerovalue="")
)

Benchmarks

This is a comparison of running Graphs.dijkstra_shortest_paths on the egonets-Facebook graph for multiple graph types.

| graph type | time (ms) | | ------------------------------------------------- | --------- | | Graphs.SimpleGraph + Matrix weights | 6.5 | | Graphs.SimpleGraph + SparseMatrixCSC weights | 11.4 | | SimpleWeightedGraphs.SimpleWeightedGraph | 11.7 | | MetaGraphs.MetaGraph | 141.9 | | SimpleValueGraphs.ValGraph | 12.4 |

Currently a lot of Graphs.jl algorithms do not optimally work with graphs that store edge metadata internally. The next benchmark is an optimized version of the same algorithm that can be found in SimpleValueGraphs.Experimental.dijkstra_shortests_pasts. Clearly, this is a huge improvement for ValGraph and SimpleWeightedGraph.

| graph type | time (ms) | | ------------------------------------------------- | --------- | | Graphs.SimpleGraph + Matrix weights | 6.8 | | Graphs.SimpleGraph + SparseMatrixCSC weights | 10.8 | | SimpleWeightedGraphs.SimpleWeightedGraph | 2.9 | | MetaGraphs.MetaGraph | 147.3 | | SimpleValueGraphs.ValGraph | 3.1 |