Make a simple 10-vertex random (Barabasi-Albert model) graph. Set the random number seed so that the graph is always the same, for purposes of reproducibility (we want to know that the "hub" vertex will be vertex 2, and we will test your BFS function starting at that "hub" vertex).
In [4]:
suppressPackageStartupMessages(library(igraph))
set.seed(1337)
g <- barabasi.game(10, directed=FALSE)
plot(g)
Create a function bfs_single_vertex that accepts two arguments, p_graph and p_vertex, and returns the vector of distances from vertex p_vertex to all the other vertices in the graph.
In [5]:
bfs_single_vertex <- function(p_graph, p_vertex) {
vertices <- V(p_graph)
stopifnot(p_vertex %in% vertices)
N <- length(vertices)
distances <- rep(NA, N)
distances[p_vertex] <- 0
queue <- c(p_vertex, rep(NA, N-1))
read_ptr <- 1
write_ptr <- 2
while(write_ptr > read_ptr) {
cur_vertex_num <- queue[read_ptr]
read_ptr <- read_ptr + 1
cur_vertex_distance <- distances[cur_vertex_num]
stopifnot(! is.na(cur_vertex_distance))
vertex_neighbors <- neighbors(p_graph, cur_vertex_num)
for (vertex_neighbor in vertex_neighbors) {
if (is.na(distances[vertex_neighbor])) {
distances[vertex_neighbor] <- cur_vertex_distance + 1
queue[write_ptr] <- vertex_neighbor
write_ptr <- write_ptr + 1
}
}
}
distances
}
Test out your function, starting at vertex 2
In [6]:
bfs_single_vertex(g, 2)
In [9]:
shortest.paths(g, v=2)
In [ ]: