title: Sorting a List with Relative Positional Data
body: <p>This is more of a conceptual programming question, so bear with me:</p>
  
  <p>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.</p>
  
  <p>Here's some sample code in Python (pretty much pseudocode) to clarify:</p>
  
  <pre><code>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()
  </code></pre>
  
  <p>The goal is to have <code>relative_sort</code> return <code>[s4, s3, s2, s1]</code> in this case.</p>
  
  <p>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".</p>
  
  <p>FYI: The Python tag is only here because my pseudocode was written in Python.</p>