What is inside Erlang's digraph?

Question

Disclaimer: The author is a newbie in Erlang.

I would like to implement some kind of shortest-path algorithm in Erlang.

There is a standard implementation of graph data structure in Erlang: http://www.erlang.org/doc/man/digraph.html

However, I have not found any information on the actual data structure it uses.

Mostly I would like to know:

• what is the worst case performance of getting all 'neighbours' for a vertex action?
• what is the worst case performance of fetching a vertex from the graph?

Answer 1

A digraph uses 3 ets tables (vertices, edges and neighbour vertices).

So both of that operations are O(1).

Take a look at OTP code, it's clean and in most cases idiomatic Erlang. stdlib's gen.erl + gen_server.erl, proc_lib.erl and sys.erl are must read :)