# Sorting Algorithm with constraints

I am looking for a sorting algorithm to help me in my work. My objective is the following: after receiving an input of this kind:

5 4
1 2
2 3
3 4
4 5


The first line tells me how many ids I have, and the second number tells me how many connections. The following lines tell me the connections, and tell me that the first Id comes before the second one, for example: 1 comes before 2, 2 comes before 3, and so on. And if an impossible situation occurs:

3 2
1 2
2 3
3 1


or

2 2
1 2
2 1


I want to be able to send an error message.

Or even when there is not enough information to have a conclusive sorting:

4 4
1 2
3 1
3 4
4 2


Is there an algorithm that already does this? or can u give me some guide lines to how to start my work? The sorting part is not hard, but the impossible/insuficient info cases is what I am struggling to implement.

• This is topological sorting. I'm reluctant to write a full answer, since it's well-documented elsewhere. – KWillets Mar 21 '17 at 17:55
• I'm also not going to write a full answer, but I will give this link: en.wikipedia.org/wiki/… – Pseudonym Mar 22 '17 at 1:11

In other words, you are given a directed graph, and you want to know:

1. Whether there are any directed cycles, i.e., whether your graph is a DAG.

2. Assuming there are no directed cycles, whether the corresponding partial order is a linear order.

As KWillets comments, this is just topological ordering. In your case, to find whether your digraph is a DAG supporting a unique topological ordering, try the following algorithm:

1. Verify that there is a unique source (a node with no incoming edges).

2. Remove the unique source, and repeat.

This succeeds iff your digraph is a DAG which has a unique topological ordering.