Today’s Erlang Thursday is on digraph:get_path/3.

digraph:get_path/3 takes a graph, a starting vertex, and an ending vertex and will attempt to find some path through the graph of length greater than zero, where all vertices in the path are distinct, except allowing for the first and last vertices to be the same.

If a path is found, it returns a list of the vertices visited (in order) to complete the path, if no path is found, false is returned.

First we will setup a new graph that we can traverse.

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]

This will give us a graph that looks like the following:

Now we can get to playing with digraph:get_path/3 and see what the paths are from any sets of nodes.

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

Note that these just happen to be the shortest paths, but this is not guaranteed to return the shortest path, but just the first path found.

And if we add a new vertex, and don’t connect it to any other node in the graph, and we call digraph:get_path/3, we can see it returns false.

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

–Proctor