英文:
Calculating cumulative sum of vertices in a directed graph with route priorities with R or Python
问题
我正在使用R中的igraph处理有向图,并且遇到了一个特定的问题,我无法解决。每个顶点都有一个权重为1,我想计算考虑以下条件的顶点的累积和:
- “Fiber”路由优先于“Micro”路由。
- 如果有两个“Fiber”或“Micro”路由,物理距离(以千米为单位)决定选择哪一个。
- 解决方案不应涉及删除或添加任何边,即即使是为了计算目的,所有现有的连接也应保持不变。
以下是我的图的简化示例。为了方便起见,我使用R,但也可以使用Python:
library(igraph)
library(dplyr)
edges <- tribble(
~from, ~to, ~tipo, ~distance_km, ~color, ~width,
"A", "B", "Fiber", 10, "black", 2,
"B", "C", "Fiber", 5, "black", 2,
"B", "C", "Fiber", 6, "gray", 0.5,
"A", "C", "Micro", 5, "gray", 0.5,
"C", "D", "Micro", 1, "black", 2,
"C", "D", "Micro", 2, "gray", 0.5
)
edges <- edges %>%
mutate(label = paste0(tipo, " (", distance_km, ")"))
g <- graph_from_data_frame(edges, directed = TRUE)
V(g)$name <- paste0(V(g)$name, " (", 1:4, ")")
plot(g, edge.label = E(g)$label)
如何根据上述条件计算顶点的累积和?
在下面的图像中,您可以看到我期望算法必须决定以实现累积和的路径为黑色。
非常感谢任何指导或帮助。
英文:
I'm working with a directed graph in R using igraph and I have a specific issue that I'm unable to resolve. Each vertex carries a weight of 1 and I want to calculate the cumulative sum of the vertices taking into account the following conditions:
- "Fiber" routes have priority over 'Micro' routes.
- If there are two 'Fiber' or 'Micro' routes, the physical distance in kilometers determines which one is selected.
- The solution should not involve removing or adding any edges, i.e., even for calculation purposes, all the existing connections should remain intact.
Here is a simplified example of my graph. For convenience I use R, but it can be in Python:
library(igraph)
library(dplyr)
edges <- tribble(
~from, ~to, ~tipo, ~distance_km, ~color, ~width,
"A", "B", "Fiber", 10, "black", 2,
"B", "C", "Fiber", 5, "black", 2,
"B", "C", "Fiber", 6, "gray", 0.5,
"A", "C", "Micro", 5, "gray", 0.5,
"C", "D", "Micro", 1, "black", 2,
"C", "D", "Micro", 2, "gray", 0.5
)
edges <- edges %>%
mutate(label = paste0(tipo, " (", distance_km, ")"))
g <- graph_from_data_frame(edges, directed = TRUE)
V(g)$name <- paste0(V(g)$name, " (", 1:4, ")")
plot(g, edge.label = E(g)$label)
How can I calculate the cumulative sum of the vertices following the conditions described above?
In the next image you can see in black the paths that I expect the algorithm must decide to achieve the cumulative sum.
Any guidance or help would be greatly appreciated.
答案1
得分: 0
更新
给定一个顶点权重为 wt=1
的图,即,
edges <- edges %>%
mutate(label = paste0(tipo, " (", distance_km, ")"))
g <- graph_from_data_frame(edges, directed = TRUE) %>%
set_vertex_attr(name = "wt", value = 1)
可以通过以下方式获得沿期望路径的累积权重
v <- names(which(degree(g, mode = "in") == 0))
P <- v
repeat {
if (degree(g, v, "out") == 0) {
break
}
v <- edges %>%
filter(from == v) %>%
arrange(match(tipo, c("Fiber", "Micro")), distance_km) %>%
slice_head() %>%
select(to) %>%
pluck(1)
P <- append(P, v)
}
gout <- g %>%
set_vertex_attr(
name = "cumwt",
index = match(V(.)$name, P),
value = cumsum(V(.)$wt[match(V(.)$name, P)])
)
这样
> gout
IGRAPH 3f25ba4 DN-- 4 6 --
+ attr: name (v/c), wt (v/n), cumwt (v/n), tipo (e/c), distance_km
| (e/n), color (e/c), width (e/n), label (e/c)
+ edges from 3f25ba4 (vertex names):
[1] A->B B->C B->C A->C C->D C->D
> V(gout)
+ 4/4 vertices, named, from 3f25ba4:
[1] A B C D
> V(gout)$wt
[1] 1 1 1 1
> V(gout)$cumwt
[1] 1 2 3 4
之前: 如果你想要edge
数据框的子集来指示路由
假设你总是只有一个源和一个汇,那么这是我的尝试,可能效率有点低
route <- c()
v <- names(which(degree(g, mode = "in") == 0))
repeat {
if (degree(g, v, "out") == 0) {
break
}
p <- edges %>%
filter(from == v) %>%
arrange(match(tipo, c("Fiber", "Micro")), distance_km) %>%
slice_head()
route <- rbind(route, p)
v <- p$to
}
然后你会得到一个数据框中的路径(从上到下)
> route
# A tibble: 3 × 7
from to tipo distance_km color width label
<chr> <chr> <chr> <dbl> <chr> <dbl> <chr>
1 A B Fiber 10 black 2 Fiber (10)
2 B C Fiber 5 black 2 Fiber (5)
3 C D Micro 1 black 2 Micro (1)
英文:
Update
Given a graph with vertex weights wt=1
for all vertices, i.e.,
edges <- edges %>%
mutate(label = paste0(tipo, " (", distance_km, ")"))
g <- graph_from_data_frame(edges, directed = TRUE) %>%
set_vertex_attr(name = "wt", value = 1)
the cumulative weights along the desired routing can be obtain like below
v <- names(which(degree(g, mode = "in") == 0))
P <- v
repeat {
if (degree(g, v, "out") == 0) {
break
}
v <- edges %>%
filter(from == v) %>%
arrange(match(tipo, c("Fiber", "Micro")), distance_km) %>%
slice_head() %>%
select(to) %>%
pluck(1)
P <- append(P, v)
}
gout <- g %>%
set_vertex_attr(
name = "cumwt",
index = match(V(.)$name, P),
value = cumsum(V(.)$wt[match(V(.)$name, P)])
)
such that
> gout
IGRAPH 3f25ba4 DN-- 4 6 --
+ attr: name (v/c), wt (v/n), cumwt (v/n), tipo (e/c), distance_km
| (e/n), color (e/c), width (e/n), label (e/c)
+ edges from 3f25ba4 (vertex names):
[1] A->B B->C B->C A->C C->D C->D
> V(gout)
+ 4/4 vertices, named, from 3f25ba4:
[1] A B C D
> V(gout)$wt
[1] 1 1 1 1
> V(gout)$cumwt
[1] 1 2 3 4
Previous: If you want to have a subset of edge
dataframe to indicate the routing
Assuming you have one source and one sink only always, then here is my attempt, which works but might be a bit inefficient
route <- c()
v <- names(which(degree(g, mode = "in") == 0))
repeat {
if (degree(g, v, "out") == 0) {
break
}
p <- edges %>%
filter(from == v) %>%
arrange(match(tipo, c("Fiber", "Micro")), distance_km) %>%
slice_head()
route <- rbind(route, p)
v <- p$to
}
and you will obtain the route in a dataframe (from top to bottom)
> route
# A tibble: 3 × 7
from to tipo distance_km color width label
<chr> <chr> <chr> <dbl> <chr> <dbl> <chr>
1 A B Fiber 10 black 2 Fiber (10)
2 B C Fiber 5 black 2 Fiber (5)
3 C D Micro 1 black 2 Micro (1)
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论