TCS -TR-A-14-75

TCS Technical Report

An Eﬃcient Method of Indexing All TopologicalOrders for a Given DAG
byYuma Inoue and Shin-ichi Minato

Division of Computer Science
Report Series A
July 17, 2014

Hokkaido University
Graduate School ofInformation Science and Technology
Email:

minato@ist.hokudai.ac.jp

Phone:+81-011-706-7682

Fax:+81-011-706-7682

An Eﬃcient Method of Indexing All Topological Orders
for a Given DAG
Yuma Inoue

Shin-ichi Minato∗

Division of Computer Science
Graduate School of Info. Sci. and Tech.
Hokkaido University
Sapporo 060-0814, Japan

Division of Computer Science
Graduate School of Info. Sci. and Tech.
Hokkaido University
Sapporo 060-0814, Japan

July 17, 2014

Abstract
Topological orders of a directed graph are an important concept of graphalgorithms. The generation of topological orders is useful for designing graphalgorithms and solving scheduling problems. In this paper, we generate andindex all topological orders of a given graph. Since topological orders are permutations of vertices, we can use the data structure πDD, which generates andindexes a set of permutations. In this paper, we propose Rot-πDDs, which area variation of πDDs based on a diﬀerent interpretation. Compression ratiosof Rot-πDDs for representing topological orders are theoretically improved
from the original πDDs. We propose an eﬃcient method for constructing a
Rot-πDD based on dynamic programming approach. Computational experiments show the amazing eﬃciencies of a Rot-πDD: a Rot-πDD for 3.7 × 1041
topological orders has only 2.2 × 107 nodes and is constructed in 36 seconds.
In addition, the indexed structure of a Rot-πDD allows us to fast post-process
such as edge addition and random samplings.

1

Introduction

Topological sort is one of the classical and important concepts of graph algorithms.
Vertex orders obtained by topological sort are used to analyze characteristics ofa directed graph structure and support graph based algorithms [6]. Furthermore,
topological orders are equivalent to linear extensions of a poset, i.e., total orders
which are in no contradiction with the partially ordered set defined by directededges of a graph. Thus, topological sort plays an important role in several research areas such as discrete mathematics and computer science, and has many
applications such as graph problems and scheduling problems [14].
∗He also works for JST ERATO Minato Project.

1

2

Yuma Inoue and Shin-ichi Minato

Linear time algorithms calculating a topological order are classical and wellknown algorithms, and dealt with by Cormen et al. [6]. In recent researches,
two derived problems are mainly discussed. One of these is an online topologicalsort, i.e., calculation of a topological order on a dynamic graph. Bender et al. [2]proposed a topological sort algorithm which allows edge insertions, and Pearce etal. [13] proposed an algorithm which can also handle edge deletions. Another one
is the enumeration problem of all topological orders. Ono et al. [12] presented
a worst case constant delay time generating algorithm using family trees. The
complexity of the counting problem has been studied from several aspects since
Brightwell et al. [3] proved that it is #P -complete. Bubley et al. [4] proposed arandomized algorithm to approximate the number of all linear extensions. Li etal. [10] provided an experimentally fast algorithm counting all topological orders
based on Divide & Conquer method. There are many polynomial time counting
algorithms when we restrict the graph structure or fix some graph parameters, e.g.,trees and bounded poset width [1, 5].
In this paper, we deal with both of these problems. That is, our goal is generation of all topological orders of given graphs and manipulation of these orders
when the graph is dynamically changed, e.g., edge addition. In addition, we implicitly store all topological orders as a compressed data structure in order to handle
graphs that are as large as possible. Experimental results, which will be describedlater, show that our algorithm and data structure work very well: 3.7 × 1041 topological orders of a directed graph with 50 vertices are generated in 36 seconds, andthe compressed data size is only about 1 gigabyte. Furthermore, an edge addition
query for a directed graph with 25 vertices is done in 1 second.
Our method is based on an indexed data structure compactly representing a
set of permutations, permutation decision diagram, also called πDD or PiDD [11].
Although a πDD can be used to achieve our purpose, compression ratio and query
processing are not eﬃcient enough practically or theoretically. Thus, we developed
a new variation of πDD, named Rot-πDD (Rotation-based πDD). The key ideaof our modification is a direct construction of a decision diagram based on the
dynamic programming approach. This modification realizes the practical eﬃciency
of compression and query processing, which are also bounded theoretically.
Our contributions in this paper are summarized as follows.
• We provide the first algorithm for implicit generation of all topological orders
with dynamic manipulation.
• Time and space for construction and query processing of our algorithm are
eﬃcient experimentally and theoretically, while it is diﬃcult to estimate thesize and computation time of decision diagrams in general.
The rest of this paper is organized as follows. Section 2 introduces a precise
definition of topological sort and algorithms for counting, which will be used in ouralgorithm. Section 3 introduces πDDs and our modified version (Rot-πDDs) forAn Eﬃcient Method of Indexing All Topological Orders for a Given DAG
(a)

