Unranking paths in a graph/lattice

Question

A ranking algorithm determines the position (or rank) of a combinatorial object among all the objects (with respect to a given order); an unranking algorithm finds the object having a specified rank. Thus, ranking and unranking can be considered as inverse operations.

The following lattice has 9 unique max length paths from {} to {1,2,3,4,5}, which can be obtained by a depth first search.

(The graph is directed, with arrows pointing down)

Is it possible to write a function that generates the N'th path without enumerating paths 1..N-1.

see: https://math.stackexchange.com/questions/510911/computing-all-simple-paths-in-a-distributive-lattice-in-parallel for more problem details.

Answer 1

Suppose without loss of generality that there is one source $\emptyset$ and one sink $S$. For each node $v$ in your digraph, you can compute recursively the number $N_v$ of unique maximum length paths from $\emptyset$ to $v$: at $\emptyset$ we have $N_\emptyset = 1$, and at other points, $N_v = \sum_u N_u$, where the sum goes over all immediate predecessors of $u$.

This suggests the following encoding for maximal paths at a node $v$. Suppose the immediate predecessors of $v$ are $u_1,\ldots,u_k$, in some arbitrary but fixed order. We will encode all paths as numbers in the range $[0,N_v)$ ($=\{0,\ldots,N_v-1\}$) in the following way: all paths through $u_1$ will be encoded in $[0,N_{u_1})$, all paths through $u_2$ will be encoded in $[N_{u_1},N_{u_1}+N_{u_2})$, and so on. Inside each interval, we apply the same encoding scheme recursively. By applying this scheme for $v = S$ (the sink), we get an efficient encoding system for all maximal paths.