序列化有向加权图

Question

我是一名有用的助手，可以为您进行文本翻译。以下是需要翻译的内容：

我有一个有向带权图。每个节点都表示为一个2元组，其第一个元素是节点的名称，第二个元素是包含从该节点发出的所有顶点的元组，按其权重排序。基本上，每个顶点的权重都是它在此元组中的索引。

例如：

a = ('A', () )

a是一个没有任何边从其出发的节点，其名称为A。

b = ('B', () )
a = ('A', (b,) )

a 是一个名为 A 的节点，与名为 B 的节点连接有一条边，权重为 0。

b = ('B', () )
c = ('C', () )
a = ('A', (b, c) )

a是一个名为A的节点，它有两个顶点连接到名为B和C的节点，第一个顶点的权重为0，第二个顶点的权重为1。

很明显，('A', (b, c) )不等于('A', (c, b) )。

现在我需要根据以下规则对此图进行序列化：

1. 结果的第一个元素是起始节点。
2. 然后按升序顺序跟随所有直接从起始节点访问的节点的权重。如果节点已经在结果中，则不要再次添加它。
3. 现在将规则一和规则二递归地应用于刚刚添加的所有元素。

基本上，先按权重从低到高排序，然后按深度排序。

这里是一个示例输入和输出：

f = ('F', () )
e = ('E', () )
d = ('D', (e,) )
c = ('C', (f, d, e) )
b = ('B', (d,) )
a = ('A', (b, c) )

结果为：

['A', 'B', 'C', 'D', 'F', 'E']

现在我的第一个幼稚的方法是这样的：

def serialize (node):
    acc = []

    def serializeRec (node, level):
        tbd = [] #acc items to be deleted
        tbi = False #insertion index
        for idx, item in enumerate (acc):
            if item [1] > level and tbi == False:
                tbi = idx
            if item [0] == node [0]:
                if item [1] > level: tbd.append (item)
                else: break
        else:
            if tbi == False: acc.append ( (node [0], level) )
            else: acc.insert (tbi, (node [0], level) )
        for item in tbd:
            acc.remove (item)
        for vertex in node [1]:
            serializeRec (vertex, level + 1)

    serializeRec (node, 0)
    #remove levels
    return [node for node, level in acc]

显然这是一个非常糟糕的想法，因为在每次递归中我都要遍历各种列表。这就是为什么我转而使用字典的原因：

def serializeDict (node):
    levels = defaultdict (list) #nodes on each level
    nodes = {} #on which level is which node

    def serializeRec (node, level):
        try:
            curLevel = nodes [node [0] ]
            if curLevel > level:
                nodes [node [0] ] = level
                levels [curLevel].remove (node [0] )
                levels [level].append (node [0] )
        except:
            nodes [node [0] ] = level
            levels [level].append (node [0] )
        for vertex in node [1]:
            serializeRec (vertex, level + 1)

    serializeRec (node, 0)
    #flatten dict items
    return [node for level in (v for _, v in sorted (levels.items (), key = lambda x: x [0] ) ) for node in level]

除了非常小的图形外，它运行得更快。

我的问题是：

我如何优化此序列化以最小化运行时间？

内存使用不受关注（耶，宝贝），KLOC不受关注，只有运行时间计数。可以更改所有内容，但输入数据的格式不能更改。但如果最终可以节省时间，我将很乐意重新组织此序列化函数中的数据。

非常感谢您阅读这篇 TL;DR 的文字墙。

---

用于嬉闹的示例图表：

z = ('Z', () ); y = ('Y', (z,) ); x = ('X', (z, y) ); w = ('W', (x, y, z) ); v = ('V', (w, x) ); u = ('U', (w, v) ); t = ('T', (u, w) ); s = ('S', (z, v, u) ); r = ('R', (t, u, z) ); q = ('Q', (r, z) ); p = ('P', (w, u) ); o = ('O', (v, r, q) ); n = ('N', (r, z) ); m = ('M', (t,) ); l = ('L', (r,) ); k = ('K', (x, v) ); j = ('J', (u,) ); i = ('I', (n, k) ); h = ('H', (k, x) ); g = ('G', (l,) ); f = ('F', (t, m) ); e = ('E', (u,) ); d = ('D', (t, e, v) ); c = ('C', (m,) ); b = ('B', (n,) ); a = ('A', (g, m, v) )

- Hyperboreus

---

只是一个想法。先尝试进行拓扑排序（O（V + E）），然后运行非递归算法对它们进行序列化。 - evhen14

@evhen14 谢谢，我会研究一下。 - Hyperboreus

Answer 1

这个方法不使用递归，使用双端队列以提高效率：

from collections import deque

def serialize_plain(n):
    name, children = n
    output = [name]

    candidates = deque(children)
    while candidates:
        cname, cchildren = candidates.popleft()
        if cname not in output:
            output.append(cname)
            candidates.extend(cchildren)

    return output

根据您的图表大小，保留已经处理过的节点集可能是有意义的，以避免昂贵的列表查询：

from collections import deque

def serialize_with_set(n):
    name, children = n
    output = [name]
    done = {name}

    candidates = deque(children)
    while candidates:
        cname, cchildren = candidates.popleft()
        if cname not in done:
            output.append(cname)
            done.add(cname)
            candidates.extend(cchildren)

    return output

- Stephan Wenger

---

非常感谢。我会仔细研究你的答案。 - Hyperboreus

Answer 2

现在我需要根据以下规则对此图进行序列化： 结果的第一个元素是起始节点。 然后按升序权重顺序跟随所有直接从起始节点访问的节点。如果节点已经在结果中，则不要再附加它。 现在将规则一和规则二递归地应用于刚刚添加的所有元素。

我想补充一点，从理论上讲，这是遍历图的一种非常常见的方式，称为广度优先遍历，并且要求对邻居列表进行排序。正如第一个答案中提到的那样，通常使用队列来避免递归。

如果您的项目允许使用自己尊重的图书馆，您应该能够在其中找到广度优先遍历。例如，这个应该很快，因为它基于出色的C++ boost::graph，这是C++世界中的事实标准图书馆。

- DCS