5

2

(b)

1

5

3

6
4

2

3

6
1

3

4

Figure 1: (a) A DAG and (b) the subgraph induced by the vertex set {2, 5, 6}.

generation of all topological orders. Our algorithm for construction of a Rot-πDD isalso presented in Section 3. In Section 4, we prove the theoretical bound of the timecomplexity of our algorithm and the size of the new permutation decision diagram
for all topological orders. Section 5 presents experimental results of generationand query processing, comparing with existing πDD and other existing methods.
Section 6 gives some consequences of this paper.

2

Topological Orders

We define a directed graph G = (V, E), where V is a vertex set and E is a directededge, i.e., E ⊆ {(u, v) | u, v ∈ V }. Note that (u, v) is an ordered pair of two
vertices. Let n be the number of vertices and m be the number of edges. Without
loss of generality, we can assume V = {1, 2, . . . , n}.
A topological order of a graph G is an ordering v1 v2 . . . vn of all vertices suchthat vi must precede vj if (vi , vj ) ∈ E. For example, the graph in Fig. 1(a) has
four topological orders: 526413, 526431, 562413, and 562431.
A directed graph is a DAG (Directed Acyclic Graph) if the graph has no cycle.
In this paper, we assume that given graphs are DAGs because we can determine
whether or not a graph has cycles in linear time, and if so, there is no topologicalorder.
There are many linear time algorithms for computing a topological order of agiven graph [9, 15]. One of the key ideas is deleting vertices whose out-degree is 0.
If there is no edge from v, v can be the rightmost element in a topological order,
because there is no element that must be preceded by v. We delete such v andits incident edges, i.e., after the deletion of v, we can consider only the subgraphinduced by the vertex subset V \ {v}. Then, we repeat the same procedure forthe induced subgraph and obtain a topological order of the induced subgraphrecursively. Finally, we concatenate a topological order of the induced subgraphand v to obtain a topological order of the given graph. The time complexity ofthis algorithm is O(n + m).
Similarly, an algorithm counting all topological orders of a given graph can be
designed recursively. Let G(X) denote the subgraph of G induced by the vertex
subset X. For each recursion, we assume that the current vertex subset is V ′ .
Then, for each vertex v whose out-degree is 0 in G(V ′ ), we sum up the numbersof all topological orders of G(V ′ \ {v}). The time complexity of this algorithm is

4Yuma Inoue and Shin-ichi Minato

