Patrick Patrick - 1 month ago 16
Python Question

Sorting a List with Relative Positional Data

This is more of a conceptual programming question, so bear with me:

Say you have a list of scenes in a movie, and each scene may or may not make reference to past/future scenes in the same movie. I'm trying to find the most efficient algorithm of sorting these scenes. There may not be enough information for the scenes to be completely sorted, of course.

Here's some sample code in Python (pretty much pseudocode) to clarify:

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()


The goal is to have
relative_sort
return
[s4, s3, s2, s1]
in this case.

If it's helpful, I can share my initial attempt at the algorithm; I'm a little embarrassed at how brute-force it is. Also, if you're wondering, I'm trying to decode the plot of the film "Mulholland Drive".

FYI: The Python tag is only here because my pseudocode was written in Python.

jme jme
Answer

The algorithm you are looking for is a 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.

You can compute this pretty easily using a graph library, for instance, networkx, which implements topological_sort. First we import the library and list all of the relationships between scenes -- that is, all of the directed edges in the graph

>>> 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
]

We then create a directed graph:

>>> g = nx.DiGraph(relations)

Then we run a topological sort:

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