Today’s Erlang Thursday is on digraph:del_path/3.

We will continue working with the same graph we started with in the previous post on digraph:get_path/3.

Graph = digraph:new().
% {digraph,20498,24595,28692,true}
V1 = digraph:add_vertex(Graph).
% ['$v'|0]
V2 = digraph:add_vertex(Graph).
% ['$v'|1]
V3 = digraph:add_vertex(Graph).
% ['$v'|2]
V4 = digraph:add_vertex(Graph).
% ['$v'|3]
E1 = digraph:add_edge(Graph, V1, V2).
% ['$e'|0]
E2 = digraph:add_edge(Graph, V2, V3).
% ['$e'|1]
E3 = digraph:add_edge(Graph, V3, V4).
% ['$e'|2]
E4 = digraph:add_edge(Graph, V2, V4).
% ['$e'|3]
E5 = digraph:add_edge(Graph, V4, V1).
% ['$e'|4]

digraph:del_path/3 takes three arguments, a Graph, a source vertex, and a destination vertex, and removes all edges in a each path in the graph from the source vertex to the destination vertex, until no path exist between the source and destination vertices.

The return value of digraph:del_path/3 is always a return value of true.

Looking at the picture of the graph above as reference, we are going to call digraph:del_path/3 for the graph with a source vertex of V1, and a destination vertex of V4.

digraph:del_path(Graph, V1, V4).
% true
digraph:vertices(Graph).
% [['$v'|2],['$v'|1],['$v'|0],['$v'|3]]
digraph:edges(Graph).
% [['$e'|1],['$e'|2],['$e'|4]]

Translating the edge names, we see that the edge from V1 to V2 has been removed, as well as the edge from V2 to V4 has been removed.

So how did Erlang come up with this result?

This puzzled me at first, as it wasn’t one of the two scenarios I was expecting to see, which were either: remove all edges but the edge from V4 to V1, or remove only the edge from V1 to V2.

I then opened the Erlang source code on Github for digraph module to clarify my thinking, and looking at the code it then made sense what was happening.

First digraph:del_path/3 calls digraph:get_path/3, and removes all edges in that path, and then recurses until no path is found.

This is when it clicked as to why Erlang was removing only those edges.

If we call digraph:get_path/3 on a fresh version of the graph, we see that it returns the path of V1 -> V2 -> V4.

digraph:get_path(Graph, V1, V4).
[['$v'|0],['$v'|1],['$v'|3]]

Erlang then removes the edges in that path, and the will call digraph:del_path/3, which calls digraph:get_path/3 again, but as we removed the edge between V1 and V2, no path is found so the process is finished.

This is why we see more edges removed if we reset the Graph again (by exiting the shell and recreating it from scratch by pasting the initialization into the shell), and call digraph:del_path/3 between V2 and V4.

digraph:del_path(Graph, V2, V4).
% true
digraph:edges(Graph).
% [['$e'|0],['$e'|4]]

This case there are the paths V2 -> V4 and V2 -> V3 -> V4, and if we remove the path V2 -> V4, the removal of all the edges associated with that path doesn’t break the path of V2 -> V3 -> V4, so it can remove all edges in that path as well.

So we have a win in the case where the documentation wasn’t quite as clear as it could be, but having the Erlang standard library be open source gets us a win because we can always go in and check out what the code is really doing.

–Proctor