title: Encoding directed graph as numbers
body: <p>Let's say that I have a directed graph, with a single root and without cycles. I would like to add a type on each node (for example as an integer with some custom ordering) with the following property:</p>
  
  <pre><code>if Node1.type &lt;= Node2.type then there exists a path from Node1 to Node2
  </code></pre>
  
  <p>Note that topological sorting actually satisfies the reversed property:</p>
  
  <pre><code>if there exists a path from Node1 to Node2 then Node1.type &lt;= Node2.type
  </code></pre>
  
  <p>so it cannot be used here. </p>
  
  <p>Now note that integers with natural ordering cannot be used here because every 2 integers can be compared, i.e. the ordering of integers is linear while the tree does not have to be.</p>
  
  <p>So here's an example. Assume that the graph has 4 nodes <code>A, B, C, D</code> and 4 arrows:</p>
  
  <pre><code>A-&gt;B, A-&gt;C, B-&gt;D, C-&gt;D
  </code></pre>
  
  <p>So it's a diamond. Now we can put</p>
  
  <pre><code>A.type = 00
  B.type = 01
  C.type = 10
  D.type = 11
  </code></pre>
  
  <p>where on the right side we have integers in binary format. The comparison is defined bitwise:</p>
  
  <pre><code>(X &lt;= Y) if and only if (n-th bit of X &lt;= n-th bit of Y for all n)
  </code></pre>
  
  <p>So I guess such ordering could be used, the question is how to construct values from a given graph? I'm not even sure if the solution always exists. Any hints?</p>
  
  <p><strong>UPDATE:</strong> Since there is some misunderstanding about terminology I'm using let me be more explicite: I'm interested in directed acyclic graph such that there is exactly one node without predecessors (a.k.a. the root) and there's at most one arrow between any two nodes. The diamond would be an example. It <strong>does not</strong> have to have one leaf (i.e. the node without successors). Each node might have multiple predecessors and multiple successors. You might say that this is a partially ordered set with a smallest element (i.e. a unique globally minimal element).</p>