In R, how to find out if two vertices are adjacent from an adjacency matrix

Question

This is the adjacency matrix, how to find out (implement an algorithm) if the vertices 2 and 3 are adjacent using R?

Answer 1

Well, your question is a little better but for your example to be really reproducible you should provide the matrix in a ready format for R, so that whoever answered it would only need to copy and paste. Anyway follows the answer.

Minimal Set

Here I will recreate your matrix on R:

g <- matrix(c(0,1,1,0,0,1,0,1,0,0,1,1,0,1,1,0,0,1,0,0,0,0,1,0,0), nrow = 5)

which results in the following matrix

      [,1] [,2] [,3] [,4] [,5]
[1,]    0    1    1    0    0
[2,]    1    0    1    0    0
[3,]    1    1    0    1    1
[4,]    0    0    1    0    0
[5,]    0    0    1    0    0

Using the igraph

The R has igraph which allows you to do practically everything with graphs, including graph numbers from adjacency matrices:

library(igraph)

## Cria o grafo a partir da matriz de adjacências g
G <- as.undirected(graph.adjacency(g, weighted = T))

## Plot do grafo
plot(G)

which results in the following graph:

And finally you can use the function as_adj_list():

al <- as_adj_list(G, mode="out")

[[1]]
+ 2/5 vertices, from 7a41c18:
[1] 2 3

[[2]]
+ 2/5 vertices, from 7a41c18:
[1] 1 3

[[3]]
+ 4/5 vertices, from 7a41c18:
[1] 1 2 4 5

[[4]]
+ 1/5 vertex, from 7a41c18:
[1] 3

[[5]]
+ 1/5 vertex, from 7a41c18:
[1] 3

Note that each element of the list is related to one of the vertices and within the list are the neighboring vertices. In the case of your question, to find out if vertices 2 and 3 are neighbors, just look for the neighbors of vertex 2, at position 2 of the list:

> al[[2]]
+ 2/5 vertices, from 7a41c18:
[1] 1 3

so points 1 and 3.

Building an adjacency test

Possession of graph and adjacency list it is possible to create a function that tests the adjacency of any two vertices:

sao_adj <- function(x,y,al) {

  ## Testa se x e y são adjacentes
  return(y %in% al[[x]])

}

And let’s test for a case where adjacency occurs and a case where it doesn’t occur:

> sao_adj(x = 1, y = 2, al = al)
[1] TRUE
> sao_adj(x = 5, y = 2, al = al)
[1] FALSE
> sao_adj(x = 1, y = 4, al = al)
[1] FALSE
> sao_adj(x = 3, y = 1, al = al)
[1] TRUE