0

我使用numpy矩阵来表示有向图，如下所示：

0 0 0
1 0 1
1 0 0

给定这样一个矩阵，我想找到所有缺失的有向边，其中存在相反方向的有向边。

例如，在上面的矩阵中，对于节点1（索引为 0），边1 -> 2和1 -> 3在这个意义上是缺失的，因为存在边2 -> 1和3 -> 1在另一个方向上。同样，3 -> 2由于存在 edge ，所以 edge 也丢失了2 -> 3。

我的应用程序中的实际矩阵很大，例如数千个节点，并且找到这些边的算法必须很快。一种蛮力的方法是检查每一对（考虑到矩阵的主对角线，它们是对称的），看看两者之间是否缺少一条边。

我想知道是否有更有效的方法（numpy也许提供？）来做到这一点。一些线性代数技巧？

4

2 回答 2

2

我稍微修改了您的示例以显示一对节点在两个方向上连接的情况。这是一种使用 numpy 的方法：

import numpy as np

A = np.array([[0, 1, 0],
              [1, 0, 1],
              [1, 0, 0]]).astype(bool)

A = A
print A.astype(int)
B = A.transpose() & ~A
print B.astype(int)

这应该给出：

[[0 1 0]
 [1 0 1]
 [1 0 0]]
[[0 0 1]
 [0 0 0]
 [0 1 0]]

我相信这就是你想要的。如果你的矩阵非常大，你可以考虑使用稀疏矩阵，但原理是一样的。

说明：

对于任何边 A[i,j]，该边的倒数是 A[j,i]。A[j,i] 与 A.transpose()[i,j] 相同。因此，如果您反转每条边的方向，A.transpose() 就是您绘制的邻接矩阵。~ 运算符等效于 np.logical_not 函数。在没有边的地方，~A 的值为 1。您对“丢失的连接”感兴趣，即不在 A 中但在 A.transpose() 中的连接。您可以在 A.transpose() 和 ~A 上使用 & 运算符获得这些连接，该运算符等效于 np.logical_and。

于 2013-07-12T16:56:16.317 回答
0

像这样的邻接矩阵应该是对称的。取下三角形部分，将其转置并与上三角形部分进行比较呢？像这样的东西：

low = tril(m).transpose()
upp = triu(m)
missing = mod(low + upp, 2)

missing应该是 1，其中上三角部分缺少位置。

如果您只关心确保上部正确，则可以执行以下操作：

m = tril(m).transpose() + tril(m)
于 2013-07-12T16:46:21.187 回答