时间戳

首页 > 解决方案 > 将（邻接）矩阵的列和行排序为上三角

python - 将（邻接）矩阵的列和行排序为上三角

问题描述

对于有向图，我有一个约束，即邻接矩阵A应该是具有 0 对角线的上三角形（断言非循环条件）。现在假设我任意排列了节点的顺序，这样新的邻接矩阵B就不再是上三角矩阵了。我想要的是从中恢复A三角矩阵B。我可以将矩阵作为numpy.array对象pandas.DataFrame，因此我正在这些库中寻找解决方案。

到目前为止，我的解决方案如下：

  1. 我们知道有一个节点没有父节点（一个全零列）所以我找到它，将它存储在一个数组中，并从其他节点中删除连接
  2. 我对所有节点重复，直到我制作节点的有序列表。

这是代码：

def sort_nodes(adj_matrix: np.ndarray = None):
    ordered_list = []
    covered_nodes = 0
    while covered_nodes < adj_matrix.shape[0]:
        # sum of the columns
        sum_c = adj_matrix.sum(axis=0)
        # find nodes with no parents: sum should be zero
        parent_inds = list(np.where(sum_c == 0)[0])

        # an assertion to make sure the matrix can be sorted triangular
        assert len(parent_inds) != 0
        
        # update the while condition
        covered_nodes += len(parent_inds)
        # add to the list
        ordered_list += parent_inds

        # remove parent edges by set the corresponding row to zero
        adj_matrix[parent_inds, :] = 0
        # eliminate from columns by assigning values so that its sum cannot be zero
        adj_matrix[:, parent_inds] = 10
    return ordered_list

有什么解决办法吗？一个函数或更简洁的算法。我还触及了图形库的表面，networkx但一无所获……干杯！

编辑：1

此类问题的一个示例是：

A:
   1  2  3  4
1[[0, 1, 1, 1]
2 [0, 0, 1, 1]
3 [0, 0, 0, 1]
4 [0, 0, 0, 0]]

B:
   2  1  4  3
2[[0, 0, 1, 1]
1 [1, 0, 1, 1]
4 [0, 0, 0, 0]
3 [0, 0, 1, 0]]

其中 A 是完整的顺序 DAG。（在非循环条件允许的情况下完全连接）

标签： pythonpandasnumpydirected-acyclic-graphsadjacency-matrix

解决方案

为了使我的pandas解决方案能够正常工作，请将一列全为 1 的列添加到数据框中（以避免全零行）：

df = pd.DataFrame([[0,1,1,0],[0,0,0,1],[0,0,1,1],[0,0,0,0]])
df.loc[:, df.shape[1]] = 1

现在您可以找到每一行中最左边的 1 的索引。索引越小，原始非置换矩阵中的行就越高。最后，按该位置对行进行排序并删除最后一列 1：

df = df.reindex(df.idxmax(1) - 1).iloc[:,:-1]
#   0  1  2  3
#0  0  1  1  0
#2  0  0  1  1
#1  0  0  0  1
#3  0  0  0  0

推荐阅读