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

Question

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 <- 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.

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