Given a set of relationships, what is the most efficient algorithm to calculate the ordered set

Question

   c > b
   d > b
   a > d
   c > a

Given such transitive relationships, what is the most efficient algorithm to calculate the relation between all of them?

Answer 1

Build a graph, and use topological sort to retrieve the nodes in sorted order.

If you use am adjacency list representation and a hash map for the vertices of your graph, the overall timing will be O(N), where N is the number of relationships that you have. Building the graph is linear in the number of relationships that you have. The topological sort is O(|V|+|E|), where |V| is the number of vertices, and |E| is the number of edges. The number of edges is equal to the number of relationships, i.e. N, and V has the upper bound of 2*N, so it we have O(3*N), which is O(N).

Answer 2

What you are actually describing in your case is a topological sort problem: http://en.wikipedia.org/wiki/Topological_sorting

Where instead of a graph, you have orderings of letters. Each letter represents a node and each comparison operator represents a directed edge. The standard algorithm for computing the topological sort of a pairwise orderings is as follows:

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
    remove a node n from S
    add n to tail of L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least one cycle)
else 
    return L (a topologically sorted order)

Keep in mind that for you to find an ordering, there can be no cycles. i.e.:

a < b //This
b < c //contains
c < a //a cycle!

This is called a DAG. Directed acyclic graph. See: http://en.wikipedia.org/wiki/Directed_acyclic_graph

Here is an example of how to do it in Python: Topological sort python