libgraph

About

This library provides an alternative directed graph implementation (i.e. replaces :digraph).

I created this library because one of my current projects has a need for doing processing on large numbers of graphs concurrently. As :digraph requires a minimum of 3 ETS tables per graph, and up to 6 depending on what queries you are running on it, this means you can very easily hit the max ETS tables system limit and crash a node. So, the need for a non-ETS backed graph structure became evident.

I'm not attempting to make an API that matches :digraph, though they will be similar for obvious reasons. I'm likely also only going to implement the operations that I feel are common or that I need myself, but feel free to open an issue if there is something missing that you would like to have, and I'll do my best to get it implemented if I feel it belongs here.

If you are curious, there is a test suite, including QuickCheck-style tests, and some benchmarks which compare some common scenarios with both :digraph and libgraph. So far, I've been able to get libgraph to outperform :digraph, but the benchmarks are by no means comprehensive, so I would recommend doing some of your own which reflect your use case. That said, please let me know if you find any pathological performance issues with this library, as I would like to ensure that as much as possible, libgraph either matches the performance of :digraph, or exceeds it.

Installation

If available in Hex, the package can be installed by adding libgraph to your list of dependencies in mix.exs:

def deps do
  [{:libgraph, "~> 0.1"}]
end

Roadmap

The following are items I plan to implement soon - they are not in any particular order.

Graph reducer, allowing you to manipulate the graph as you walk it
Graph iterators, allow you to walk a graph via BFS/DFS, applying a function as you go
Implement weighted edges, and a corresponding shortest path implementation

License

MIT (See the LICENSE file)