Search code examples
rdijkstraadjacency-matrix

Calculate Adjacency Matrix in R from nxm matrix (representing the map)

I'm new to R and I'm playing around with igraph and routes. I have a Matrix which can be seen as a Map (x and y coordinates). 0 is walkable space and 1 are obstacles. An example matrix would be:

0   0   0   0   0   0   0
0   0   0   1   1   0   0
0   0   0   1   1   0   0
0   0   1   1   1   0   0
0   0   1   1   1   0   0
0   0   0   0   0   0   0

The goal is to calculate the shortest path from the top left point to he bottom right point. Movable ways are left/right/top/down and diagonal, but the obstacle (indicated by the 1 values of the matrix)in the way cannot be passed.

I have found ways to use Dijkstra on Adjacency Matrix in R from similar questions, but I didn't find a way to use it on this example matrix (representing the map/floor). Hence I wanted to know if there is an easy way (like a function) to create the Adjacency Matrix from this input?

The example is inspired by the Dijkstra Wikipedia Page https://en.wikipedia.org/wiki/Dijkstras_algorithm#Algorithm

Especially from the GIF where an obstacle is blocking the direct way. (I would post the GIF but I don't have enough reputation)

Solution

  • I think this is what you're after. I'm using igraph version 1 notation.

    > packageVersion("igraph")
[1] ‘1.0.1’

    The idea is to create a 2D grid and then either remove the blocked nodes or (in this case) remove any edges attached to them.

    library(igraph)
# Your grid in matrix form
grid <- rbind(c(0,   0,   0,   0,   0,   0,   0),
              c(0,   0,   0,   1,   1,   0,   0),
              c(0,   0,   0,   1,   1,   0,   0),
              c(0,   0,   1,   1,   1,   0,   0),
              c(0,   0,   1,   1,   1,   0,   0),
              c(0,   0,   0,   0,   0,   0,   0))

# Make a network on a 2D grid
g <- make_lattice(dimvector=c(nrow(grid), ncol(grid)))

# Add a colour for the nodes we'll be disconnecting
V(g)$color <- c('orange', 'blue')[as.numeric(grid==1)+1]
plot(g)

    enter image description here

    # Disconnect the inpassable nodes
gGap <- g - E(g)[inc(V(g)[grid==1])]
plot(gGap)

    enter image description here

    # Either output the adjacency matrix and do your own thing
as_adjacency_matrix(gGap,sparse = FALSE)

# Or find distances in igraph
distances(gGap, v=V(gGap)[1], to=V(gGap), algorithm="dijkstra")