Erlang Thursday – digraph:del_path/3

今天的Erlang Thursday讲的是 digraph:del_path/3.

我们继续使用上次文章 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 有三个入参，一个有向图，一个源节点，一个目标节点，函数将删除有向图中从源节点到目标节点的每一条路径上的所有边，直到源节点和目标节点之间没有路径为止。

digraph:del_path/3 的返回值总是true。

我们将调用 digraph:del_path/3 传入上面例子的有向图，节点V1作为源节点，节点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]]

根据边的名字来看，从节点1到节点2点边已经被删除，从节点2到节点4点边也被删除。

那么Erlang是怎么得到这样的结果的？

它的结果一开始让我困惑，因为结果并不是我所预期的两种结果之一。我预期的结果是：除了从节点4到节点1的边其他边全部删除，或者仅删除从节点1到节点2的边。

为了解惑，我找到托管在Github上的Erlang源码来阅读 digraph 模块，在代码里我终于明白了其中缘由。

首先 digraph:del_path 调用 digraph:get_path/3 ，并且删除路径上所有的边，然后递归执行直到没有再找到路径。

这就是为什么Erlang只删除那些边对原因。

当我们在原始样例有向图上调用 digraph:get_path/3 ，我们得到的路径是 V1 -> V2 -> V4 。

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

Erlang将路径里的边都删除，然后再递归调用 digraph:del_path/3 ，而这个函数再一次调用 digraph:get_path/3 ，但是因为节点1和节点2之间的边已经被删除，所以没有找到路径，整个处理过程就此结束。

这就是为什么我们看到更多的边被删除，如果我们再次重置样例有向图（退出erlang shell，然后重新打开一个erlang shell，把初始化样例有向图的语句重新执行一遍），然后将节点2和节点4传给 digraph:del_path/3 。

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

这个场景有两个路径：V2 -> V4 和 V2 -> V3 -> V4 ，如果我们删除路径V2 -> V4路径，与这条路径的所有相关的边都被删除但是不会中断路径V2 -> V3 -> V4，所以函数也可以删除这条路径上的所有边。

所以在官方文档没有很清晰说明白函数内部机制的这个场景，我们可以通过开源的Erlang标准库来彻底了解其中奥妙，因为我们可以获取Erlang的源码来研究它底层的实现机制。

原文链接： https://www.proctor-it.com/erlang-thursday-digraph-del_path-3/