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