funcion - Cambio de atributo de los nodos durante la primera búsqueda de amplitud en R

funcion cbind en r

Question

Creé un gráfico aleatorio (Erdos-Renyi) que tiene 100 nodos. Establecí un valor de atributo para los 100 nodos como 0. Encontré el nodo con el grado máximo (la mayoría de los vecinos), y cambié su valor de atributo de 0 a 1. Luego, usando el nodo como nodo raíz, y otro nodo como segundo nodo raíz, hago una primera búsqueda de amplitud (BFS) en la red.

Esto está relacionado con esta pregunta .

Hago la primera búsqueda de amplitud así:

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

Quiero ver los vecinos del primer nodo raíz, luego los vecinos del segundo nodo raíz, luego los vecinos de los vecinos del primer nodo raíz, luego los vecinos de los vecinos del segundo nodo raíz, y así sucesivamente.

Entonces algo como esto:

                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

Entonces, para empezar, se examinan los vecinos del primer nodo raíz:

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

Luego se observan los vecinos del segundo nodo raíz:

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

Luego, los vecinos de los vecinos del primer nodo raíz:

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

Luego, los vecinos de los vecinos del segundo nodo raíz:

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

Y así sucesivamente hasta que todos los nodos hayan sido examinados:

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

A medida que se mira cada nodo, quiero cambiar su valor de atributo de 0 a 1, de modo que si aparece otra ruta, ya se ha observado el nodo que conoce este nodo.

Además, ¿hay alguna manera de contar cuántas repeticiones se necesitan para mirar a través de todos los nodos? Por ejemplo, aquí es 6 (incluido el original).

Nota: los dos nodos raíz están conectados de alguna manera (es decir, hay una ruta entre ellos).

Perdón por las imágenes, pero esa es la idea básica. Espero que esto tenga sentido.

Cualquier ayuda sería muy apreciada. ¡Gracias!

Answer 1

Aquí es cómo hacerlo. Primero, aquí hay un gráfico generado aleatoriamente.

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

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

Ahora, tomamos el vértice máximo y un vértice aleatorio. (No especificó cómo eligió el segundo). Replanteamos al azar el vértice hasta que esté conectado y no sea el grado máximo del vértice.

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

Al recorrer gráficos como este, me gusta hacer un seguimiento de dónde estoy. Aquí está la posición inicial y una línea para marcar estos nodos iniciales como visitados.

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

Ahora realizamos la búsqueda y marcamos nodos como visitados. El ciclo terminará si todos los nodos están marcados como visitados o si no hay más nodos conectados para explorar. Si el código tiene errores, sabemos que no debe haber más iteraciones que pasos para la búsqueda, por lo que sabemos si el gráfico no está conectado y no necesitamos continuar. Para cada iteración, pasamos por el vector que contiene nuestros nodos ocupados actualmente. Si alguno de sus vecinos no ha sido visitado, los marcamos como visitados y los agregamos al vector para la próxima vez. Una vez que hemos visitado todos los nodos para esta iteración, comenzamos el siguiente ciclo.

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
}

Ahora hemos visitado todos los nodos conectados al nodo de grado máximo. Ahora imprimimos el número de iteraciones que tomó para recorrer el gráfico. Si no se visitan los nodos, esto adicionalmente imprimirá un mensaje que indica que el gráfico no está conectado.

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