Digraph edges notation

Questions / Help
1

When you use the :digraph module and want to get a list of all edges, one would expect to see a list of vertex pairs, ideally with the “emanate from” / “incident to” order consistent. So something like [{:a, :b}, {:b, :c}, {:c, :b}] for a graph with vertices [:a, :b, :c] where :a has an edge incident to :b and :b and :c have a bidirectional edge. Instead you might see something inscrutable like [[:"$e" | 0], [:"$e" | 1], [:"$e" | 2]]. How are you supposed to interpret that list?

2

Definitely an odd design choice - you could get something closer to what you’re looking for by mapping :digraph.edge over the output of :digraph.edges, but that’s a lot of round-trips to ETS to get what could have been one call to :ets.select :thinking:

2 Likes
3

Alternatively, you could specify you our own edge names when creating the edges. As long as there is only a single edge in each direction between each pair of vertices, the following should work:

:digraph.add_edge(g, {from, to}, from, to, [])
1 Like
4

So that’s brilliant. I’m curious why that’s not the default behavior of add_edge/3 though? Implicitly naming an edge with {from, to} has to be more intuitive than whatever [:"$e" | N] is meant to convey.

I also think it’s difficult to understand that this is possible from the docs for add_edge/5 because the edge() type is not documented. It’s also confusing to have edge “names” differ from edge “labels” and not document the “names” anywhere.

1 Like
5

The default edge names aren’t meant to convey anything: not giving them a name implies that you don’t care what they’re called.

The funny-looking names were most likely chosen because they’re more compact in memory and are unlikely to clash with user-named edges.

1 Like
6

Submitted pull request to hopefully clarify docs a bit.

1 Like
7

Using the {from, to} naming scheme will not work in general, because the :digraph module supports having any number of distinct edges between each pair of vertices.

8

What is the utility of that feature? Is it to allow using labels to sort of classify connections in different schemas or something? Something like a graph of cars that includes vertices

v1 = {:toyota, :yellow}
v2 = {:toyota, :red}
v3 = {:ford, :yellow}
v4 = {:also_ford, :yellow}

Could have edges {v1, v2} label: :toyota, {v1, v3} label: :yellow, {v3, v4} label: :yellow, {v3, v4} label: :ford?

9

I don’t know the original motivation for that feature, but one algorithm that needs it is Karger’s algorithm.

1 Like