6
$\begingroup$

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

enter image description here

$\endgroup$
3
  • 1
    $\begingroup$ 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? $\endgroup$
    – JakobS
    Sep 26 '19 at 7:25
  • $\begingroup$ @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. $\endgroup$
    – Jacob Myer
    Sep 26 '19 at 11:25
  • 1
    $\begingroup$ 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? $\endgroup$
    – prubin
    Sep 28 '19 at 17:59
3
$\begingroup$

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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.