有向无环图的特定拓扑排序

Question

有向无环图的拓扑顺序不是唯一的但要取决于传出边的遍历顺序。

我需要特定的遍历顺序。所以功能topological_order_depth_first调用函数sort_algorithm应该做些什么-但我很难确定应该做些什么（我肯定知道我需要拓扑顺序，并且首先需要深度）。

代码

# Source for the algorithm: https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search
def topological_order_depth_first(nodes, descendants):
    result = []
    remaining = list(nodes)
    permanent = set()
    temporary = set()

    def visit(n):
        if n in permanent: return
        if n in temporary: raise Exception('Cycle.')

        temporary.add(n)

        children = list(descendants[n])
        while any(children):
            # sorting them every loop step instead of just once
            # because the sorting order might depend on those previously added
            # because a shared node has been added.
            # If it turns out that's not needed can still move it out of the loop.
            children = sort_algorithm(descendants, children)
            m = children.pop()
            visit(m)

        temporary.remove(n)
        permanent.add(n)

        result.append(n) # should actually prepend, but doing append, so need to reverse later.

    while any(remaining):
        # sorting them every loop step instead of just once
        # because the sorting order might depend on those previously added
        # because a shared node has been added.
        # If it turns out that's not needed can still move it out of the loop.
        remaining = sort_algorithm(descendants, remaining)
        n = remaining.pop()
        visit(n)

    result.reverse() # nodes need to be prepended to result, but I appended, so need to reverse.

    return result

def sort_algorithm(descendants, current):
    # TODO: this should do something.
    return current

我尝试计算出传出的边缘，包括递归所有孩子特别对待那些有多个传入节点的孩子，但没有什么能满足我的需求。

1。主要示例

例如，考虑以下图形：

    _1___
   / | \ \
  2  4  6 |
 / \/ \/  8
3  5  7   |
 \_|_/___/
   9

我希望它产生拓扑顺序

    [1, 2, 3, 4, 5, 6, 7, 8, 9]

与节点和边的传递顺序无关。

此算法调用产生了预期的结果：

print(topological_sort_depth_first(
    [1, 2, 3, 4, 5, 6, 7, 8, 9], # nodes
    { # edges
    1: [2, 4, 6, 8],
    2: [3, 5],
    4: [5, 7],
    6: [7],
    3: [9],
    5: [9],
    7: [9],
    8: [9],
    9: []
    }))

此，更改边的输入顺序，不会：

print(topological_order_depth_first(
    [1, 4, 3, 6, 5, 2, 7, 8, 9], # nodes
    { # edges
    1: [2, 4, 6, 8],
    2: [3, 5],
    4: [5, 7],
    6: [7],
    3: [9],
    5: [9],
    7: [9],
    8: [9],
    9: []
    }))

相反，它产生订单

    [1, 4, 6, 2, 3, 5, 7, 8, 9]

（节点名称的选择仅出于说明目的。进行词法排序不是解决方案。）

其他示例

2。简单树

此节点的行为正确，与节点的顺序无关（2和3可能以两种顺序出现，因为无法分辨）：

  1
 / \
2   3

print(topological_order_depth_first(
    [1, 2, 3], # nodes
    { # edges
    1: [2, 3],
    2: [],
    3: []
    }))

3。钻石

菱形的行为相同（2和3的顺序无关紧要：]

  1
 / \
2   3
 \ /
  4

print(topological_order_depth_first(
    [1, 2, 3, 4], # nodes
    { # edges
    1: [2, 3],
    2: [4],
    3: [4],
    4: []
    }))

    [1, 2, 3, 4]

4。双钻

双菱形的行为根据节点的顺序而有所不同：

  1
 / \
4   2
 \ / \
  5   3
   \ /
    6

这将产生正确的拓扑顺序（在我想要的意义上为“正确”-当然，没有客观地将任何顺序选为另一个）：

