LFE Friday - digraph:get_cycle/2

This week's LFE Friday was translated with permission from the Erlang Thursday series by Steven Proctor. This week's translator: Robert Virding.

Today's LFE Friday is on digraph:get_cycle/2.

We will continue working with the graph from the previous post on digraph:get_path/3.

> (set graph (digraph:new))
#(digraph 8207 12304 16401 true)
> (set v-1 (digraph:add_vertex graph 'v-1))
v-1
> (set v-2 (digraph:add_vertex graph 'v-2))
v-2
> (set v-3 (digraph:add_vertex graph 'v-3))
v-3
> (set v-4 (digraph:add_vertex graph 'v-4))
v-4
> (set e-1 (digraph:add_edge graph v-1 v-2))
($e . 0)
> (set e-2 (digraph:add_edge graph v-2 v-3))
($e . 1)
> (set e-3 (digraph:add_edge graph v-3 v-4))
($e . 2)
> (set e-4 (digraph:add_edge graph v-2 v-4))
($e . 3)
> (set e-5 (digraph:add_edge graph v-4 v-1))
($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 v-1)
(v-1 v-2 v-4 v-1)
> (digraph:get_cycle graph v-2)
(v-2 v-4 v-1 v-2)

Next, we add a new vertex v-5, and a new edge originating from v-4 and ending on v-5

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

> (set v-5 (digraph:add_vertex graph 'v-5))
v-5
> (digraph:add_edge graph v-4 v-5)
($e . 5)
> (digraph:get_cycle graph v-5)            
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 v-1)      
(v-1 v-2 v-4 v-1)
> (digraph:get_short_cycle graph v-5)
false

- Proctor, Robert