Engee documentation
Notebook

Finding the shortest path on a graph

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

Working with graphs

Graphs are often used as an element of models in logistics, transportation, information, or social media tasks, and other related systems. They are abstract mathematical objects consisting of vertices (vertex, vertices) and edges (edges). Usually, each vertex has its own unique number, and the edges are indicated by two numbers – the numbers of the vertices they connect.

Some information may be associated with nodes and edges (for example, coordinates or bandwidth). In the library Graphs.jl it is assumed that additional information is stored in an external table or dictionary (Dict). Records can be linked to vertices (via their numbers) or edges (via a tuple of numbers identifying the edge). Sparse matrices can be used to save money (SparseArrays.jl).

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

Package GraphsRecipes.jl is responsible for drawing graphs.

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

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

Now there are three vertices in our graph, connect them with edges.

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

And we will output this graph:

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

Note that the node names are names taken from an "external" array 1:nv(g), where are the node numbers stored from 1 before nv (number of vertices, the number of vertices).

Let's create a map on which we will look for a way

As a field for finding the shortest path, we will take a random matrix and set a goal to walk along it along the main diagonal. The connectivity of this "map" and the ability to reach point B from point A, alas, is not provided by anything other than 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, that is, 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 the matrix where the 2D coordinates of all points on the map will be stored.

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

Let's create a graph that translates the vertex number of the graph 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 we invert this dictionary and get the opportunity to translate a coordinate into a point number on 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

Add the coordinates of the points into arrays xx and yy – we will transfer them to the graph rendering procedure.

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

Filling the graph

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

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

Let's go through all the points and connect them with neighboring 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 any edges have been added to our graph, and how many of them there are:

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

Judging by the output, 840 edges were added to 634 points. Let's output a 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 didn't have to "lay out" the graph, because we already know the coordinates of each node. The rest of the rendering parameters can be studied [here] (https://juliagraphs.org/GraphPlot.jl /).

Finding the shortest path

We use the [A-star algorithm](https://juliagraphs.org/Graphs.jl/dev/algorithms/shortestpaths /), which searches for the shortest path using heuristics. At the output, we get 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 need to be visited 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–cycles, trees, shortest or longest paths, and connected regions. The opportunity to work with them from a dynamic systems modeling environment gives engineers very interesting opportunities.