APL中传递边计算的精简实现、递归必要性及低内存方案问询

给定表示图中边的2阶向量：

m←3 2⍴3 5 5 9 6 3
      m
3 5
5 9
6 3

需要计算传递边（例如，由3→5和5→9可推导出3→9）。已实现单步传递边函数：

transitive_edges_one_step←{idx←⍸⍵[;2]∘.=⍵[;1] ⋄ 0=⍴idx:⍵ ⋄ ∪⍵⍪↑⍵∘{⍺[1⌷⍵;1],⍺[2⌷⍵;2]}¨idx}

通过幂运算符迭代至稳定状态可得到预期结果：

(transitive_edges_one_step⍣≡) m
3 5
5 9
6 3
3 9
6 5
6 9

现提出以下问题：

1. 有哪些更精简的实现方案？
2. 该问题是否必须采用递归类方法（如本例的幂运算符）？
3. 处理20000行的大2阶向量时，Dyalog中出现WS FULL错误，有无低内存解决方案？

问题解答 #

1. 更精简的实现方案 #

可以利用APL的矩阵运算特性简化实现，传递闭包本质是邻接矩阵的布尔闭包运算，再还原为边列表：

• 先将边转换为邻接矩阵：nodes←∪,m，adj←(nodes∘.=m[;1])∧.∨(nodes∘.=m[;2])
• 计算传递闭包：tc←(adj∨.∧adj)⍣≡adj（部分APL环境支持直接用tc←adj⍣.≡）
• 从闭包矩阵还原边列表：edges←nodes[⍋⍸tc],nodes[⍋⍉⍸tc]

另外，也可以用更紧凑的单步函数写法，直接通过集合运算拼接可推导的边：

transitive_short←{∪⍵,↑(⊂⍵[;1]),¨⊂⍵[⍸⍵[;2]∘.=⍵[;1];2]}

该函数直接定位首尾相连的边对，拼接新边后去重，逻辑更简洁。

2. 是否必须采用递归类方法？ #

不是必须的。除了迭代递推，还有多种非递归方案：

• 矩阵幂运算：传递闭包等价于邻接矩阵自身的布尔幂累积（adj∨adj∧.∧adj∨adj∧.∧adj∧.∧adj∨…），可通过向量化运算一次性计算。
• Warshall算法：通过三层循环的向量化实现，非递归地逐步更新节点间的可达关系，无需迭代递推即可得到闭包。
• 若处理的是等价关系闭包（对称+传递+自反），还可以用路径压缩的并查集，但该方法更适合无向图或等价类场景，有向图传递闭包优先选择矩阵或Warshall方案。

3. 大数据量下的低内存解决方案 #

20000行边列表若对应大量节点，全量邻接矩阵会占用N×N内存导致溢出，可采用以下方案：

• 分块处理：将节点划分为若干块，分别计算块内、块间的传递关系，逐步合并结果，避免一次性构建全量邻接矩阵。
• 基于节点可达集合的增量更新：用关联数组或命名空间存储每个节点的可达集合，每次迭代仅更新新增的可达关系，而非拼接全量边再去重：

  tc_hash←{
    nodes←∪,⍵
    reach←(nodes⍴⊂⍬)⌷⍨nodes  // 初始化每个节点的可达集合为空
    :For edge :In ⍵
        reach[edge[1]]←∪reach[edge[1]],edge[2],reach[edge[2]]
    :EndFor
    :Repeat
        updated←0
        :For n :In nodes
            new_reach←∪reach[n],∪reach¨reach[n]
            :If new_reach≢reach[n]
                reach[n]←new_reach
                updated←1
            :EndIf
        :EndFor
    :Until updated=0
    // 还原为边列表
    ↑,{(⍺,¨⍵)/⍵≢⍺}¨nodes reach
  }
  

  这种方式用集合存储可达关系，避免大量重复边的冗余存储，内存占用更低。
• 稀疏矩阵存储：使用Dyalog APL的稀疏矩阵（⎕SM）表示邻接关系和传递闭包，仅存储非零元素（实际存在的边），大幅降低内存消耗。

内容的提问来源于stack exchange，提问作者justin2004