Expand data.table with combinations of two columns given condition in another column

Question

I have a `data.table` that gives me the connections between locations (`origin` and `destination`) for different bus routes (`route_id`). ``` library(data.table) library(magrittr) # data for reproducible example dt <- data.table( origin = c('A','B','C', 'F', 'G', 'H'), destination = c('B','C','D', 'G', 'H', 'I'), freq = c(2,2,2,10,10,10), route_id = c(1,1,1,2,2,2), stringsAsFactors=FALSE ) # > dt # origin destination freq route_id # 1: A B 2 1 # 2: B C 2 1 # 3: C D 2 1 # 4: F G 10 2 # 5: G H 10 2 # 6: H I 10 2 ``` For the purposes of what I'd want to do, if there is a `route_id` that gives a connection `A-B` and a connection `B-C`, then I want to add to the data a connection `A-C` for that same `route_id` and so on. Problems: So far, I've created a simple code that does this job but: - it uses a `for loop` that takes a long time (my real data has hundreds of thousands observations) - it still does not cope well with direction. The direction of the connections matter here. So although…

Accepted Answer

One way:

```
res = dt[, {
  stops = c(origin, last(destination))
  pairs = combn(.N + 1L, 2L)
  .(o = stops[pairs[1,]], d = stops[pairs[2,]])
}, by=route_id]

route_id o d
 1:        1 A B
 2:        1 A C
 3:        1 A D
 4:        1 B C
 5:        1 B D
 6:        1 C D
 7:        2 F G
 8:        2 F H
 9:        2 F I
10:        2 G H
11:        2 G I
12:        2 H I
```

This is assuming that `c(origin, last(destination))` is a full list of stops in order. If `dt` does not contain enough info to construct a complete order, the task becomes much more difficult.

If vars from `dt` are needed, an update join like `res[dt, on=.(route_id), freq := i.freq]` works.

Tasks like this always risk running out of memory. In this case, the OP has up to a million rows containing groups of up to 341 stops, so the end result could be as large as `1e6/341*choose(341,2)` = 170 million rows. That's manageable, but in general this sort of analysis does not scale.

How it works

Generally, data.table syntax can be treated just like a loop over groups:

```
DT[, { 
  ...
}, by=g]
```

This has a few advantages over loops:

- Nothing created in the `...` body will pollute the workspace.

- All columns can be referenced by name.

- Special symbols `.N`, `.SD`, `.GRP` and `.BY` are available, along with `.()` for `list()`.

In the code above, `pairs` finds pairs of indices taken from 1 .. #stops (=.N+1 where .N is the number of rows in the subset of the data associated with a given route_id). It is a matrix with the first row corresponding to the first element of a pair; and the second row with the second. The `...` should evaluate to a list of columns; and here `list()` is abbreviated as `.()`.

Further improvements

I guess the time is mostly devoted to computing `combn` many times. If multiple routes have the same #stops, this can be addressed by computing beforehand:

```
Ns = dt[,.N, by=route_id][, unique(N)]
cb = lapply(setNames(,Ns), combn, 2)
```

Then grab `pairs = cb[[as.character(.N)]]` in the main code. Alternately, define a `pairs` function that uses memoization to avoid recomputing.

Expand data.table with combinations of two columns given condition in another column

Solution

Problem