Question: I have an array of pairs like this:

```
[["a", "b"], ["b", "d"], ["a", "c"], ["e", "d"], ["a", "d"], ..., ["s", "f"]]

```

1. What is an efficient way to check if the given array can express a partial ordering? That is, there is no "loop" in the given array like `["a", "b"], ["b", "c"], ["c", "a"]`.
2. If it is confirmed that the array expresses a partial order, I want to normalize this by removing all of the pairs that can be derived by reflexivity or transitivity. For example, in the above, since there is `["a", "b"]` and `["b", "d"]`, the pair `["a", "d"]` is redundant, and should be removed.

The order between 1 and 2 does not matter. If 2 should be done before or within the process of 1, then, that is fine.

Preferably I want it in Ruby 1.9.3, but just pseudo-code will suffice.

Answer: 
**For number 1:**

You can **module your problem as a [graph](http://en.wikipedia.org/wiki/Graph_%28mathematics%29)**, and each pair will be an edge, next you can **run a [topological sort](http://en.wikipedia.org/wiki/Topological_sorting)** - if the algorithm fails, the graph is not a [DAG](http://en.wikipedia.org/wiki/Directed_acyclic_graph) - and there is a "loop" - otherwise - you get a possible partial order, as the output of the topological sort.

**For number2:**

I am not sure regarding this part at all, so this answer is only partial actually, sorry about it - but just a priliminary thaught:

You can use a [DFS](http://en.wikipedia.org/wiki/Depth-first_search), and remove edges from "already discovered" vertices to "just discovered vertices" [on the same path]. Though I don't think it is optimal, but prehaps doing it iteratively [until no changes were made] will improve it.

**Deeper thaught for number2:**

I am not sure what you mean here, but a forest created by DFS fulfill your request, however I am afraid you might lose too much data using it, for instance: `["a","b"],["a","c"],["b",d"],["c","d"]` will trim one of `["b","d"]` OR `["c","d"]`, which might be too much, but it will also trim all the "redundant" edges, as described in the example.
For the first part of the question, I came up with my own answer [here](https://stackoverflow.com/questions/9728910) with the help of an answer at a mathematics site.

For the second part of the question, after following the suggestions given in the other answers, I implemented in Ruby (i) [Floyd-Warshall algorithm](http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm) to calculate the transitive closure, (ii) composition, and (iii) transitive reduction using the formula R^- = R - R \cdot R^+.

```
module Digraph; module_function
    def vertices graph; graph.flatten(1).uniq end
    ## Floyd-Warshall algorithm
    def transitive_closure graph
        vs = vertices(graph)
        path = graph.inject({}){|path, e| path[e] = true; path}
        vs.each{|k| vs.each{|i| vs.each{|j| path[[i, j]] ||= true if path[[i, k]] && path[[k, j]]}}}
        path.keys
    end
    def compose graph1, graph2
        vs = (vertices(graph1) + vertices(graph2)).uniq
        path1 = graph1.inject({}){|path, e| path[e] = true; path}
        path2 = graph2.inject({}){|path, e| path[e] = true; path}
        path = {}
        vs.each{|k| vs.each{|i| vs.each{|j| path[[i, j]] ||= true if path1[[i, k]] && path2[[k, j]]}}}
        path.keys
    end
    def transitive_reduction graph
            graph - compose(graph, transitive_closure(graph))
    end
end

```

Usage examples:

```
Digraph.transitive_closure([[1, 2], [2, 3], [3, 4]])
#=> [[1, 2], [2, 3], [3, 4], [1, 3], [1, 4], [2, 4]]

Digraph.compose([[1, 2], [2, 3]], [[2, 4], [3, 5]])
#=> [[1, 4], [2, 5]]

Digraph.transitive_reduction([[1, 2], [2, 3], [3, 4], [1, 3], [1, 4], [2, 4]])
#=> [[1, 2], [2, 3], [3, 4]]

```