在Python中将无向循环图（UCG）转换为有向无环图（DAG）的最快方法？

Question

假设我有一个无向循环图（UCG）。所有边的权重均为1。因此，该UCG可由邻接矩阵A表示：

import numpy as np

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

为了可视化UCG，我们可以通过

import networkx as nx

ucg = nx.Graph()
rows, cols = np.where(A == 1)
edges = zip(rows.tolist(), cols.tolist())
ucg.add_edges_from(edges)

UCG看起来像这样：

我用不同的颜色给节点着色，以显示“最小距离”。橙色节点{8, 9, 10}是起始节点，绿色节点{0, 1, 2, 3}是到起始节点的最小距离为1的节点，蓝色节点{4, 5, 6, 7}的最小距离为2。现在我想把它转换成一个有向无环图（DAG），箭头从起始节点指向距离-1节点到距离-2节点，依此类推。具有相同“最小距离”的节点之间的边将被丢弃

预期输出是表示DAG的字典：

d = {8: {1, 3},
     9: {1, 2},
     10: {0, 2, 3},
     0: {4, 6, 7},
     1: {5, 6, 7},
     2: {4, 5, 6},
     3: {4, 5, 7}}

类似地，为了可视化DAG，我们可以通过

dag = nx.DiGraph()
dag.add_edges_from([(k, v) for k, vs in d.items() in for v in vs])

预期输出DAG如下所示：

我想编写一个高效的通用代码，将具有给定起始节点的给定UCG转换为相应的DAG

我尝试过的

显然，需要递归。我的想法是使用BFS方法找到每个起始节点的1-距离节点，然后是它们的1-距离节点，然后递归继续。所有访问的节点都存储在一个集合prev_starts中，以避免向后移动。下面是我的代码

from collections import defaultdict

def ucg2dag(A, starts):
    """Takes the adjacency matrix of a UCG and the indices of the
    starting nodes, returns the dictionary of a DAG."""

    def recur(starts):
        starts = list(set(starts))
        idxs, nbrs = np.where(A[starts] == 1)
        prev_starts.update(starts)

        # Filter out the neighbors that are previous starts so the
        # arrows do not point backwards
        try:
            idxs, nbrs = zip(*((idx, nbr) for idx, nbr in zip(idxs, nbrs)
                                if nbr not in prev_starts))
        # Terminate if every neighbor is a previous start.
        except:
            return d

        for idx, nbr in zip(idxs, nbrs):
            d[starts[idx]].add(nbr)

        return recur(starts=nbrs)

    prev_starts = set()
    d = defaultdict(set)
    return recur(starts)

测试我的代码：

d = ucg2dag(A, starts={8, 9, 10})
print(d)

编辑：由于@trincot的评论，在recur之前添加了return之后，我能够获得正确的输出：

defaultdict(<class 'set'>, 
            {8: {1, 3}, 
             9: {1, 2}, 
             10: {0, 2, 3}, 
             0: {4, 6, 7}, 
             1: {5, 6, 7}, 
             2: {4, 5, 6}, 
             3: {4, 5, 7}})
%timeit 37.6 µs ± 591 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

实际上，我有一个更大的图表。我想知道是否有更有效的算法

Answer 1

您已经对代码应用了一些修复（部分基于注释），因此现在您的代码可以正常工作了

剩下的几句话是：

• BFS通常不是递归算法（与DFS相反）：您的递归是尾部递归。在这种情况下，可以将其写入循环，这样可以避免使用堆栈

• 很遗憾，您必须在邻接矩阵中查找边。最好先将邻接矩阵转换为邻接列表，除非图形非常密集

• 输出也可以是一个邻接列表，每个节点都有一个条目，这样就可以是列表列表而不是字典

• 使用zip重复转换结构可能不是最有效的（尽管我没有进行基准测试）

如果不使用numpy，它可能会如下所示：

def ucg2dag(adj_matrix, starts):
    adj_list = [
        [target for target, is_connected in enumerate(row) if is_connected]
            for row in adj_matrix
    ]

    frontier = starts

    dag = [[] for _ in range(len(adj_list))]

    while frontier:
        for source in frontier:
            dag[source].extend(target for target in adj_list[source] if not target in starts)
        frontier = set(target 
            for source in frontier for target in adj_list[source] if not target in starts
        )
        starts.update(frontier)

    return dag

运行示例：

adj_matrix = [[0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1],
              [1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0],
              [1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1],
              [1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1],
              [1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0],
              [0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0],
              [1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0],
              [1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0],
              [0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0],
              [0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
              [1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0]]

dag = ucg2dag(adj_matrix, {8, 9, 10})
print(dag)  

示例运行的输出：

[[4, 6, 7], [5, 6, 7], [4, 5, 6], [4, 5, 7], [], [], [], [], [1, 3], [1, 2], [0, 2, 3]]