Ranking, unranking and random generation of extensional acyclic digraphs

Extensional acyclic digraphs are acyclic digraphs whose vertices have pairwise different sets of out-neighbors; they represent hereditarily finite sets, which stand at the basis of some computer languages. In this paper we give an O(n3)O(n3) algorithm for generating uniformly at random an extensional acyclic digraph on n   vertices. This is done by first proposing a linear-time algorithm for encoding such digraphs by particular (n−1)(n−1)-tuples of subsets of {0,…,n−2}{0,…,n−2}. We then give a new counting recurrence for such tuples, which we exploit in ranking/unranking algorithms. These are also useful for indexing data structures by hereditarily finite sets.

► Extensional acyclic digraphs can be directly generated uniformly at random in cubic time. ► We first propose a linear-time algorithm for encoding such digraphs by particular set systems. ► We give a new counting recursion for such set systems. ► We then exploit this in ranking/unranking algorithms These are also useful for indexing data structures by hereditarily finite sets.