创建网络拓扑

Question

我从一个网络中获取数据，其中包含所有调制解调器、网络元素以及最后的技术站点，我想为每个调制解调器创建一个包含拓扑的向量。

网络具有树状结构。对于我的问题，假设它看起来像：

红色的是技术站点，绿色的是调制解调器。黄色的是介于两者之间的拓扑元素。此信息位于以下数据集中：

library(data.table)

df1 = structure(list(mac = c("A90", "BCF", "12A", "D4B"), top = c(100L, 
200L, 300L, 400L)), row.names = c(NA, -4L), class = c("data.table","data.frame"))

   mac  top
1: A90 100
2: BCF 200
3: 12A 300
4: D4B 400


df2 = structure(list(a = c(100L, 150L, 156L, 800L, 200L, 203L, 300L, 
400L, 111L, 963L), b = c(150L, 156L, 800L, 263L, 203L, 800L, 
263L, 111L, 963L, 156L)), row.names = c(NA, -10L), class = c("data.table","data.frame"))

> df2
   a   b
1: 100 150
2: 150 156
3: 156 800
4: 800 263
5: 200 203
6: 203 800
7: 300 263
8: 400 111
9: 111 963
10: 963 156

a代表起点，b代表目标。

现在我想为每个调制解调器创建如下所示的拓扑结构：

df_target = structure(list(mac = c("A90", "BCF", "12A", "D4B"), topo_complete = c("100, 150, 156, 800, 263", 
"200, 203, 800, 263", "300, 263", "400, 111, 963, 156, 800, 263"
)), row.names = c(NA, -4L), class = c("data.table", "data.frame"))
   mac      topo_complete 
1: A90           100, 150, 156, 800, 263
2: BCF                200, 203, 800, 263
3: 12A                          300, 263
4: D4B      400, 111, 963, 156, 800, 263

或者换句话说：对于 df1 中的每个调制解调器 (mac)，取 top 值并在 df2.a 中搜索其目标 (df.b)，然后取此目标值，将其存储并用它来搜索它是否存在于 df2.a 中。如果是，再次选择目标 (df.b) 并重复。只要它不再找到任何目标值。目标点永远不会多于一个，所以不需要处理多于一个目标点的情况。

老实说，我不知道如何解决这个问题。此外，由于现实世界的数据有超过一百万个 mac 和大约 100k 的拓扑元素，它必须在 speed/performance 方面有效。内存使用无关紧要。如果可能的话，我想使用 data.table.

有人可以帮忙吗？

Answer 1

一种方法是使用 igraph 包：

library(igraph)
library(data.table)

g <- graph_from_data_frame(df2, directed = TRUE)
df1[, topo_complete := lapply(as.character(top), function(x) names(subcomponent(g, x, mode = "out")))]

创建网络拓扑

Creating topology of a network

r

data.table