Geek asks and answers

Changing the attribute of nodes at the first search in width in R

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

This is related to this question .

I do the first width search as follows:

# 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 neighbors, then the neighbors of the second root node neighbors, etc.

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, for starters, the neighbors of the first root node look:

                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 look:

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

node :

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

node :

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

, :

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

node, 0 1, , , , node .

, , , ? , 6 ( ).

: - (.. ).

, . , .

. !

+3
1

. -, .

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

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

. ( , ). , .

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)
}

, , , . , .

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

. , . , , , , , , . , . , . , .

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
}

, node. , . - , , .

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

More articles:


All Articles