Sorting strings with “before” and “after” constraints

Question

I'm trying to solve a constraint-satisfaction problem for a project of mine that seems like it should have a well-known solution, but I can't for the life of me seem to find it described anywhere.

I've been poring over what literature I can find about CSP's and none of the general stuff seems to be clicking. I feel like maybe my CS chops just aren't quite up to the task, so feel free to point me to some tutorial that will make me feel stupid for even asking this, if such a thing exists.

What I'm looking to do is this:

Given a list of unique strings, where each string may have either, both, or neither of the following constraints associated with it:

• before, which references another string in the list, and ensures that this string occurs before that one in the final sorting.
• after, which also references another string in the list, and ensures that this string occurs after that one in the final sorting.

Sort the strings in a way that can guarantee satisfaction of all constraints.

Something like this:

• 'bar', no constraints
• 'foo', before 'bar'
• 'baz', no constraints
• 'qux', after 'baz'
• 'quux' before 'baz', after 'foo'

Will result in a final sort like this:

• 'foo'
• 'bar'
• 'quux'
• 'baz'
• 'qux'

Though it isn't a hard requirement, I would prefer the result be deterministic. There are several alternate answers to the problem above, as 'bar' has no constraints besides being after 'foo'. Of course, I don't really care which one I get back as long as the algorithm reliably produces the same result each time.

I wouldn't be surprised to learn that such determinism is impossible since it seems to be one of the biggest reasons I keep running into blocks, but I've thus far been unable to prove to myself that it can't be done.

Of course, I'll also need to be able to detect sets of constraints that are impossible to satisfy-- such as this one:

• 'foo', no constraints
• 'bar', after 'foo'
• 'baz', after 'bar', before 'foo'

In cases like this I don't need any kind of answer. I just need to detect it so I can throw an exception.

So far may natural inclination has been to bust out a genetic algorithm, but that of course kills the determinism and would be wasteful if there is a better solution that just requires me to know what the heck I'm doing, lol. So I want to see if I can rule out that possibility before proceeding.

Thanks ahead of time!