O((n + m)T O(G)), where T O(G) is the number of the topological orders of thegraph G. Since T O(G) = O(n!), the time complexity is O((n + m)n!). We can
improve this complexity by a dynamic programming (DP ) approach.
For example, in Fig. 1(a), we can delete vertices {1, 3, 4} in the order 134 or 314.
(Note that a deletion order is the reverse of a topological order.) Then we obtainthe same induced subgraph on {2, 5, 6}. Although T O(G({2, 5, 6})) is not changed,
we redundantly count T O(G({2, 5, 6})) in each recursion of 134 and 314. Thus,by memorizing the calculation result T O(G(V ′ )) for G(V ′ ) at the first calculation,
we can avoid duplicated calculations for each G(V ′ ). In other words, this is a∑
top-down DP, which recursively calculates T O(G(V ′ )) = v∈V ′ T O(G(V ′ \ {v})),0where V0′ is the set of vertices whose out-degree is 0 in G(V ′ ). We define valid
induced subgraphs of G as induced subgraphs G(V ′ ) that can appear in the above
DP recursion. Let IS(G) denote the number of valid induced subgraphs of G.
Then, this DP algorithm uses O((n + m)IS(G)) time and O(IS(G)) space. In theworst case, IS(G) = 2n , which is the number of all subsets of V . Therefore, we
improve the complexity from factorial O((n + m)n!) to exponential O((n + m)2n ).
The idea of valid induced subgraphs is equivalent to upsets in a poset in the
talk of Cooper [5]. Cooper provided another upper bound O(nw ) of IS(G), where
w is the width of a poset corresponding to G. The proof of this bound and more
precise analyses will be described in Section 4.
Here, we remember our goal in this paper again. Our goal is generating andindexing all topological orders, which are permutations of vertices. Thus, it is reasonable to expect that a compressed and indexed data structure for permutations
can be useful for this purpose. And if we can compress permutations in the same
way as the above DP, the compression size is bounded by IS(G) = O(min{2n , nw }),which can be quite smaller than T O(G).

3Permutation Decision Diagrams

In this section, we introduce a compressed and indexed data structure for permutations, πDD, and discuss whether or not compression of a πDD is suitable for the
DP approach.

3.1

Existing Permutation Decision Diagrams: πDDsFirst, we define some notations about permutations. A permutation of length n,or n-permutation, is a numerical sequence π = π1 π2 . . . πn such that all elements
are distinct and πi ∈ {1, 2, . . . , n} for each i. The identity permutation of lengthn is denoted by en , which satisfies eni = i for each 1 ≤ i ≤ n.
We define a swap τi,j as the exchange of the ith element and the jth element.
Any n-permutation can be uniquely decomposed into a sequence of at most n − 1
swaps. This swap sequence is defined as the series of swaps to obtain an objective

5

An Eﬃcient Method of Indexing All Topological Orders for a Given DAG
τ1,6

0

1

τ3,6

τ3,5
τ1,5

τx,y

τ2,3

1

τx,y

0

τx,y

1

0

0

1

P0

τ2,3

0

P0

τ1,2
0

τx,y

τ1,3

1

Figure 2: The πDD representing{526413, 526431, 562413, 562431}.

P1P0(1) merging ruleP1

P0(2) deletion ruleFigure 3: Two reduction rules ofπDDs.

n-permutation π from the identity permutation en by a certain algorithm. The
algorithm repeats swaps to move πk to the kth position, where k runs from rightto left. For example, we consider a decomposition of the permutation π = 43152
into a swap sequence. We start with e5 = 12345. The 5th element of π is 2 and2 is the 2nd element of en , hence we swap the 2nd element and the 5th element,
and obtain 15342 = τ2,5 . Next, since the 4th element of π is 5, and 5 is the 2nd
element, we then obtain 14352 = τ2,5 · τ2,4 . Repeating this procedure, we finallyobtain π = 43152 = τ2,5 · τ2,4 · τ1,3 · τ1,2 .
A πDD is a data structure representing a set of permutations canonically [11],and has eﬃcient set operations for permutation sets. πDDs consist of five components: nodes with a swap label, 0-edges, 1-edges, the 0-sink, and the 1-sink. Fig. 2
shows the πDD representing topological orders of the graph in Fig. 1(a).
Each internal node has exactly a 0-edge and a 1-edge. Each path in a πDD
represents a permutation: if a 1-edge originates from a node with label τx,y , thedecomposition of the permutation contains τx,y , while a 0-edge from τx,y meansthat the decomposition excludes τx,y . If a path reaches the 1-sink, the permutation
corresponding to the path is in the set represented by the πDD. On the other hand,
if a path reaches the 0-sink, the permutation is not in the set.
A πDD becomes a compact and canonical form by applying the following two
reduction rules (Fig. 3):(1) Merging rule: share all nodes which have the same labels and child nodes.
(2) Deletion rule: delete all nodes whose 1-edge points to the 0-sink.
Although the size of a πDD (i.e. the number of nodes in a πDD) can grow2
exponentially (O(2n )) with respect to the length of permutations, in many practical cases, πDDs demonstrate high compression ratio. In addition, πDDs support
eﬃcient set operations such as union, intersection, and set diﬀerence. The computation time of πDD operations depends on the size of πDDs, not on the number of
permutations in the sets represented by the πDDs.

