DAG shortest path in R - I have a list of nodes, each node's completion time and each node's predecessor(s). How can I turn this to a list of arcs?

Question

Without trying to manually sketch out a graph on paper, is there a simple way I could get the arcs between nodes in this problem? I am using R and it seems there must be an elegant way of doing so but I'm at a loss. I'm going to need to be passing this into getShortestPathTree() from optrees, which takes a matrix with the list of arcs of the graph. Each row represents one arc. The first two columns contain the two endpoints of each arc and the third column contains their weights.

By going through with a pen and paper and sketching the graph I was able to create this matrix but I'm just looking for a simpler solution.

head =   c(1,1,1,     2,  3, 4,4,4,    6,  7,  9)
tail =   c(2,6,9,     3,  7, 5,8,10,   7,  4,  10)
weight = c(90,90,90,  15, 5, 20,20,20, 21, 25, 30)

arcs = cbind(head, tail, weight)
head(arcs)
     head tail weight
[1,]    1    2     90
[2,]    1    6     90
[3,]    1    9     90
[4,]    2    3     15
[5,]    3    7      5
[6,]    4    5     20

Answer 1

The problem here seems to be that the data is provided in a somewhat untidy fashion. To use the function the data needs to be preprocessed to extract each entry from the column "Predecessor(s)". You can use the function separate_rows from the R package tidyr (contained in the tidyverse) to do this. You'll also have to convert the letters to numbers.

library(tidyverse)

myLetters <- LETTERS[1:26]

raw_table <- tribble(
    ~Task, ~Predecessors, ~ECT,
    "A", "-", 90,
    "B", "A", 15,
    "C", "B,A", 25,
    "D", "A,B,C", 10
)

processed_table <- raw_table %>% 
    separate_rows(Predecessors) %>%
    filter(Predecessors != "") %>%
    transmute(start=match(Predecessors, myLetters), 
              end=match(Task, myLetters),
              weight=ECT)
processed_table
#> # A tibble: 6 x 3
#>   start   end weight
#>   <int> <int>  <dbl>
#> 1     1     2     15
#> 2     2     3     25
#> 3     1     3     25
#> 4     1     4     10
#> 5     2     4     10
#> 6     3     4     10