Encoding directed graph as numbers

Question

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:

if Node1.type <= Node2.type then there exists a path from Node1 to Node2

Note that topological sorting actually satisfies the reversed property:

if there exists a path from Node1 to Node2 then Node1.type <= Node2.type

so it cannot be used here.

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.

So here's an example. Assume that the graph has 4 nodes A, B, C, D and 4 arrows:

A->B, A->C, B->D, C->D

So it's a diamond. Now we can put

A.type = 00
B.type = 01
C.type = 10
D.type = 11

where on the right side we have integers in binary format. The comparison is defined bitwise:

(X <= Y) if and only if (n-th bit of X <= n-th bit of Y for all n)

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?

UPDATE: 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 does not 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).

Answer 1

You call the relation <=, but it's necessarily not complete (that is: it may be that for a given pair a and b, neither a <= b nor b <= a).

Here's one idea for how to define it.

If your nodes are numbered 0, 1..., N-1, then you can define type like this:

type(i) = (1 << i) + sum(1 << (N + j), for j such that Path(i, j))

And define <= like this:

type1 <= type2 if (type1 >> N) & type2 != 0

That is, type(i) encodes the value of i in the lowest N bits, and the set of all reachable nodes in the highest N bits. The <= relation looks for the target node in the encoded set of reachable nodes.

This definition works whether or not there's cycles in the graph, and in fact just encodes an arbitrary relation on your set of nodes.

You could make the definition a little more efficient by using ceil(log2(N)) bits to encode the node number (for a total of N + ceil(log2(N)) bits per type).