Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Forgive me if this is too imprecise a question. My math-fu is weak, I'm just a humble programmer.

I'm looking for an algorithm to sort a list of items based on a partial order: each item has a list of other items that it must be before, and a list of items it must be after. I can produce from this a list of directed edges, $A > B$. However, many pairs will have no given order, while others will only have an implied order (ie $A > B$ and $B > C$ implies $A > C$, but neither $A$ nor $C$ specify this).

What I want to get from this is a single ordered list containing all the inputs once, that satisfies all conditions. There will often be many possible solutions for a given set of inputs, but I don't need to find them all or a definitive "best" order (if that even has a meaning).

Preferably the algorithm will be:

  • Stable under small changes, so the resulting sorted list doesn't change wildly when an input changes. This will make the code easier to debug should one of the orders need changing.
  • Linear time or near
  • Functional more than procedural (but not tied to a single programming language)
  • Clear enough to get my head round

No item may appear more than once in the inputs. It is of course possible for the inputs to be invalid, ie for the graph of directed edges to be cyclical. In this case it would be best to spot the error and report it accurately to aid debugging.

share|improve this question

1 Answer 1

up vote 5 down vote accepted

I believe that your question may be solved by topological sorting.

share|improve this answer
    
That looks right, right. The article isn't clear on the performance/scaling difference between the two algorithms. The first is easier to understand, and I have a rough version of it coded now. Which would you recommend? –  Marcus Downing Aug 6 '11 at 1:13
    
I don't know. In an asymptotic sense, I'm pretty sure both are linear. If you're asking about real-world performance, this would be highly dependent on your exact implementation and the nature of your inputs. Also, the presentation of topological sort in Wikipedia is not the greatest so you might benefit from searching alternate sources. –  mhum Aug 6 '11 at 16:01
    
Thanks. The nature of my inputs is that the known edges for a given node are largely localised and low in number, so the total number of edges is roughly proportional to the number of nodes. I believe the Kuhn algorithm should at least approximate to linear. –  Marcus Downing Aug 6 '11 at 23:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.