API reference

GridGraphs

A package for graphs defined by a grid of vertices.

GridDirection

Enum type for the 9 possible move directions on a 2-dimensional grid with square cells: northwest, west, southwest, north, center, south, northeast, east, southeast.

Various subsets of these directions are defined as constants, but not exported. They are based on an analogy with the game of chess:

• QUEEN_DIRECTIONS_PLUS_CENTER
• ROOK_DIRECTIONS_PLUS_CENTER
• QUEEN_DIRECTIONS
• ROOK_DIRECTIONS
• QUEEN_ACYCLIC_DIRECTIONS
• ROOK_ACYCLIC_DIRECTIONS

Acyclic direction sets give rise to an acyclic graph because they are contained in {south, east, southeast}.

GridGraph{
    T<:Integer,
    R<:Real,
    W<:AbstractMatrix{R},
    A<:AbstractMatrix{Bool}
}

Graph defined by a grid of vertices with index type T.

Fields

• weights::W: vertex weights matrix, which serve to define edge weights.
• active::A: vertex activity matrix. All the vertices on the grid exist, but only active vertices can have edges (inactive vertices are isolated).
• directions::Vector{GridDirection}: the set of legal directions which are used to define edges.
• diag_through_corner::Bool: defines how the weight of a diagonal edge is computed.

See also

• edge_weight(g, s, d)

GridGraph{T}(weights[; active, directions, diag_through_corner])

User-friendly constructor. By default, all vertices are active, all directions are allowed, and edge weights are always computed based on the arrival vertex alone.

ShortestPathTree{T<:Integer,R<:Real}

Storage for the result of a single-source shortest paths query with source s.

Fields

• parents::Vector{T}: the parent of each vertex v in a shortest s -> v path.
• dists::Vector{R}: the distance of each vertex v from s.

Base.+((i, j), dir)

Add a GridDirection to a couple of grid coordinates and return the new coordinates.

Base.-(dir)

Compute the opposite GridDirection (e.g. northwest / southeast).

Base.-((i, j), dir)

Subtract a GridDirection from a couple of grid coordinates and return the new coordinates.

Base.show(io, g)

Display a GridGraph using braille patterns when not all vertices are active.

Graphs.weights(g)

Efficiently compute a sparse matrix of edge weights based on the vertex weights.

active_vertex(g, v)

Check if vertex v is active.

coord_to_index(g, i, j)

Convert a grid coordinate tuple (i,j) into the index v of the associated vertex.

diag_through_corner(g)

Check if diagonal edge weights are computed using the corner vertices.

edge_weight(g, s, d)

Compute the weight of the edge from s to d.

• If diag_through_corner(g) is false, return the vertex weight of the destination d
• If diag_through_corner(g) is true, use Pythagoras' theorem on the cheapest of the two corner vertices.

See also

• edge_weight_direct(g, s, d)
• edge_weight_corner(g, s, d)

edge_weight_corner(g, s, d)

edge_weight_direct(g, s, d)

get_direction(Δi, Δj)

Translate a couple of grid steps in {±1,0} into a GridDirection.

get_path(spt::ShortestPathTree, s, d)

Reconstruct the shortest s -> d path from a ShortestPathTree with source s.

get_tuple(::Type{T}, dir)

Translate a GridDirection into a couple of grid steps in {±1,0} with integer type T.

grid_bellman_ford(g, s, d)

Apply grid_bellman_ford(g, s) and retrieve the shortest path from s to d.

grid_bellman_ford(g, s)

Apply the Bellman-Ford algorithm on an GridGraph g, and return a ShortestPathTree with source s.

Compatible with ForwardDiff.

grid_dijkstra(g, s, d)

Apply grid_dijkstra(g, s) and retrieve the shortest path from s to d.

grid_dijkstra(g, s)

Apply Dijkstra's algorithm on an GridGraph g, and return a ShortestPathTree with source s.

Uses a DataStructures.BinaryHeap internally instead of a DataStructures.PriorityQueue. Compatible with ForwardDiff.

grid_topological_sort(g, s, d)

Apply grid_topological_sort(g, s) and retrieve the shortest path from s to d.

grid_topological_sort(g, s)

Apply the topological sort on an acyclic GridGraph g, and return a ShortestPathTree with source s.

Assumes vertex indices correspond to topological ranks. Compatible with ForwardDiff.

has_direction(g, dir)

Check if direction dir is a valid edge direction.

has_negative_weights(g)

Check if any of the vertex weights are negative.

By default this check is not included in Dijkstra's algorithm to save time.

height(g)

Compute the height of the grid (number of rows).

index_to_coord(g, v)

Convert a vertex index v into the tuple (i,j) of associated grid coordinates.

is_acyclic(directions)

Check if a set of directions is contained in {south, east, southeast}.

path_to_matrix(g::GridGraph, path::Vector{<:Integer})

Store the shortest s -> d path in g as an integer matrix of size height(g) * width(g), where entry (i,j) counts the number of visits to the associated vertex.

vertex_weight(g, v)

Retrieve the vertex weight associated with index v.

width(g)

Compute the width of the grid (number of columns).