0

次のように、行列を使用してnumpy有向グラフを表します。

0 0 0
1 0 1
1 0 0

このような行列が与えられた場合、反対方向に有向エッジが存在するすべての欠落している有向エッジを見つけたいと考えています。

たとえば、上記のマトリックスでは、ノード1(インデックス 0) について、エッジ1 -> 2と反対方向に1 -> 3エッジが存在するため、この意味ではエッジとエッジが欠落してい2 -> 1ます。3 -> 1同様に、 edge3 -> 2が存在するため、 edge も欠落しています2 -> 3。

私のアプリケーションの実際の行列は数千のノードなど、大きく、そのようなエッジを見つけるためのアルゴリズムは高速でなければなりません。力ずくの方法は、すべてのペア (行列の主対角線を考慮して対称) をチェックし、2 つの間にエッジがないかどうかを確認することです。

それを行うためのより効率的な方法（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 に答える