Skip to content

A LightGraphs.jl compatible graph package for graphs with multiple vertex, edge and graph metadata.

License

Notifications You must be signed in to change notification settings

simonschoelly/SimpleValueGraphs.jl

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

SimpleValueGraphs.jl

version Stable Dev CI codecov

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="")
)

example output

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