6

Yuma Inoue and Shin-ichi Minato
0

ρ3,6

ρ1,6 1
ρ2,5

ρ1,5
ρ2,4
ρ1,3
ρ1,2
0

1

Figure 4: The Rot-πDD representing {526413, 526431, 562413, 562431}.

3.2

DP Approach and πDDs

Now, we consider whether or not we can directly construct a πDD in the same way
as the DP approach described in Section 2.
Here, we note that the swap decomposition algorithm behaves as deletions ofa vertex on an induced subgraph. We can represent the current recursive state in
DP procedure as a permutation, i.e., let k be the number of vertices of the current
induced subgraph, then the k-prefix of an n-permutation represents the vertex setof the induced subgraph, and the (n − k)-suﬃx of the permutation represents thereverse order of deletions. Furthermore, a deletion of a vertex v can be described
as a swap τi,k , where i is the position of v in the permutation. For example, we
can consider a permutation 625431 represents the subgraph in Fig. 1(b) such thatthe deletion order is 134. When we delete the vertex 6, we swap the 1st position,
which is 6, and the 3rd position, which is the rightmost of the k-prefix representing
the vertex subset. Then, we obtain 526431, which represents the subgraph inducedby {2, 5} and the reverse order of deletions.
By compressing swap sequences into a πDD, we can recursively construct a πDD
for all topological orders. That is, for each recursion represented as a permutation
π, if we apply τi,j to delete πi , we create the new πDD such that its root nodeis τi,j , its 1-edge child is the πDD for swap sequences after applying τi,j , and its
0-edge child is the πDD for swap sequences in which we do not apply τi,j . The
πDDs for the 1-edge and 0-edge child are recursively constructed.
However, deletions by swaps are not available for DP. In order to use DP approach, swap sequences for the same induced subgraph must be uniquely determined. Even if diﬀerent prefixes of permutations represent the same induced subgraph, their swap sequences can diﬀer. For example, consider the DAG in Fig. 1.
Deletion sequences 314 and 134 generate the same induced subgraph on {2, 5, 6},
and these states are represented as 526413 and 625431, respectively. The induced
subgraph on {2, 5, 6} has a topological order 526. In order to obtain this, we apply
no swap to 526413, while we apply τ1,3 to 625431. This means there are multiple
πDDs corresponding to the same induced subgraph.

An Eﬃcient Method of Indexing All Topological Orders for a Given DAG

7Algorithm 1 Rot-πDD construction for all topological orders of G = (V, E).
ConstructRotP iDD(G):if V is empty thenreturn 1-sinkelse if have never memorized the Rot-πDD RG for G thenRot-PiDD R ← 0-sink
for each v whose out-degree is 0 in G do
Integer i ← v’s position in the increasing sequence of V , j ← |V |R ← the Rot-PiDD with root node ρi,j , left child R, and right child
ConstructRotP iDD(G(V \ {v}))end formemorize R as RG
end ifreturn RG

3.3

New Permutation Decision Diagrams: Rot-πDDs

