title: How to efficiently construct a dependency graph from a transitive pairwise relation?
body: <p>The following algorithm is necessary in a code generation problem that I am tackling. My current algorithm is O(n^2) but I feel like there is a better way to do it.</p>
  
  <p>Suppose I have a predicate function for computing whether x &lt; y.</p>
  
  <pre><code>less?: (x:T, y:T) -&gt; True|False
  </code></pre>
  
  <p>I know a-priori that this relation is transitive. Such that,</p>
  
  <pre><code>less?(a, b) and less?(b, c)
  </code></pre>
  
  <p>implies</p>
  
  <pre><code>less?(a, c)
  </code></pre>
  
  <p>I would like to compute the dependency graph for a set of objects (x1, ..., xn). It should look like:</p>
  
  <pre><code>x1 =&gt; (x2, x4, x5)
  x2 =&gt; (x3)
  x5 =&gt; (x7)
  x10 =&gt; ()
  etc...
  </code></pre>
  
  <p>where each node, xi, is associated with a list of xj such that less?(xj, xi) is true. The easiest way to compute this graph is to call less? on all possible pairs of (xi, xj). But the less? relation is expensive and I would like to minimize the calls to less?</p>
  
  <p>Thanks for your help.</p>
  
  <p>-Patrick</p>