在R中的宽度优先搜索期间更改节点的属性 [英] Changing attribute of nodes during breadth first search in R
问题描述
我创建了一个有100个节点的随机（Erdos-Renyi）图。我已经将所有100个节点的属性值设置为0.我找到最大度数的节点（最邻近），并将其属性值从0更改为1.然后，使用该节点作为根节点，并将另一个节点作为第二个根节点，我在网络上进行了广度优先搜索（BFS）。
＃网络上的BFS
bfs< b $< p> ; - graph.bfs（graph，root = c（root_node，root_node2），unreachable = FALSE，
order = TRUE，dist = TRUE）
我想查看第一个根节点的邻居，然后查看第二个根节点的邻居，然后查看第一个根节点的邻居的邻居，然后查看第二个根节点的邻居根节点的邻居，等等。
所以有些东西像这样：
O＃注意：O *是第一个根节点
| ＃和O！是第二个根节点
|
O ---- O ---- O！---- O ---- O * ---- O ---- O ---- O
| |
| |
OO
因此，首先查看第一个根节点的邻居：
O＃注意：双连接是
| ＃到邻居
|的路径
O ---- O ---- O！---- O ==== O * ==== O ---- O ---- O
| ||
| ||
OO
然后查看第二个根节点的邻居：
O
|
|
O ---- O ==== O！==== O ---- O * ---- O ---- O ---- O
|| |
|| |
OO
然后，第一个根节点的邻居的邻居：
O
||
||
O ---- O ---- O！---- O ---- O * ---- O ==== O ---- O
| |
| |
OO
然后是第二个根节点的邻居的邻居：
O
|
|
O ==== O ---- O！---- O ---- O * ---- O ---- O ---- O
| |
| |
OO
依此类推，直到所有节点都被查看过：
O
|
|
O ---- O ---- O！---- O ---- O * ---- O ---- O ==== O
| |
| |
OO
在查看每个节点时，我想将其属性值从0到1，所以如果另一条路径来到它，它知道这个节点已被查看。
另外，有没有一种方法来计算有多少次迭代if需要查看所有节点？例如，这里是6（包括原来的）。
注意：两个根节点以某种方式连接（即它们之间有一条路径）。
很抱歉，这是基本的想法。希望这是有道理的。
任何帮助将不胜感激。谢谢！
以下是如何操作。首先，这是一个随机生成的图。
numnodes < - 50
the.graph< - grg。游戏（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 ）||
（short.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 （（curloop< maxloops）&&&（长度（curpos）> 0）&&
（sum（V（the curve））
curloop = 0
。 （长度（curpos）> 0）{
curnode < - curpos [1] $）{
nextpos< -c（）
b $ b curpos< - curpos [-1]
adjnodes< - which（thegraph [curnode] == 1）
for（adjnode in adjnodes）{$ b $如果（！V（the.graph）[adjnode] $ visited）{
nextpos< -c（nextpos，adjnode）
V（the.graph）[adjnode] $ visited <-1
}
}
}
curpos< - nextpos
curloop< - curloop + 1
}
现在我们访问了连接到最大度节点的所有节点。我们现在打印出遍历图的迭代次数。如果没有访问任何节点，则会另外打印一条消息，指出图形未连接。
print（curloop）
if（sum（V（the.graph）$ visited）
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!
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.")
这篇关于在R中的宽度优先搜索期间更改节点的属性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
