如何转换邻接表中的对称矩阵？

Question

我想知道从 R 中的邻接矩阵创建邻接列表的最快方法是什么。我目前正在使用 for-for 方法，但由于我必须处理大矩阵，最快的方法会很有帮助。

矩阵示例：

  A B C D
A 1 2 3 4
B 2 1 2 3
C 3 2 1 2
D 4 3 2 1

预期的邻接表：

A B 2
A C 3 
A D 4
B C 2
B D 3
C D 2

以下是testthat涵盖我当前代码的测试：

test_that("Matrix to List", {
  mat <- matrix(c(1,2,3,4,
                  2,1,2,3,
                  3,2,1,2,
                  4,3,2,1), ncol=4)
  colnames(mat) <- rownames(mat) <- letters[1:4]
  adj <- matrixToAdjacencyList(mat)
  expected <- data.frame(Columns=c("a", "a", "a", "b", "b", "c"),
                            Rows=c("b", "c", "d", "c", "d", "d"),
                           Value=c(2,3,4,2,3,2))
  expect_identical(adj, expected)
})

多谢。

Answer 1

您可以像对待您matrix一样table并使用该data.frame方法。

mat[lower.tri(mat, diag = TRUE)] <- NA
na.omit(data.frame(as.table(mat)))
#    Var1 Var2 Freq
# 5     A    B    2
# 9     A    C    3
# 10    B    C    2
# 13    A    D    4
# 14    B    D    3
# 15    C    D    2

从这里开始，只需清理dimnames并重新排序输出即可为您的testthat.

（或者，在第一行使用upper.tri代替lower.tri，然后将列顺序更改为以c(2, 1, 3)获得正确的列顺序 - 这可能比对许多行进行排序更有效。）