I’m happy to announce the first (of hopefully many) custom graph interfaces to LightGraphs.jl. SimpleWeightedGraphs is a proof-of-concept that was mostly hammered out at JuliaCon. As its name might imply, it provides weighted edges, and all functions that can take weights (such as shortest path calculations) will work seamlessly with this graph structure:
using LightGraphs, SimpleWeightedGraphs
g = SimpleWeightedGraph(3)
add_edge!(g, 1, 2, 0.5)
add_edge!(g, 2, 3, 0.8)
add_edge!(g, 1, 3, 2.0)
# find the shortest path from vertex 1 to vertex 3 taking weights into account.
enumerate_paths(dijkstra_shortest_paths(g, 1), 3)
3-element Array{Int64,1}:
1
2
3
# reweight the edge from 1 to 2
add_edge!(g, 1, 2, 1.6)
# rerun the shortest path calculation from 1 to 3
enumerate_paths(dijkstra_shortest_paths(g, 1), 3)
2-element Array{Int64,1}:
1
3
Both directed and undirected weighted graphs are supported.
Please feel free to open up issues if you find any problems or see performance improvement opportunities.
One thing I’d like to see would be better support for visualization. For teaching purposes, I wanted to be be able to have a simple data structure for directed graphs that allowed me to attach labels to edges and nodes, to set colors for edges and nodes (so that I could e.g. color a cycle or a spanning tree in a graph), and control other visualization properties (e.g. to make the edges 50% longer so that the display was easier to read). And I wanted the graphs to display automatically in IJulia (especially for use with interactive widgets) rather than having to call some visualization function manually.
I got a little frustrated, and ended up hacking together my own, but I would have preferred to use something more polished:
Visualization has historically been a bit of a challenge for LightGraphs. I believe you can do this with the current versions of GraphPlot and/or Plots/PlotsRecipes, but I’ve never done it myself. It would require storing the color / edge information in a separate data structure and then passing it in to the visualization function itself (which is what you’d need to do if we stored that in the graph structure in any case).
If you’ve found something that works, I’d suggest posting on GraphPlot or Plots with a PR or some code and we can look at incorporating it.
That said - a graph structure that provides general metadata is definitely feasible (though it wouldn’t be as memory-efficient as the current SimpleGraphs structure). We might look at revamping Networks.jl to handle this, since most of the heavy lifting has been done already.