文档结构  
翻译进度:已翻译     翻译赏金:0 元 (?)    ¥ 我要打赏

今天的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]

 

第 1 段(可获 0.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]]

 

第 2 段(可获 1.01 积分)

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

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

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

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

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

第 3 段(可获 1.54 积分)

这就是为什么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 。

第 4 段(可获 1.28 积分)
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的源码来研究它底层的实现机制。

第 5 段(可获 1.1 积分)

文章评论