As described in the previous subsection, the DP approach cannot be used to directly construct a πDD. To overcome this problem, we use another decomposition
where each vertex subset is uniquely represented as a prefix of permutations. In order to realize this, we use the left-rotation decomposition. A left-rotation ρi,j rearranges ith element into jth position, and kth element into (k−1)th position for eachi + 1 ≤ k ≤ j. That is, ρi,j rearranges an n-permutation π1 . . . πi πi+1 . . . πj . . . πninto π1 . . . πi+1 . . . πj πi . . . πn .
Left-rotations also can uniquely decompose a permutation. The left-rotation
decomposition is similar to the one for swaps: we start with en and repeatedly
apply ρi,j to move πi to the jth position, from right to left. For example, consider
to decompose 43152 into a sequence of left-rotations. We start with e5 = 12345.
Now, we move 2 from the 2nd position to the 5th position. Thus, we obtain
13452 = ρ2,5 . Next, we move 5 from the 4th position to the 4th position, i.e., we
do not rotate. Repeating this procedure, we finally obtain 43152 = ρ2,5 · ρ1,3 · ρ1,2 .
Left-rotations realize the unique representation of an induced subgraph as aprefix of a permutation, because a prefix is always in an increasing order. Leftrotation ρi,j only changes the relative order between the ith element and the elements in [i + 1, j], i.e., relative orders in [1, j − 1] are not changed. This means the(j − 1)-prefix is always in increasing order when we start with en and apply ρi,j indecreasing order of j.
Thus, we can use the DP approach by using left-rotations as node labels of
πDDs. We call this left-rotation based πDD Rot-πDD, and existing πDD SwapπDD to distinguish. Fig. 4 illustrates the Rot-πDD for the same set as Fig. 2.
Algorithm 1 describes the DP based construction algorithm of a Rot-πDD.

8

3.4

Yuma Inoue and Shin-ichi Minato

Rot-πDD operations

Since Rot-πDDs are decision diagrams, they can use the same set operations as
Swap-πDD such as union, intersection, and set diﬀerence. Some queries such as
random samplings and counting the cardinality of the set represented by a RotπDD are also available without any modification. On the other hand, some queries
have to be redesigned. For example, the precedence query R.P recede(u, v) returns
the Rot-πDD that represents only permutations π extracted from the Rot-πDD R
such that u precedes v in π. This query is equivalent to addition of the edge (u, v)
in a graph. This query can be designed as a recursive procedure (we omit details),
and the runtime depends on only the size of the Rot-πDDs.

4

Theoretical Analysis

In this section, we analyze the time and the space complexity of DP based counting
and Rot-πDD construction. Here, we remember the definition of IS(G): IS(G)is the number of the induced subgraphs of G that can be obtained by deletionsof vertices with out-degree 0. We start by proving the bound O(nw ) of IS(G).
According to Dilworth’s theorem [7], the width w of a poset equals the minimum
path cover of the DAG corresponding to the poset, where a path cover of a graph
G is a set of paths in G such that each vertex of G must appear in at least one ofthe paths. Therefore, it is suﬃcient to prove the following theorem.
Theorem 1. Given a DAG G with n vertices and minimum path cover w, IS(G) ≤(n + 1)w holds.
Proof. Let pi be the ith path of the minimum path cover and li be the length of pi .
Here, all vertices in a valid induced subgraph must be consecutive in prefix of eachpi due to precedence. The number of the possible prefixes of each path is at most∏li + 1, and the number of paths is w. Therefore, IS(G) is bounded by w
k=1 (lk + 1).
w
Since li is also bounded by n, IS(G) ≤ (n + 1) holds.
∑
In this proof, we use the rough estimation li = n, but in fact w
k=1 lk = n holds.
We can prove a tighter bound using this restriction.
∑∏w
w
Lemma 2. If w
k=1 lk = n holds,
k=1 (lk + 1) ≤ (n/w + 1) holds for all positive
integers n, 1 ≤ w ≤ n, and 1 ≤ li ≤ n.
Proof. The proof is by induction. We prove it in the Appendix.
Corollary 3. Given a DAG G with n vertices and minimum path cover w, IS(G) ≤(n/w + 1)w holds.
Proof. The proof follows from the proof of Theorem 1 and Lemma 2.

An Eﬃcient Method of Indexing All Topological Orders for a Given DAG

