Erlang Thursday – digraph:get_path/3

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

digraph:get_path/3 接收三个入参,一个有向图,一个开始节点和一个结束节点,该函数将尝试在图中找到一些大于0的路径,在路径里除了允许第一个节点和最后一个节点相同,其他所有的节点都不能相同。

如果找到一个路径,函数将返回一个在路径中按顺序被访问到的节点所组成的列表,如果找不到路径,函数将返回false。

首先我们创建一个新的有向图以便我们可以遍历它。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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:get_path/3 函数来看看图中任何两个节点间有什么路径。

1
2
3
4
5
6
7
8
9
10
11
12
digraph:get_path(Graph, V2, V3).
% [['$v'|1],['$v'|2]]
digraph:get_path(Graph, V2, V4).
% [['$v'|1],['$v'|3]]
digraph:get_path(Graph, V2, V1).
% [['$v'|1],['$v'|3],['$v'|0]]
digraph:get_path(Graph, V3, V1).
% [['$v'|2],['$v'|3],['$v'|0]]
digraph:get_path(Graph, V1, V4).
% [['$v'|0],['$v'|1],['$v'|3]]
digraph:get_path(Graph, V1, V1).
% [['$v'|0],['$v'|1],['$v'|3],['$v'|0]]

注意:上述结果中只是碰巧有最短的路径,但是该函数并不保证最短路径是第一个返回的路径。

如果我们新增加一个节点,但是没有将它和其他节点连接起来,然后我们就调用 digraph:get_path/3 来获取与它相关的路径,那么函数会返回false。

1
2
3
4
V5 = digraph:add_vertex(Graph).
% ['$v'|4]
digraph:get_path(Graph, V1, V5).
% false

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