Search code examples
rgraph-theoryigraph

Create a 3D lattice graph where nodes are connected to all others in their Moore neighbourhood

I am trying to create a 3D lattice igraph object, where nodes are connected to adjacent and diagonal neighbours (Moore neighborhood), in 3D. I can create one where all nodes are connected to their von Neumann neighbours (only adjacent nodes), in 3D using default functions. e.g.

library(rgl)
library(igraph)

g <- make_lattice( c(4, 4, 4))
coords <- layout_with_fr(g, dim = 3)
rglplot(g, layout = coords)

enter image description here

Now I want to make it so that every node is connected to its diagonal neighbours as well as its adjacent neighbours. Any advice would be much appreciated... I am quite stuck.

Something like this (but for all nodes): enter image description here

Solution

  • I think this does it, although it's brute force - there's almost certainly a more elegant way to do it, and I wouldn't try this on a large grid ...

    library(Matrix)
library(igraph)
library(rgl)


n <- 4  ## grid dimension
dd <- do.call(expand.grid, replicate(6, 1:n, simplify = FALSE))
## determine adjacency
afun <- function(p) as.numeric(max(abs(p[1:3]-p[4:6])) <= 1)
adj <- apply(dd, 1, afun)

## set up node IDs, drop self-loops
nodes <- expand.grid(1:n^3, 1:n^3)
self <- nodes[,1] == nodes[,2]
nodes <- nodes[!self,]
adj <- adj[!self]

## construct adjacency matrix
m <- Matrix(0, nrow = n^3, ncol = n^3)
m[as.matrix(nodes)] <- adj
image(m)

## convert to graph, plot
g <- graph_from_adjacency_matrix(m)
coords <- layout_with_fr(g, dim = 3)
rglplot(g, layout = coords)

    enter image description here

    I think the layout algorithm pulls the internal nodes in a little bit more than the corners because they have more connections ...

    (At one point I wrote some nice tricks to construct 2D grid adjacency matrices using sparse Kronecker products - they could probably be extended to 3D ...)