Changing attribute of nodes during breadth first search in R

Question

I have created a random (Erdos-Renyi) graph that has 100 nodes. I have set an attribute value for all 100 nodes as 0. I find the node with the maximum degree (the most neighbors), and change its attribute value from 0 to 1. Then, using the node as the root node, and another node as a second root node, I do a breadth first search (BFS) on the network.

This is related to this question.

I do the breadth first search like this:

# BFS on the network
bfs <- graph.bfs(graph, root = c(root_node, root_node2), unreachable = FALSE,
    order = TRUE, dist = TRUE)

I want to look at the neighbors of the first root node, then the neighbors of the second root node, then the neighbors of the first root node's neighbors, then the neighbors of the second root node's neighbors, and so on.

So something like this:

                O                        # Note: O* is the first root node
                |                        # and O! is the second root node
                |
O----O----O!----O----O*----O----O----O
          |          |
          |          |
          O          O

So, to start with, the neighbors of the first root node are looked at:

                O                        # Note: double connections are
                |                        # the paths taken to the neighbors
                |
O----O----O!----O====O*====O----O----O
          |          ||
          |          ||
          O          O

Then the neighbors of the second root node are looked at:

                O
                |
                |
O----O====O!====O----O*----O----O----O
          ||         |
          ||         |
          O          O

Then, the neighbors of the first root node's neighbors:

                O
                ||
                ||
O----O----O!----O----O*----O====O----O
          |          |
          |          |
          O          O

Then the neighbors of the second root node's neighbors:

                O
                |
                |
O====O----O!----O----O*----O----O----O
          |          |
          |          |
          O          O

And so on until all of the nodes have been looked at:

                O
                |
                |
O----O----O!----O----O*----O----O====O
          |          |
          |          |
          O          O

As each node is looked at, I want to change its attribute value from 0 to 1, so that if another path comes to it, it that knows this node has already been looked at.

Also, is there a way to count how many iterations if takes to look through all of the nodes? For example, here it is 6 (including the original).

Note: the two root nodes are connected in some way (i.e. there is a path between them).

Sorry about the images, but that's the basic idea. Hope this makes sense.

Any help would be much appreciated. Thanks!

Answer 1

Here is how to do it. First, here is a randomly generated graph.

numnodes <- 50
the.graph <- grg.game(numnodes, 0.3)

V(the.graph)$visited <- 0
graph.degree <- degree(the.graph)

Now, we take the maximum vertex and a random vertex. (You didn't specify how you chose the second one). We randomly repick the vertex until it is connected to and is not the maximum degree vertex.

maxvertex <- sample(which(graph.degree == max(graph.degree)),1)
randvertex <- as.integer(sample(V(the.graph),1))
while((randvertex == maxvertex) ||
      (shortest.paths(the.graph,maxvertex,randvertex) == Inf)) {
  randvertex <- sample(V(the.graph),1)
}

When traversing graphs like this, I like to keep track of where I am. Here is the starting position and a line to mark these initial nodes as visited.

curpos <- c(maxvertex, randvertex)
for(num in curpos) V(the.graph)[num]$visited <- 1

Now we actually do the search and mark nodes as visited. The loop will terminate if all of the nodes are marked as visited or if there are no more connected nodes to explore. If the code is bugged, we know there shouldn't be more iterations than steps for the search, so we know if it goes over the graph is not connected and we needn't continue. For each iteration, we go through the vector containing our currently occupied nodes. If any of its neighbors haven't been visited, we mark them as visited and add them to the vector for next time. Once we have visited all of the nodes for this iteration, we start the next cycle.

maxloops = length(V(the.graph))
curloop = 0
while((curloop < maxloops) && (length(curpos)>0) &&
      (sum(V(the.graph)$visited) < numnodes)) {
  nextpos <- c()
  while(length(curpos)>0) {
    curnode <- curpos[1]
    curpos <- curpos[-1]

    adjnodes <- which(the.graph[curnode] == 1)
    for(adjnode in adjnodes) {
      if(!V(the.graph)[adjnode]$visited) {
        nextpos <- c(nextpos,adjnode)
        V(the.graph)[adjnode]$visited <- 1
      }
    }
  }
  curpos <- nextpos
  curloop <- curloop + 1
}

Now we have visited all nodes connected to the maximal degree node. We now print the number of iterations it took to traverse the graph. If any nodes are not visited, this will additionally print a message stating that the graph is not connected.

print(curloop)
if(sum(V(the.graph)$visited) < numnodes) print("Not a connected graph.")