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

Pingback: Erlang Thursday – digraph:in_neighbors/2Proctor It | Proctor It

Pingback: Erlang Thursday – digraph:get_cycle/2Proctor It | Proctor It

Pingback: Erlang Thursday – digraph:del_path/3Proctor It | Proctor It