9Corollary 3 gives a new bound of IS(G). Since (n/w + 1)w is monotonicallynondecreasing for all positive integers n and w, the range of (n/w +1)w is [n+1, 2n ]for 1 ≤ w ≤ n. This means the previous bound O(min{2n , nw }) can be directly
replaced by O((n/w+1)w ). Hence, we obtain the time complexity O((n+m)(n/w+
1)w ) and the space complexity O((n/w + 1)w ) of the DP.
We can also estimate the size of a Rot-πDD representing all topological orders
and the time of the construction. The size of such a Rot-πDD is at most w times
larger than the space of DP because each DP recursion has at most w transitions,while each node of a Rot-πDD has exactly two edges. Therefore, the size of sucha Rot-πDD is at most O(w(n/w + 1)w ). 1 On the other hand, the time of theconstruction is as fast as DP, because each node is only created for each vertex
deletion in constant time. Hence, the time complexity of the construction of a
Rot-πDD representing all topological orders is O((n + m)(n/w + 1)w ).

5

Computational Experiments

We measured the performance of our Rot-πDD construction algorithm by computational experiments. Experiment setting is as follows.
• Input: A DAG.
• Output: The number of topological orders of the given DAG.
• Test Cases: For each n = 5, 10, 15, . . . , 45, 50 and k = 1, 3, 5, 7, 9, we generatekexactly 30 random DAGs with n vertices and ⌊ 10
× n(n−1)⌋ edges. (That is,
2
k provides the edge density of DAGs.)
We also compared with other methods on the same setting. Comparisons are
Swap-πDD construction, DP counting, and Divide & Conquer counting [10]. Since
direct construction of a Swap-πDD is ineﬃcient, we apply precedence queries foreach edge individually. We implemented all algorithms in C++ and carried out
experiments on a 3.20 GHz CPU machine with 64 GB memory.
Fig. 5 and Fig. 6 show the average runtime and memory usage on n = 20 cases.
Divide & Conquer method times-out on some cases of k = 1. These results indicatethat the worse cases of all algorithms are sparse graphs. In general, sparse graphs
tend to have a large poset width. In fact, the average w of k = 1 cases is 10.6,
while that of k = 5 cases is 3.3. Therefore, the complexity O((n/w + 1)w ) also
tends to become large on the sparse graph cases.
We therefore focus on sparse graphs. Table 1 shows the average numbers of
topological orders, the sizes of Rot-πDDs, and runtimes on the case k = 1. It shows
the amazing eﬃciency of Rot-πDDs: 3.7 × 1041 topological orders are compressed1

Note that this bound is valid only for all topological orders. For any permutation set, the2worst size of Rot-πDDs is O(2n ), which is same as the size bound of Swap-πDDs.

10Yuma Inoue and Shin-ichi Minato
100

memory usage (kB)10
runtime (sec)107

Rot-πDD
Swap-πDDDP
Divide&Conquer

1
0.1
0.01

Rot-πDD
Swap-πDDDP
Divide&Conquer

106

105

104

0.001
0.0001

1

2

3

4

5
k

6

7

8

9

Figure 5: Average runtime for construction when n = 20.

103

1

2

3

4

5
k

6

7

8

9

Figure 6: Average memory usage forconstruction when n = 20.

Table 1: Experimental results on the cases k = 1.
n
The number of topological orders Rot-πDD size Time (sec)
5
60
16
0.00
10
270816310
0.00
153849848730
3990
0.00
20
84248623806362
35551
0.04
25
1729821793136903967
1792050.18
30166022551499377802024339
6950290.90
3518897260805585874040859189398
2634015
3.78
40
192246224377065271125689349980187
46496396.68
457506858927008084384591070452622456252
8288752
12.69
50 375636607794991518114274279559952431497225
22542071
35.51

into a Rot-πDD that has only 2.2 × 107 nodes in 36 seconds on the case n = 50.
Note that each node of Rot-πDDs consumes about 30 bytes.
Fig. 7 and Fig. 8 show the average runtime and memory usage on k = 1 cases.
Swap-πDD and Divide & Conquer time-out on the case n ≥ 25 and n ≥ 20, respectively. We can obtain a Rot-πDD, which supports many operations for queries,
with only tenfold increase in runtime and memory usage compared to DP. We guessthat the overhead time is used to store new nodes of a Rot-πDD into the hash table, and the overhead memory is caused by the diﬀerence of the space complexities
between DP and Rot-πDD as described in Section 4.
We also carried out experiments to measure the performance of query processing. On these experiments, we use 30 random DAGs with 25 vertices and 90 edges.
We start with a graph having no edge, and add each edge individually. The RotπDD method uses precedence queries for each edge addition, while DP recomputes
T C(G) for each addition. We measure the runtime and the size of a Rot-πDD anda DP table. Note that the DP table size equals IS(G).

