数据表中的"recursive"自连接

Question

数据表中的"recursive"自连接

5

我有一个由三列组成的组件列表：产品、组件和使用的组件数量：

a <- structure(list(prodName = c("prod1", "prod1", "prod2", "prod3", 
"prod3", "int1", "int1", "int2", "int2"), component = c("a", 
"int1", "b", "b", "int2", "a", "b", "int1", "d"), qty = c(1L, 
2L, 3L, 4L, 5L, 6L, 7L, 8L, 9L)), row.names = c(NA, -9L), class = c("data.table", 
"data.frame"))

  prodName component qty
1    prod1         a   1
2    prod1      int1   2
3    prod2         b   3
4    prod3         b   4
5    prod3      int2   5
6     int1         a   6
7     int1         b   7
8     int2      int1   8
9     int2         d   9

名称以prod开头的产品是最终产品，名称类似于int的产品是中间产品，而只有字母的产品是原材料。

我需要所有仅由原材料组成的最终产品的完整组件列表。也就是说，我希望将任何int转换为原材料。

中间产品可以由原材料和另一个中间产品组成，因此我称之为“递归”。
我无法提前知道中间产品的嵌套/递归级别（在此示例中为2级，在实际数据中超过6级）。

对于此示例，我的预期结果为（我明确说明了所得出的数字计算）：

prodName  |component  |qty
prod1     |a          |1+2*6 = 13
prod1     |b          |0+2*7 = 14
prod2     |b          |3
prod3     |b          |4+5*8*7 = 284
prod3     |a          |0+5*8*6 = 240
prod3     |d          |0+5*9 = 45

我的工作：

我通过使用merge创建了一系列繁琐的连接来解决这个问题。虽然这种方法对于玩具数据有效，但我无法将其应用于真实数据。

#load data.table
library(data.table)

# split the tables between products and different levels of intermediate
a1 <- a[prodName %like% "prod",]
b1 <- a[prodName %like% "int1",]
c1 <- a[prodName %like% "int2",]

# convert int2 to raw materials
d1 <- merge(c1, 
            b1, 
            by.x = "component", 
            by.y = "prodName", 
            all.x = TRUE)[
              is.na(component.y),
              component.y := component][
                is.na(qty.y),
                qty.y := 1][,
                                .(prodName, qty = qty.x*qty.y),
                                by = .(component = component.y)]

# Since int1 is already exploded into raw materials, rbind both tables:
d1 <- rbind(d1, b1)

# convert all final products into raw materials, except that the raw mats that go directly into the product won't appear:
e1 <- merge(a1, 
            d1, 
            by.x = "component", 
            by.y = "prodName", 
            all.x = TRUE)

# rbind the last calculated raw mats (those coming from intermediate products) with those coming _directly_ into the final product:
result <- rbind(e1[!is.na(qty.y), 
                   .(prodName, qty = qty.x * qty.y), 
                   by = .(component = component.y)], 
                e1[is.na(qty.y), 
                   .(prodName, component, qty = qty.x)])[, 
                                                         .(qty = sum(qty)), 
                                                         keyby = .(prodName, component)]

我知道我可以将数据分成表格，并进行连接，直到每个中间产品都只由原材料组成，但如上所述，由于数据的大小和中间产品的递归级别，这将是最后的选择。有没有更容易/更好的方法来执行这种递归连接？

- PavoDive

你能否将 qty 的例子改成不同的数字，比如 1:9 （不确定它们是否都可以不同）？ - M--

@M-M 请查看我的修改后的代码。 - PavoDive

3个回答

3

这是使用您的数据集尝试的结果。

它使用一个`while`循环来检查是否存在任何在`prodName`字段中也有的`components`。循环始终需要具有相同的字段，因此不需要为递归乘数添加列（即末尾的5*8*7），而是将迭代乘数集成在内。也就是说，5 * 8 * 7在最后变成了5 * 56。

library(data.table)

a[, qty_multiplier := 1]
b <- copy(a)

while (b[component %in% prodName, .N] > 0) {
  b <- b[a
         , on = .(prodName = component)
         , .(prodName = i.prodName
             , component = ifelse(is.na(x.component), i.component, x.component)
             , qty = i.qty
             , qty_multiplier = ifelse(is.na(x.qty), 1, x.qty * qty_multiplier)
         )
         ]
}

b[prodName %like% 'prod', .(qty = sum(qty * qty_multiplier)), by = .(prodName, component)] 

   prodName component qty
1:    prod1         a  13
2:    prod1         b  14
3:    prod2         b   3
4:    prod3         b 284
5:    prod3         a 240
6:    prod3         d  45

- Cole

1

我认为最好用一组邻接矩阵来表示信息，告诉你“这个东西有多少是由那个东西组成的”。你需要四个矩阵，对应所有可能的关系。例如，你可以将最终产品和中间产品之间的关系放在一个3行2列的矩阵中，如下所示：

QPI <- matrix(0,3,2)
row.names(QPI) <- c("p1","p2","p3")
colnames(QPI) <- c("i1","i2")

QPI["p1","i1"] <- 2
QPI["p3","i2"] <- 5

   i1 i2
p1  2  0
p2  0  0
p3  0  5

这段话告诉你，制造一个最终产品p1需要两个中间产品i1的单位。

