Prolog help needed.

Write a PROLOG program that does a topological sort.

Problem:

Topological sort of a partial order, which is a list of ordered pairs [left, right] which you can think of as meaning left<=right. The predicate to define is my_topo_sort(Partial_order, Total_order).

For example, we might have [[left_sock, left_shoe], [right_sock, right_shoe]] to describe the constraints on the order in which to get dressed.

A topological sort of a partial order then produces a total order, which is a linearization consistent with the partial order. For the example above,

[left_sock, left_shoe, right_sock, right_shoe] and [left_sock, right_sock, left_shoe, right_shoe] would both be acceptable linearizations.

To code a topological sort in PROLOG we can use "negation as failure" so that if we cannot prove two elements in the list to be topologically sorted are out of order, we can assume they are not out of order (the closed-world assumption). That allows us to say an element of a list is the max if we can't prove it's not the max.

For the example above, first make a list of all the elements in all the constraints: [left_sock, left_shoe, right_sock, right_shoe]. Then eliminate duplicates (if any). Next sort as in problem 1 but with my_max finding an element M which you can't prove is not the maximum (i.e., you can't prove there is a constraint [M, M2] in the list of constraints, which would mean M2 >= M and M would not be guaranteed to be the maximum).

So to test the program we then do:

?-my_topo_sort([[left_sock, left_shoe], [right_sock, right_shoe]], TotalOrder). 

Which should output: TotalOrder = [left_sock, left_shoe, right_sock, right_shoe].