# 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?

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)
[1,]    1    2     90
[2,]    1    6     90
[3,]    1    9     90
[4,]    2    3     15
[5,]    3    7      5
[6,]    4    5     20


• Hi Jacob, welcome to OR.SE. I'm not sure whether I understand your problem correctly. Is it you are given the table and want to extract the underlying graph from it in an automated fashion? That is, you have as input the table and want as output the matrix that you can feed to the function in R? Sep 26, 2019 at 7:25
• @JakobS Thats a good summary of my problem. I need to make a table that looks like arc. The far right column needs to correspond to the task # in head, these are the weights of the arcs that go from The head to tail I should have clarified that the numbers in head refer to tasks, so 1 is task A, 2 is task B and so on. Sep 26, 2019 at 11:25
• Do you have the input table (the one with the predecessors column) in R already? If so, what does it look like? For instance, if a data frame, can you show its structure here?
– prubin
Sep 28, 2019 at 17:59

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(
"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),