11

An Eﬃcient Method of Indexing All Topological Orders for a Given DAG

107

100
memory usage (kB)runtime (sec)

10
1
0.1
0.01
0.001
0.0001

5

10

15

20

Rot-πDD
Swap-πDDDP
Divide&Conquer
25 30 35 40n45

Rot-πDDDP

runtime (sec)

10
1
0.1
0.01
0.001
0.00010

10

20 30 40 50 60 70
the number of added edges

80

90

Figure 9: Average runtime for edge
addition queries.

104

5

10

15

20

Rot-πDD
Swap-πDDDP
Divide&Conquer
25 30 35 40
n

45

50

Figure 8: Average memory usage forconstruction when k = 1.
the size of Rot-PiDD / DP table

100

105

103

50

Figure 7: Average runtime for construction when k = 1.

106

108

Rot-πDD
DP

107
106
105
104
103
102

0

10

20 30 40 50 60 70
the number of added edges

80

90

Figure 10: Average space for edge addition queries.

Fig. 9 and Fig. 10 show the results for query processing. In almost all cases,
Rot-πDDs can generate and index all topological orders faster than or equal to DP.
Especially in sparse cases, query processing of Rot-πDDs is very eﬃcient. It may be
because Rot-πDDs (and Swap-πDDs) can represent the set of all n-permutations
with n(n − 1)/2 + 1 nodes (please refer to [8] for more details).

6

Conclusion

In this paper, we gave an eﬃcient method for generating and indexing all topological orders of a given DAG. We proposed a new data structure Rot-πDD, which
is suitable for indexing topological orders. Theoretical analysis and experiments
showed the eﬃciency of our construction algorithm, compression ratios of RotπDDs, and query processing.
Future work is to apply Rot-πDDs to solve several scheduling problems. We
would like to develop new operations to process required queries and optimizations
for each problem. Another topic is to apply the Rot-πDD construction technique toother graph generation problems such as Hamiltonian paths and perfect elimination
orderings. These problems can also be recursively divided into subproblems basedon induced subgraphs.

12

Yuma Inoue and Shin-ichi Minato

References[1] Mike D Atkinson. On computing the number of linear extensions of a tree.
Order, 7(1):23–25, 1990.
[2] Michael A Bender, Jeremy T Fineman, and Seth Gilbert. A new approach
to incremental topological ordering. In 20th Annual ACM-SIAM Symposium
on Discrete Algorithms (SODA), pages 1108–1115. Society for Industrial andApplied Mathematics, 2009.
[3] Graham Brightwell and Peter Winkler. Counting linear extensions. Order,
8(3):225–242, 1991.
[4] Russ Bubley and Martin Dyer. Faster random generation of linear extensions.
Discrete Mathematics, 201(1):81–88, 1999.
[5] Joshua N Cooper. When is linear extensions counting easy? AMS Southeastern Sectional Meeting, 2013.
[6] Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Cliﬀord Stein.
Introduction to Algorithms. The MIT Press, Cambridge, 2001.
[7] Robert P Dilworth. A decomposition theorem for partially ordered sets. Annals of Mathematics, 51(1):161–166, 1950.
[8] Yuma Inoue. Master’s thesis: Generating PiDDs for indexing permutation
classes with given permutation patterns. Technical Report TCS-TR-B-14-9,
Division of Computer Science, Hokkaido University, 2014.
[9] Arthur B Kahn. Topological sorting of large networks. Communications of
the ACM, 5(11):558–562, 1962.
[10] Wing-Ning Li, Zhichun Xiao, and Gordon Beavers. On computing the numberof topological orderings of a directed acyclic graph. Congressus Numerantium,
174:143–159, 2005.
[11] Shin-ichi Minato. πDD: A new decision diagram for eﬃcient problem solving
in permutation space. In 14th International Conference on Theory and Applications of Satisfiability Testing (SAT), volume 6695 of LNCS, pages 90–104.
Springer, 2011.
[12] Akimitsu Ono and Shin-ichi Nakano. Constant time generation of linear extensions. In 15th International Symposium on Fundamentals of Computation
Theory (FCT), volume 3623 of LNCS, pages 445–453. Springer, 2005.
[13] David J Pearce and Paul HJ Kelly. A dynamic topological sort algorithm
for directed acyclic graphs. ACM Journal of Experimental Algorithmics,
11(1.7):1–24, 2006.