同样地，你可以定义其他矩阵：

QPR <- matrix(0,3,3)
row.names(QPR) <- c("p1","p2","p3")
colnames(QPR) <- c("a","b","d")

QPR["p1","a"] <- 1
QPR["p2","b"] <- 3
QPR["p3","b"] <- 4

QIR <- matrix(0,2,3)
row.names(QIR) <- c("i1","i2")
colnames(QIR) <- c("a","b","d")

QIR["i1","a"] <- 6
QIR["i1","b"] <- 7
QIR["i2","d"] <- 9

QII <- matrix(0,2,2)
row.names(QII) <- colnames(QII) <- c("i1","i2")

例如，观察QIR，我们发现制造一个中间产品i1需要6个单位的原材料a。一旦以这种方式获得，您可以通过矩阵乘法对从原材料到最终产品的所有可能路径进行求和。您有3个术语：您可以直接从原材料到最终产品[QPR] QPR，或者从原材料到中间产物再到最终产品[QPI%*%QIR]，或者从原材料到其他中间产物再到最终产品[QPI%*%QII%*%QIR]。最终结果由矩阵表示。

result <- QPI%*%QIR + QPI%*%QII%*%QIR + QPR

我把所有的代码放在下面。如果你运行它，你会看到结果长这样：

     a   b  d
p1  13  14  0
p2   0   3  0
p3 240 284 45

这句话的意思与下面的话完全相同

prodName  |component  |qty
prod1     |a          |1+2*6 = 13
prod1     |b          |0+2*7 = 14
prod2     |b          |3
prod3     |b          |4+5*8*7 = 284
prod3     |a          |0+5*8*6 = 240
prod3     |d          |0+5*9 = 45

希望这有所帮助。

QPI <- matrix(0,3,2)
row.names(QPI) <- c("p1","p2","p3")
colnames(QPI) <- c("i1","i2")

QPI["p1","i1"] <- 2
QPI["p3","i2"] <- 5

QPR <- matrix(0,3,3)
row.names(QPR) <- c("p1","p2","p3")
colnames(QPR) <- c("a","b","d")

QPR["p1","a"] <- 1
QPR["p2","b"] <- 3
QPR["p3","b"] <- 4

QIR <- matrix(0,2,3)
row.names(QIR) <- c("i1","i2")
colnames(QIR) <- c("a","b","d")

QIR["i1","a"] <- 6
QIR["i1","b"] <- 7
QIR["i2","d"] <- 9

QII <- matrix(0,2,2)
row.names(QII) <- colnames(QII) <- c("i1","i2")


QII["i2","i1"] <- 8

result <- QPI%*%QIR + QPI%*%QII%*%QIR + QPR
print(result)

- FGirosi

1

感谢您的建议。我会考虑如何通过编程将我的数据转换为一组未知的qpr qpi qii qir矩阵。正如我在问题中所述，我有一个疑问，即我可能有许多嵌套级别的中间产品，这将需要（嵌套？）qii矩阵。如果您有任何关于如何做到这一点的想法，我会非常感激您与我分享。 - PavoDive

我不确定我完全理解“嵌套”。你能给我举一个更深层次的嵌套例子吗？只是为了更好地理解。谢谢。 - FGirosi

Prod20 由 a + int18 组成；int18 由 k + int14 组成；int14 由 int3 + int4 组成；int3 由 b 和 c 组成；int4 由 g + h 组成。我称之为“嵌套中间产品”（缺乏更好的名称），将它们中的每一个转化为原材料就是我所谓的“递归”（这可能也是一个不太好的名称）。 - PavoDive

抱歉回复晚了。感谢您的澄清，我现在明白您的意思了。上述方法以及使用igraph的出色解决方案将独立于嵌套级别的数量。它们都放在一个QII矩阵中，矩阵乘法会处理所有可能的贡献总和。我不太熟悉igraph，但我相信如果您想提取Q矩阵，该库会为您完成：这些是不同子图的邻接矩阵。希望这有所帮助。 - FGirosi

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Joris C. · Accepted Answer

本质上，您的数据代表有向图中的加权边列表。以下代码直接使用 igraph 库计算从原始组件到最终产品的每个简单路径上的距离（乘积）之和：

library(igraph)

## transform edgelist into graph
graph <- graph_from_edgelist(as.matrix(a[, c(2, 1)])) %>%
  set_edge_attr("weight", value = unlist(a[, 3]))

## combinations raw components -> final products
out <- expand.grid(prodname = c("prod1", "prod2", "prod3"), component = c("a", "b", "d"), stringsAsFactors = FALSE)

## calculate quantities
out$qty <- mapply(function(component, prodname) {

  ## all simple paths from component -> prodname
  all_paths <- all_simple_paths(graph, from = component, to = prodname)

  ## if simple paths exist, sum over product of weights for each path
  ifelse(length(all_paths) > 0,
         sum(sapply(all_paths, function(path) prod(E(graph, path = path)$weight))), 0)

}, out$component, out$prodname)

out
#>   prodname component qty
#> 1    prod1         a  13
#> 2    prod2         a   0
#> 3    prod3         a 240
#> 4    prod1         b  14
#> 5    prod2         b   3
#> 6    prod3         b 284
#> 7    prod1         d   0
#> 8    prod2         d   0
#> 9    prod3         d  45