Erlang Thursday – digraph:get_cycle/2

发表于   |   分类于 ，

今天的Erlang Thursday讲的是 digraph:get_cycle/2.

我们将继续在上一篇文章 digraph:get_path/3 用的有向图上讲解。

有向图

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_cycle/2 两个入参分别是一个有向图G，一个节点V，该函数尝试在有向图中找到一条路径使得节点V在其中并且形成一个环。

1
2
3
4
digraph:get_cycle(Graph, V1).
% [['$v'|0],['$v'|1],['$v'|3],['$v'|0]]
digraph:get_cycle(Graph, V2).
% [['$v'|1],['$v'|3],['$v'|0],['$v'|1]]

接着我们增加一个新节点V5，并且新增一条从节点V4发出到节点V5的边。

然后我们调用 digraph:get_cycle/2 第二个入参是V5，我们会得到一个false，因为在图中没有一个环使得V5在其中。

1
2
3
4
5
6
V5 = digraph:add_vertex(Graph).
% ['$v'|4]
E6 = digraph:add_edge(Graph, V4, V5).
% ['$e'|5]
digraph:get_cycle(Graph, V5).
% false

digraph模块还有一个函数 digraph:get_short_cycle/2 。

digraph:get_short_cycle/2 尝试为节点V在图G中找到一条最短的环。

官方文档解释 digraph:get_short_cycle/2 的原话是：

尝试在有向图G上找到尽可能短的通过节点V的简单环。

因此这取决于你如何理解这句话，可能不能保证返回最短的环，而只是返回更短的一个环，这可能取决于有向图的整体大小和复杂度。

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

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