在邻接矩阵中形成一个循环的节点（Matlab）

Question

我有一个有向边的邻接矩阵。计算A^3将帮助我检测矩阵中是否有任何长度为3（三角形）的周期。但是，我想知道哪些节点形成三角形。我如何在Matlab中实现这一点？

感谢

Answer 1

与矩阵乘法的问题是，它加起来所有行。当矩阵P的第一行乘以矩阵Q的第一列时，它执行元素方式的乘法，然后生成结果向量的总和，丢弃关于中间节点的所有数据。那么，我们需要这个矢量，所以让我们停止添加它。

说我们有我们的邻接矩阵A：

A = 

    0 1 0 0 0 
    0 0 1 0 0 
    1 0 0 1 0 
    0 0 0 0 0 
    0 0 0 1 0 

，我们希望从节点x看看是否有任何路径（不循环，还）到节点z通过节点y。行x告诉我们哪些节点的边缘从x到y，并且列z告诉我们哪些节点的边缘从y到z。如果我们执行行x的元素明智AND和列z，我们应该得到连接到x和z的所有节点y的向量。

例如，如果我们AND行1并为此邻接矩阵列3：

A = 

    0 1 0 0 0 
    x x 1 x x 
    x x 0 x x 
    x x 0 x x 
    x x 0 x x 

>> A(1,:) & A(:,3).' %// remember to transpose the column first... 
ans = 

    0 1 0 0 0 

我们看到，他们通过节点2连接。太棒了，现在我们知道，对于这种情况，我们有一个路径1->2->3。一般来说，从1到3可能有多条路径，所以我们要使用整个向量。

现在我们所要做的就是确保从节点3到节点1有一条路径。那么，我们的邻接矩阵中的行3，列1。如果我们ANDA(3,1)与我们的向量，我们应该回到相同的向量，如果有从3到1的边缘，并且如果没有（并因此没有循环）则返回零。

>> (A(1,:) & A(:,3).') & A(3,1) 
ans = 

    0 1 0 0 0 

归纳这一点，从x到z每个路径矢量是

C(x,:,z) = (A(x,:) & A(:,z).') & A(z,x); 

不幸的是我一直无法找到一个方法来矢量化这一点，所以双for循环将有足够的现在：

for x = 1:size(A,1) 
    for z = 1:size(A,2) 
     C(x,:,z) = (A(x,:) & A(:,z).') & A(z,x); 
    end 
end 

所得矩阵将具有C(x,y,z) = 1如果存在来自一个周期至y至z（和返回）以及0。请注意，每个周期将列出3次：

C(x,y,z) == C(y,z,x) == C(z,x,y)