Algorithm to establish ordering amongst a set of items

Question

I have a set of students (referred to as items in the title for generality). Amongst these students, some have a reputation for being rambunctious. We are told about a set of hate relationships of the form 'i hates j'. 'i hates j' does not imply 'j hates i'. We are supposed to arrange the students in rows (front most row numbered 1) in a way such that if 'i hates j' then i should be put in a row that is strictly lesser numbered than that of j (in other words: in some row that is in front of j's row) so that i doesn't throw anything at j (Turning back is not allowed). What would be an efficient algorithm to find the minimum number of rows needed (each row need not have the same number of students)?

We will make the following assumptions:

1) If we model this as a directed graph, there are no cycles in the graph. The most basic cycle would be: if 'i hates j' is true, 'j hates i' is false. Because otherwise, I think the ordering would become impossible.

2) Every student in the group is at least hated by one other student OR at least hates one other student. Of course, there would be students who are both hated by some and who in turn hate other students. This means that there are no stray students who don't form part of the graph.

Update: I have already thought of constructing a directed graph with i --> j if 'i hates j and doing topological sorting. However, since the general topological sort would suit better if I had to line all the students in a single line. Since there is a variation of the rows here, I am trying to figure out how to factor in the change into topological sort so it gives me what I want.

When you answer, please state the complexity of your solution. If anybody is giving code and you don't mind the language, then I'd prefer Java but of course any other language is just as fine.

JFYI This is not for any kind of homework (I am not a student btw :)).

Answer 1

It sounds to me that you need to investigate topological sorting.

Answer 2

Essentailly the important thing in assumption #1 is that there must not be any cycles in this graph. If there are any cycles you can't solve this problem.

I would start by seating all of the students that do not hate any other students in the back row. Then you can seat the students who hate these students in the next row and etc.

Answer 3

Simple answer = 1 row.

Put all students in the same row.

Actually that might not solve the question as stated - lesser row, rather than equal row...

1. Put all students in row 1
2. For each hate relation, put the not-hating student in a row behind the hating student
3. Iterate till you have no activity, or iterate Num(relation) times.

But I'm sure there are better algorithms - look at acyclic graphs.

Answer 4

This problem is basically another way to put the longest path in a directed graph problem. The number of rows is actually number of nodes in path (number of edges + 1).

Assuming the graph is acyclic, the solution is topological sort. Acyclic is a bit stronger the your assumption 1. Not only A -> B and B -> A is invalid. Also A -> B, B -> C, C -> A and any cycle of any length.

HINT: the question is how many rows are needed, not which student in which row. The answer to the question is the length of the longest path.

Answer 5

It's from a project management theory (or scheduling theory, I don't know the exact term). There the task is about sorting jobs (vertex is a job, arc is a job order relationship).

Obviously we have some connected oriented graph without loops. There is an arc from vertex a to vertex b if and only if a hates b. Let's assume there is a source (without incoming arcs) and destination (without outgoing arcs) vertex. If that is not the case, just add imaginary ones. Now we want to find length of a longest path from source to destination (it will be number of rows - 1, but mind the imaginary verteces).

We will define vertex rank (r[v]) as number of arcs in a longest path between source and this vertex v. Obviously we want to know r[destination]. Algorithm for finding rank:

0) r_0[v] := 0  for all verteces v
repeat
t) r_t[end(j)] := max( r_{t-1}[end(j)], r_{t-1}[start(j)] + 1 )  for all arcs j
until for all arcs j r_{t+1}[end(j)] = r_t[end(j)]    // i.e. no changes on this iteration

On each step at least one vertex increases its rank. Therefore in this form complexity is O(n^3).

By the way, this algorithm also gives you student distribution among rows. Just group students by their respective ranks.

Edit: Another code with the same idea. Possibly it is better understandable.

# Python
# V is a list of vertex indices, let it be something like V = range(N)
# source has index 0, destination has index N-1
# E is a list of edges, i.e. tuples of the form (start vertex, end vertex)
R = [0] * len(V)
do:
    changes = False
    for e in E:
     if R[e[1]] < R[e[0]] + 1:
      changes = True
      R[e[1]] = R[e[0]] + 1
while changes
# The answer is derived from value of R[N-1]

Of course this is the simplest implementation. It can be optimized, and time estimate can be better.

Edit2: obvious optimization - update only verteces adjacent to those that were updated on the previous step. I.e. introduce a queue with verteces whose rank was updated. Also for edge storing one should use adjacency lists. With such optimization complexity would be O(N^2). Indeed, each vertex may appear in the queue at most rank times. But vertex rank never exceeds N - number of verteces. Therefore total number of algorithm steps will not exceed O(N^2).

Answer 6

The number of rows is the length of the longest path in the directed graph, plus one. As a limit case, if there is no hate relationship everyone can fit on the same row.

To allocate the rows, put everyone who is not hated by anyone else on the row one. These are the "roots" of your graph. Everyone else is put on row N + 1 if N is the length of the longest path from any of the roots to that person (this path is of length one at least).

A simple O(N^3) algorithm is the following:

S = set of students
for s in S: s.row = -1        # initialize row field
rownum = 0                    # start from first row below
flag = true                   # when to finish
while (flag):
  rownum = rownum + 1         # proceed to next row
  flag = false
  for s in S:
    if (s.row != -1) continue # already allocated
    ok = true
    foreach q in S:
      # Check if there is student q who will sit
      # on this or later row who hates s
      if ((q.row == -1 or q.row = rownum)
          and s hated by q) ok = false; break
    if (ok):                  # can put s here
      s.row = rownum
      flag = true