An Eﬃcient Method of Indexing All Topological Orders for a Given DAG

13[14] Gara Pruesse and Frank Ruskey. Generating linear extensions fast. SIAM
Journal on Computing, 23(2):373–386, 1994.
[15] Robert Endre Tarjan. Depth-first search and linear graph algorithms. SIAM
Journal on Computing, 1(2):146–160, 1972.

14

Yuma Inoue and Shin-ichi Minato

Appendix: Proof of Lemma. 2
Proof. The proof is done inductively over w.
(Induction Basis)
1∑
When w = 1,
lk = n implies l1 = n. Therefore,
k=1
1
∏

(
(lk + 1) = l1 + 1 = n + 1 =

k=1

)1
n
+1
1

holds. This directly proves the induction basis.
(Induction Step)
(
)x
x
x
∏
∑
n
(lk + 1) ≤+1
lk = n. We will prove that
We suppose
holds when
x
k=1
k=1
(
)x+1
x+1
x+1
∏
∑
n
(lk + 1) ≤+1
lk = n. First, we haveholds when
x+1
k=1

k=1

x+1
∏

x
∏

k=1

k=1

(lk + 1) = (lx+1 + 1) ·

Here,

x+1
∑

lk = n implies

k=1

x
∑

(lk + 1).

lk = n − lx+1 . Therefore, we have

k=1

(

x+1
∏

(lk + 1) ≤ (lx+1 + 1) ·k=1

)xn − lx+1+ 1 = f (lx+1 )xfrom the induction hypothesis. Let a be lx+1 to simplify. The first-order diﬀerentiation of f (a) is calculated as follows.
(

)x
(
) (
)x−1
n−a
1
n−a
f (a) =
+ 1 + (a + 1) · −
·x
+1
x
x
x
) (
)x−1
(
n−a
n−a
+1−a−1 ·
+1
=
x
x
(
)x−1
n − (x + 1)a
n−a
=
·
+1
.
x
x
′

n
n
If x = 1, f ′ (a) = n−(x+1)aand hence the maximum is f ( x+1) = ( x+1
+ 1)x+1 .
x
Therefore, this satisfies the induction step. If x ≥ 2, we obtain the extrema

15

An Eﬃcient Method of Indexing All Topological Orders for a Given DAGnnf ( x+1) = ( x+1
+ 1)x+1 and f (n + x) = 0. The second-order diﬀerentiation of f (a)is also calculated as follows.
(
)x−1
(
)
(
)x−2
x+1
n−a
n − (x + 1)a1
n−a′′f (a) = −
·
+1
+
· −
· (x − 1)
+1
x
x
x
x
x
{
(
}
(
)
)x−2
n−a
n − (x + 1)a
1 n−a= − (x + 1) ·+ 1 − (x − 1) ·
·
+1
x
x
x
x
(
)x−2
1 n−a
= {(x + 1)a − 2n − x − 1} ·
+1
.
x
x

x−2 is always positive when 1 ≤ a ≤ n and 2 ≤ x, f (a) is
Since x1 ( n−ax + 1)
2n
upward-convex if a < x+1+ 1, while f (a) is downward-convex otherwise. Because
n
2n
n
n
<
+
1
≤
n
+
x
holds, we can conclude f ( x+1) = ( x+1
+ 1)x+1 is the
x+1
x+1
maximum of f (a) for all 1 ≤ a ≤ n, andx+1∏(lk + 1) ≤ (lx+1 + 1) ·k=1(

n − lx+1+1
xholds. This proves the induction step.

)x(= f (lx+1 ) ≤

n
+1
x+1

)x+1