Efficient coding of labeled directed acyclic graphs

被引：7

作者：

Steinsky, B ^{[1
]}

机构：

[1] Salzburg Univ, Inst Psychol, A-5020 Salzburg, Austria

来源：

SOFT COMPUTING | 2003年 / 7卷 / 05期

关键词：

directed acyclic graph (DAG); Bayesian network; enumeration; rank; generation;

D O I：

10.1007/s00500-002-0223-5

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

We use an adaptation of the Prufer code for trees to encode labeled directed acyclic graphs, which are often abbreviated to DAGs (or ADGs). In this paper, each DAG is assigned a unique DAG code, which allows an easy handling for several purposes. The set of all possible DAG codes (and therefore the set of all DAGs) for a fixed number of n vertices can be generated efficiently. Furthermore, we are able to rank DAGs, i.e., we provide an algorithm that assigns every DAG a unique number in the set {0, . . . , a(n) - 1}, where a(n) is the cardinality of the set of labeled DAGs with n greater than or equal to 1 vertices, and we are able to unrank DAGs, which is the inverse operation. We also gain recurrence relations, which can be used to calculate a(n) and a(n,q), i.e., the number of DAGs with n vertices and q edges. Finally, it is possible to generate, enumerate, rank and unrank DAGs with given number of edges and also DAGs with bounded indegree.

引用

页码：350 / 356

页数：7