4
$\begingroup$

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.

Thanks in advance for your time.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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