Engee documentation
Notebook

Finding the shortest path in a graph

In this example, we will use the functions of the Graphs.jl library to create a graph and find the shortest path between two points on it.

Working with graphs

Graphs are often used as an element of models in logistics, transport, information or social networks and other related systems. They are abstract mathematical objects consisting of vertices (vertex, vertices) and edges (edges). Usually, each vertex has a unique number, and edges are denoted by two numbers - the numbers of vertices they connect.

Some information (such as coordinates or bandwidth) can be attached to nodes and edges. The Graphs.jl library assumes that additional information is stored in an external table or dictionary (Dict). Entries can be mapped to vertices (via their numbers) or edges (via a tuple of numbers identifying the edge). Sparse matrices (SparseArrays.jl) can be used for economy.

In [ ]: 
Pkg.add(["GraphRecipes", "Graphs"])
In [ ]: 
# Если библиотека у вас установлена, закомментируйте следующую строчку:
import Pkg; Pkg.add( ["Graphs", "GraphRecipes"] )
In [ ]: 
using Graphs, GraphRecipes

The package GraphsRecipes.jl is responsible for drawing graphs.

Let's create a simple directed graph with three nodes and several edges.

In [ ]: 
g = DiGraph()
add_vertices!( g, 3 );

Now there are three nodes in our graph, let's connect them by edges.

In [ ]: 
add_edge!( g, 1, 2 );
add_edge!( g, 1, 3 );
add_edge!( g, 2, 3 );

And derive this graph:

In [ ]: 
gr() # Упрощенная отрисовка
graphplot( g, names=1:nv(g) )
Out[0]:

Note that the node names names are taken from the "external" array 1:nv(g), which stores the node numbers from 1 to nv (number of vertices, the number of vertices).

Create a map on which to search for a path

As a field for finding the shortest path we will take a random matrix and set a goal to traverse it along the main diagonal. The connectivity of this "map" and the possibility to reach point B from point A, alas, is not ensured by anything except choosing the "correct" starting value of the pseudorandom number generator Random.seed!().

In [ ]: 
using Random;
Random.seed!( 4 )

карта = rand( 30, 30 ) .> 0.3;
heatmap( карта )

# Точка старта и финиша
точка_А = CartesianIndex(1,1)
точка_Б = CartesianIndex(30,30)

# Добавим на график токи старта и финиша
scatter!( [точка_А[1]], [точка_А[2]], c=:red )
scatter!( [точка_Б[1]], [точка_Б[2]], c=:green, leg=false )
Out[0]:

Our graph will be undirected, i.e. along each edge it will be possible to go both there and back.

In [ ]: 
g = Graph();
индексы_доступных_точек = LinearIndices( карта )[ карта .== 1 ]
println( "Количество площадок, куда можно наступать: ", count(индексы_доступных_точек .> 0 ))

Количество площадок, куда можно наступать: 634

Auxiliary objects (coordinate translation)

Let's save a matrix where 2D coordinates of all map points will be stored.

In [ ]: 
координаты_всех_точек = CartesianIndices( size(карта) );

Create a graph that translates the graph vertex number into a coordinate:

In [ ]: 
координаты_точек_графа = Dict(zip( 1:length(индексы_доступных_точек), координаты_всех_точек[индексы_доступных_точек] ))
first( sort(collect(координаты_точек_графа)), 5 )
Out[0]:
5-element Vector{Pair{Int64, CartesianIndex{2}}}:
 1 => CartesianIndex(1, 1)
 2 => CartesianIndex(2, 1)
 3 => CartesianIndex(3, 1)
 4 => CartesianIndex(4, 1)
 5 => CartesianIndex(5, 1)

Now - invert this dictionary and get the ability to translate a coordinate into a point number in the graph.

