Today’s Erlang Thursday is on digraph:get_cycle/2.

We will continue working with the graph from 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:get_cycle/2 takes a graph G, and an vertex V, and tries to find a path that creates a cycle between the vertex V in graph G.

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]]

Next, we add a new vertex V5, and a new edge originating from V4 and ending on V5

We then call digraph:get_cycle/2 on V5, and we get back a false as no cyle exists in the graph with vertex V5 in it.

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

The digraph module also contains the function digraph:get_short_cycle/2.

digraph:get_short_cycle/2 attempts to find the shortest cycle in the graph G for vertex V.

The documentation for digraph:get_short_cycle/2 exact phrasing is:

Tries to find an as short as possible simple cycle through the vertex V of the digraph G.

So depending on how you read that, the shortest cycle might not be guaranteed to be returned, but simply a shorter cycle, which may depend on the overall size and complexity of the graph.

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

–Proctor