使用R或Python计算具有路由优先级的有向图中顶点的累积和。

huangapple go评论77阅读模式
英文:

Calculating cumulative sum of vertices in a directed graph with route priorities with R or Python

问题

我正在使用R中的igraph处理有向图,并且遇到了一个特定的问题,我无法解决。每个顶点都有一个权重为1,我想计算考虑以下条件的顶点的累积和:

  1. “Fiber”路由优先于“Micro”路由。
  2. 如果有两个“Fiber”或“Micro”路由,物理距离(以千米为单位)决定选择哪一个。
  3. 解决方案不应涉及删除或添加任何边,即即使是为了计算目的,所有现有的连接也应保持不变。

以下是我的图的简化示例。为了方便起见,我使用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)

如何根据上述条件计算顶点的累积和?

在下面的图像中,您可以看到我期望算法必须决定以实现累积和的路径为黑色。

使用R或Python计算具有路由优先级的有向图中顶点的累积和。

非常感谢任何指导或帮助。

英文:

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:

  1. "Fiber" routes have priority over 'Micro' routes.
  2. If there are two 'Fiber' or 'Micro' routes, the physical distance in kilometers determines which one is selected.
  3. 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 &lt;- tribble(
  ~from,  ~to, ~tipo, ~distance_km, ~color, ~width,
  &quot;A&quot;,    &quot;B&quot;, &quot;Fiber&quot;, 10, &quot;black&quot;, 2,
  &quot;B&quot;,    &quot;C&quot;, &quot;Fiber&quot;, 5, &quot;black&quot;, 2,
  &quot;B&quot;,    &quot;C&quot;, &quot;Fiber&quot;, 6, &quot;gray&quot;, 0.5,
  &quot;A&quot;,    &quot;C&quot;, &quot;Micro&quot;, 5, &quot;gray&quot;, 0.5,
  &quot;C&quot;,    &quot;D&quot;, &quot;Micro&quot;, 1, &quot;black&quot;, 2,
  &quot;C&quot;,    &quot;D&quot;, &quot;Micro&quot;, 2, &quot;gray&quot;, 0.5
)

edges &lt;- edges %&gt;%
  mutate(label = paste0(tipo, &quot; (&quot;, distance_km, &quot;)&quot;))

g &lt;- graph_from_data_frame(edges, directed = TRUE)

V(g)$name &lt;- paste0(V(g)$name, &quot; (&quot;, 1:4, &quot;)&quot;)

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.

使用R或Python计算具有路由优先级的有向图中顶点的累积和。

Any guidance or help would be greatly appreciated.

答案1

得分: 0

更新

给定一个顶点权重为 wt=1 的图,即,

edges &lt;- edges %&gt;%
    mutate(label = paste0(tipo, &quot; (&quot;, distance_km, &quot;)&quot;))

g &lt;- graph_from_data_frame(edges, directed = TRUE) %&gt;%
    set_vertex_attr(name = &quot;wt&quot;, value = 1)

可以通过以下方式获得沿期望路径的累积权重

v &lt;- names(which(degree(g, mode = &quot;in&quot;) == 0))
P &lt;- v
repeat {
    if (degree(g, v, &quot;out&quot;) == 0) {
        break
    }
    v &lt;- edges %&gt;%
        filter(from == v) %&gt;%
        arrange(match(tipo, c(&quot;Fiber&quot;, &quot;Micro&quot;)), distance_km) %&gt;%
        slice_head() %&gt;%
        select(to) %&gt;%
        pluck(1)
    P &lt;- append(P, v)
}

gout &lt;- g %&gt;%
    set_vertex_attr(
        name = &quot;cumwt&quot;,
        index = match(V(.)$name, P),
        value = cumsum(V(.)$wt[match(V(.)$name, P)])
    )

这样

&gt; 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-&gt;B B-&gt;C B-&gt;C A-&gt;C C-&gt;D C-&gt;D

&gt; V(gout)
+ 4/4 vertices, named, from 3f25ba4:
[1] A B C D

&gt; V(gout)$wt
[1] 1 1 1 1

&gt; V(gout)$cumwt
[1] 1 2 3 4

之前: 如果你想要edge数据框的子集来指示路由

假设你总是只有一个源和一个汇,那么这是我的尝试,可能效率有点低

route &lt;- c()
v &lt;- names(which(degree(g, mode = &quot;in&quot;) == 0))
repeat {
    if (degree(g, v, &quot;out&quot;) == 0) {
        break
    }
    p &lt;- edges %&gt;%
        filter(from == v) %&gt;%
        arrange(match(tipo, c(&quot;Fiber&quot;, &quot;Micro&quot;)), distance_km) %&gt;%
        slice_head()
    route &lt;- rbind(route, p)
    v &lt;- p$to
}

然后你会得到一个数据框中的路径(从上到下)

&gt; route
# A tibble: 3 &#215; 7
  from  to    tipo  distance_km color width label
  &lt;chr&gt; &lt;chr&gt; &lt;chr&gt;       &lt;dbl&gt; &lt;chr&gt; &lt;dbl&gt; &lt;chr&gt;
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 &lt;- edges %&gt;%
    mutate(label = paste0(tipo, &quot; (&quot;, distance_km, &quot;)&quot;))

g &lt;- graph_from_data_frame(edges, directed = TRUE) %&gt;%
    set_vertex_attr(name = &quot;wt&quot;, value = 1)

the cumulative weights along the desired routing can be obtain like below

v &lt;- names(which(degree(g, mode = &quot;in&quot;) == 0))
P &lt;- v
repeat {
    if (degree(g, v, &quot;out&quot;) == 0) {
        break
    }
    v &lt;- edges %&gt;%
        filter(from == v) %&gt;%
        arrange(match(tipo, c(&quot;Fiber&quot;, &quot;Micro&quot;)), distance_km) %&gt;%
        slice_head() %&gt;%
        select(to) %&gt;%
        pluck(1)
    P &lt;- append(P, v)
}

gout &lt;- g %&gt;%
    set_vertex_attr(
        name = &quot;cumwt&quot;,
        index = match(V(.)$name, P),
        value = cumsum(V(.)$wt[match(V(.)$name, P)])
    )

such that

&gt; 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-&gt;B B-&gt;C B-&gt;C A-&gt;C C-&gt;D C-&gt;D

&gt; V(gout)
+ 4/4 vertices, named, from 3f25ba4:
[1] A B C D

&gt; V(gout)$wt
[1] 1 1 1 1

&gt; 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 &lt;- c()
v &lt;- names(which(degree(g, mode = &quot;in&quot;) == 0))
repeat {
    if (degree(g, v, &quot;out&quot;) == 0) {
        break
    }
    p &lt;- edges %&gt;%
        filter(from == v) %&gt;%
        arrange(match(tipo, c(&quot;Fiber&quot;, &quot;Micro&quot;)), distance_km) %&gt;%
        slice_head()
    route &lt;- rbind(route, p)
    v &lt;- p$to
}

and you will obtain the route in a dataframe (from top to bottom)

&gt; route
# A tibble: 3 &#215; 7
  from  to    tipo  distance_km color width label
  &lt;chr&gt; &lt;chr&gt; &lt;chr&gt;       &lt;dbl&gt; &lt;chr&gt; &lt;dbl&gt; &lt;chr&gt;
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) 

huangapple
  • 本文由 发表于 2023年6月16日 01:32:23
  • 转载请务必保留本文链接:https://go.coder-hub.com/76484176.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定