print(topological_order_depth_first(
    [1, 2, 3, 4, 5, 6], # nodes
    { # edges
    1: [2, 4],
    2: [3, 5],
    3: [6],
    4: [5],
    5: [6],
    6: []
    }))

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

这将产生错误的一个：

print(topological_order_depth_first(
    [1, 3, 4, 5, 6, 2], # nodes
    { # edges
    1: [2, 4],
    2: [3, 5],
    3: [6],
    4: [5],
    5: [6],
    6: []
    }))

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

5。不快乐的树木

[还有一些树木表现不理想：

     1
   /   \
  2     6
 / \   / \
3   5 7   8
|         |
4         9

print(topological_order_depth_first(
    [1, 2, 3, 4, 5, 6, 7, 8, 9], # nodes
    { # edges
    1: [2, 6],
    2: [3, 5],
    3: [4],
    4: [],
    5: [],
    6: [7, 8],
    7: [],
    8: [9],
    9: []
    }))

产生奇怪的事物

    [1, 2, 3, 4, 5, 6, 7, 8, 9]

我希望以下之一

    [1, 2, 3, 4, 5, 6, 8, 9, 7]
    [1, 2, 5, 3, 4, 6, 7, 8, 9]
    [1, 6, 8, 9, 7, 2, 3, 4, 5]
    [1, 6, 7, 8, 9, 2, 5, 3, 4]

因此，我正在计算后代的数量，因此我可以总是选择最大或最小的子树-但这仅适用于树，不适用于弱连接图。

---

根据要求提供更多示例。

（也：交叉发布到StackExchange: Computer Science。]

Answer 1

我一直在玩这个游戏，并且我认为有一些可行的方法，但是我不是100％肯定的。

基本思想是识别在特定技术意义上彼此“等效”的节点组。然后，我们可以用一个数字标记每个节点，其中等效节点具有相同的数字。那时，您就可以运行DFS，通过始终按降序访问孩子来决胜局。直觉是，具有相同编号的任何两个节点都具有相同的形状和相对位置，因此，如果您任意打破联系，则它位于两个相同的子图之间，并且不会被注意到/无关紧要。

为此，我们将对要查找的内容进行递归定义，然后讨论如何找到它。我们需要的基本概念是一个节点具有在其“上方”的节点（所有边缘都在我们节点内的节点）和在其“下方”的节点（我们的节点具有其边缘的所有节点）的思想。我们想要的属性如下：

[且只有当u和v上方的节点具有相同的数字且u和v下方的节点具有相同的数字时，两个节点u和v才会获得相同的数字。

因此，例如，没有出站边缘的节点无法获得与有出站边缘的节点相同的编号。

问题是如何分配这些数字。这里的想法是将其分为两个单独的通道。首先，我们仅基于DAG中下方的节点对节点进行编号。这是执行此操作的简单算法，效率不高，可能还有待改进。

• 标识所有没有输出边缘的节点。将它们标记为“第0层”，并将其从DAG中删除。为每个数字分配零。
• 虽然DAG中还有节点：
  • 查找没有外向边缘的所有节点并将它们标记为当前层。
  • 用数字的排序列表注释每个节点，其中每个数字表示DAG中紧接在其下的节点的编号。
  • 使用一些可预测的顺序（例如，按字典顺序）对这些列表进行排序，以标识重复项。然后，为这些节点分配从上次中断处开始的顺序号。

这将对节点编号，当且仅当以这些节点为根的子DAG同构时，两个节点才会获得相同的编号。

我们可以运行此算法的第二遍，而不是自下而上，自上而下地操作，根据每个节点上方出现的子DAG为每个节点分配第二个数字。

从那里开始，每个节点都有两个数字，我们可以以一致的方式对这些对进行排序，并为每个节点分配一个代表其类型的新最终数字。

我正在电话上键入此字符，在这里很难进行ASCII艺术（没有等宽字体，叹气），所以当我下次在计算机上时，我可以键入一些示例，以便您可以看到它的外观喜欢。

希望这会有所帮助！