In [ ]: 
индексы_точек_по_координатам = Dict(value => key for (key, value) in координаты_точек_графа)
first( sort(collect(индексы_точек_по_координатам)), 5 )
Out[0]:
5-element Vector{Pair{CartesianIndex{2}, Int64}}:
 CartesianIndex(1, 1) => 1
 CartesianIndex(2, 1) => 2
 CartesianIndex(3, 1) => 3
 CartesianIndex(4, 1) => 4
 CartesianIndex(5, 1) => 5

Let's add the coordinates of points to the arrays xx and yy - we will pass them to the graph drawing procedure.

In [ ]: 
xy = Tuple.(first.(sort(collect(индексы_точек_по_координатам))));
xx = first.(xy);
yy = last.(xy);

Filling the graph

Since we will be using a standard function to find the shortest path, rather than creating it ourselves from scratch, we need to create the graph on which this search will take place.

In [ ]: 
g = Graph()
add_vertices!( g, length(координаты_всех_точек[ индексы_доступных_точек ][:]) )
Out[0]:
634

Let's go through all points and connect them to neighbouring points, if there is a passage between them.

In [ ]: 
MAX_X,MAX_Y = size( карта )

for вершина in 1:nv(g)
    x,y = Tuple(координаты_точек_графа[вершина])
    точка_справа = CartesianIndex( x + 1, y )
    точка_снизу = CartesianIndex( x, y + 1 )
    
    # Соединим текущую точку с точкой справа, если есть связанность согласно карте пройденных точек 
    if x < MAX_X && карта[точка_справа] == 1 add_edge!(g, вершина, индексы_точек_по_координатам[точка_справа]); end;
    # То же самое для точки снизу
    if y < MAX_Y && карта[точка_снизу] == 1 add_edge!(g, вершина, индексы_точек_по_координатам[точка_снизу]); end;
end

Let's see if and how many edges have been added to our graph:

In [ ]: 
g
Out[0]:
{634, 871} undirected simple Int64 graph

Judging from the output, 840 edges have been added to the 634 points. Let's display the graph:

In [ ]: 
heatmap( карта', title="Карта", titlefont=font(9), leg=:false )
graphplot!( g, x = xx, y = yy, nodeshape=:circle, nodecolor=:red, nodestrokecolor=:red, nodesize=1.5, edgecolor=:red, curves=true, size=(500,500) )
Out[0]:

We did not have to "unfold" the graph, since we already know the coordinates of each node. The rest of the drawing parameters can be studied here.

Finding the shortest path

We use A-star algorithm, which searches for the shortest path using heuristics. The output is a set of edges.

In [ ]: 
# Нахождение кратчайшего пути
path = a_star( g, индексы_точек_по_координатам[точка_А], индексы_точек_по_координатам[точка_Б] );
first( path, 5 )
Out[0]:
5-element Vector{Graphs.SimpleGraphs.SimpleEdge{Int64}}:
 Edge 1 => 2
 Edge 2 => 27
 Edge 27 => 51
 Edge 51 => 52
 Edge 52 => 79

Let's make an array of graph points that we need to visit to go from point A to point B.

In [ ]: 
points = Tuple.( vcat([точка_А], [ координаты_точек_графа[dst(v)] for v in path ]) );
first( points, 5 )
Out[0]:
5-element Vector{Tuple{Int64, Int64}}:
 (1, 1)
 (2, 1)
 (2, 2)
 (2, 3)
 (3, 3)
In [ ]: 
# Вывод карты (со смещенными значениями для нужной яркости графика)
heatmap( карта' .* 0.3 .+ 0.7, title="Кратчайший путь", leg=false, c=:grays, aspect_ratio=:equal )

# Вывод графа допустимых перемещений по карте
#graphplot!( g, x = xx, y = yy, curves=true, nodeshape=:circle, size=(400,400) )

# Вывод кратчайшего пути
plot!( first.(points), last.(points), lw=3, linez=range(0,1,length(points)), c=:viridis, yflip=true )
Out[0]:

Conclusion

Graphs are very powerful mathematical objects that allow you to find structure in disparate data - loops, trees, shortest or longest paths and connected regions. Being able to work with them from a dynamic systems modelling environment gives engineers very interesting possibilities.