python - 使用相对位置数据对列表进行排序

Question

这更像是一个概念性编程问题，请耐心等待:

假设您有一个电影场景列表，每个场景可能会也可能不会引用同一部电影中的过去/ future 场景。我正在尝试找到对这些场景进行排序的最有效算法。当然，可能没有足够的信息来完全排序场景。

这里有一些 Python 示例代码(几乎是伪代码)来阐明:

class Reference:
    def __init__(self, scene_id, relation):
        self.scene_id = scene_id
        self.relation = relation


class Scene:
    def __init__(self, scene_id, references):
        self.id = scene_id
        self.references = references

    def __repr__(self):
        return self.id


def relative_sort(scenes):
    return scenes # Algorithm in question


def main():
    s1 = Scene('s1', [
        Reference('s3', 'after')
    ])
    s2 = Scene('s2', [
        Reference('s1', 'before'),
        Reference('s4', 'after')
    ])
    s3 = Scene('s3', [
        Reference('s4', 'after')
    ])
    s4 = Scene('s4', [
        Reference('s2', 'before')
    ])

    print relative_sort([s1, s2, s3, s4])


if __name__ == '__main__':
    main()

在这种情况下，目标是让 relative_sort 返回 [s4, s3, s2, s1]。

如果有帮助，我可以分享我对算法的初步尝试；我对它的蛮力程度感到有点尴尬。另外，如果您想知道，我正在尝试解读电影“穆赫兰道”的情节。

仅供引用:Python 标记只在这里是因为我的伪代码是用 Python 编写的。

Answer 1

您要查找的算法是 topological sort :

In the field of computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks.

您可以使用图形库非常轻松地进行计算，例如 networkx，它实现了 topological_sort .首先我们导入库并列出场景之间的所有关系——即图中所有有向边

>>> import networkx as nx
>>> relations = [
    (3, 1),  # 1 after 3
    (2, 1),  # 2 before 1
    (4, 2),  # 2 after 4
    (4, 3),  # 3 after 4
    (4, 2)   # 4 before 2
]

然后我们创建一个有向图:

>>> g = nx.DiGraph(relations)

然后我们运行拓扑排序:

>>> nx.topological_sort(g)
[4, 3, 2, 1]