libgraph

Documentation

About

This library provides an alternative directed graph implementation (i.e. replaces :digraph), a priority queue implementation (designed for use with graphs, as it prioritizes low integer values over high), and eventually an undirected graph implementation.

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.

NOTE: While this library is primarily focused on the Graph data structure it defines, it also contains an implementation of a priority queue (you can find it under the PriorityQueue module), designed for use with graphs specifically, as it considers lower integer values higher priority, which is perfect for the kinds of graph algorithms you need a priority queue for.

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.5"}]
end

Roadmap

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

• Support for undirected graphs

License

MIT (See the LICENSE file)