TCS -TR-B-15-10

TCS Technical Report

Master’s Thesis: A Fast Algorithm
for Enumerating Eulerian Paths
by

Muhammad Kholilurrohman

Division of Computer Science
Report Series B
February 26, 2015

Hokkaido University
Graduate School ofInformation Science and Technology
Email:

kholil@ist.hokudai.ac.jp

Phone:+81-011-706-7682

Fax:+81-011-706-7682

Master’s Thesis
平成 26 年度 修士学位論文

A Fast Algorithm for Enumerating Eulerian Paths
オイラー路を高速に数え上げるアルゴリズム

Muhammad Kholilurrohman
ムハマド

ホリルロハマン

Laboratory for Algorithmics, Division of Computer Science
Graduate School of Information Science and Technology
Hokkaido University
北海道大学

大学院情報科学研究科

コンピュータサイエンス専攻

アルゴリズム研究室

February 26, 2015

Contents
1
1.1
1.2
1.3

Introduction
Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Thesis Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1
2
3
3

2.1
2.2

Preliminaries
Zero-suppressed Binary Decision Diagram (ZDD) . . . . . . . . . . .
Simpath . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4
4
6

3.1
3.2
3.3
3.4
3.5
3.6
3.7

Enumerating Eulerian Paths
Basic Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
The Basic Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . .
The Improved Algorithm . . . . . . . . . . . . . . . . . . . . . . . .
Mate in the Improved Algorithm . . . . . . . . . . . . . . . . . . . .
Updating a Mate in the Improved Algorithm . . . . . . . . . . . . . .
The Pseudocode for the Improved Algorithm . . . . . . . . . . . . .
Retrieving an Eulerian Path from the Constructed Multi-decision DAG

11
11
12
15
17
19
22
24

4.1
4.2
4.3
4.4
4.5

Experimental Results
Multigraph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Complete Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Aztec Diamond . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Congolese drawings . . . . . . . . . . . . . . . . . . . . . . . . . .
Ring graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25
25
27
28
29
29

Conclusion

31

2

3

4

5

Summary
Although a mathematical formula for counting the number of Eulerian cycles in a directed graph is already known [1, 2], no formula is yet known for enumerating suchcycles if the graph is an undirected one. In computer science, the latter problem isknown to be in #P-complete [3], enumerating the solutions of such problem is known tobe hard. In this thesis, an efficient algorithm to enumerate all the Eulerian cycles (paths)
of an undirected graph, both simple graph and multigraph, is proposed.

Chapter 1
Introduction
In graph theory, Eulerian path (or Eulerian trail) is a path in a graph that visits everyedge exactly once. If the path starts and ends on the same vertex, then it is called an
Eulerian cycle. Graph possessing an Eulerian path is called a Semi-Eulerian graph,
while the graph possessing an Eulerian cycle is called an Eulerian graph.
Eulerian cycle problem dates back to 1736, when for the first time Leonhard Euler
discuss in his paper [4] the famous Seven Bridges of Königsberg problem. He proved
the necessary condition for the existence of an Eulerian cycle that all vertices of the connected graph must have an even degree, while the sufficient condition was proved later
by Carl Hierholzer [5] in 1873. Their proofs are extendable to show that the necessary
and the sufficient conditions for a graph having an Eulerian path is that there are exactly
two vertices with odd degree. As a result, removing one edge from an Eulerian graphwill make the graph being a Semi-Eulerian, and connecting the two vertices with odd
degree in a Semi-Eulerian graph will then form an Eulerian graph.
There are some algorithms for constructing an Eulerian path, one of them is called
Hierholzer’s algorithm, which takes linear time [6]. Thus, finding one Eulerian path isconsiderably easy, but enumerating all of the Eulerian paths of a given graph remains
hard and proved to be in #P-complete [3], a complexity class in counting problems thatis as hard as NP-complete class in decision problems1 .
In this thesis, we introduce our approach to solve the problem of Eulerian paths enumeration. We show that our proposed algorithm is efficient for practical use, and is able
to enumerate all Eulerian paths of many graphs which are otherwise will be impossible
to do using a naïve backtrack based algorithm. In our method we use a Multi-decision
Directed Acyclic Graph (Multi-decision DAG) to store all of the Eulerian paths. We
also show how to retrieve an Eulerian path from it which can be done in polynomialtime.
1 In #P-complete class we ask how many solutions for a given problem, while in NP-complete class

we ask whether there is a solution for a given problem.

2

1.1 Background
The most notable research in the past concerning Eulerian paths enumeration is probably due to de Bruijn, van Aardenne-Ehrenfest, Smith and Tutte. They showed that fora directed graph, the number of Eulerian cycles in it can be expressed using a simple
mathematical formula. The formula is called BEST theorem [1] [2], named after theirnames (Bruijn, Ehrenfest, Smith, Tutte).
Theorem 1 (BEST theorem) Let D be a directed graph with vertices V = {v1 , v2 , · · · , vm },and suppose that the in-degree2 of a vertex vi is di . Let t(D) be the number of directedspanning trees rooted at any fixed vertex v in D. The BEST theorem states that the
number of Eulerian cycles Eul(D) in D can be stated mathematically as:m

Eul(D) = t(D) ∏(di − 1)!

(1.1)

i=1

Despite the number of Eulerian cycles in a directed graph can be expressed in a simple mathematical equation, there is no any mathematical expression if the graph is undirected. Some researchers have been able to find the approximate number of the Eulerianpaths in a specific kind of undirected graph. For example in [7], McKay and Robinson
show that the number of Eulerian cycles in a Complete graph3 is asymptotic.
Almost at the same time as the author proposed the method in this thesis, Hanada
et al. [8] tried to solve the same problem by converting the original graph into its line
graph4 . Their method is based on the known fact that every Eulerian path of the originalgraph is corresponding to a Hamiltonian path in its line graph. But since the converse is
not true, that some of the Hamiltonian paths of the line graph actually do not correspondto any of the Eulerian path in the original graph, they have to label these Hamiltonian
paths and exclude them from the enumeration.
To count the Hamiltonian paths, Hanada et al. use an algorithm introduced by Knuth
which is called simpath [9] (exercise 225 in 7.1.4). Generally speaking, simpath isan algorithm that constructs a binary decision graph which later can be transformed
efficiently into a Zero-suppressed Binary Decision Diagram (ZDD) [10], a kind of data
structure that can be used to compactly represent a set of all simple paths5 between two
given vertices of a given graph. Simpath is easily extendable to count the Hamiltonian
paths instead of simple paths by adding one restriction that only the simple paths thosevisit all vertices of the graph are accepted.
Our approach to solve Eulerian paths enumeration is also based on simpath. But
unlike their method, we modify simpath further so that it can be used to count the
2 In a directed Eulerian graph, the in-degree of each vertex must be equal to its out-degree.
3 A Complete graph is a graph in which each pair of its vertices are connected by an edge.
4 Line graph is a graph that represents adjacencies between edges of the original graph.
5 Simple path is a path which does not pass through a vertex more than once.

2

1.3

Thesis Structure

3

Eulerian paths instead of the simple paths. Our algorithm is different from simpath,since we store the Eulerian paths in a multi-decision DAG instead of a binary decisiongraph and we also do not use a ZDD. In simpath, each vertex is only able to be visitedby a path at most once, but in our method we eliminate this restriction and allow eachvertex to be visited multiple times.

1.2 Contributions
Our approach and algorithm has allowed us to confirm and extend the results of someprevious researches, including the number of Eulerian cycles in a Complete graph C(n)[7] up to n = 9, the results from Audibert in his book Mathematics for Informatics
and Computer Science [11], and the results from Hanada et al. [8] for various types ofgraphs.
Although in [7] McKay and Robinson are able to enumerate C(n) for n = 21, theirtechnique is only limited to a Complete graph. On the contrary, our method aims for amore general graph, both simple graph and multigraph.

1.3 Thesis StructureThis thesis is organized as follows. Algorithm to enumerate simple paths (simpath)and the data structure (ZDD) used in it are introduced in Chapter 2. The details of ouralgorithm are discussed in Chapter 3. Next in Chapter 4, we present the experimental
results of this algorithm on several types of graphs. Lastly, we conclude the thesis in
Chapter 5.

3Chapter 2
Preliminaries
This chapter is about simpath algorithm and the data structure used in it, which is called
Zero-suppressed Binary Decision Diagram (ZDD).

2.1 Zero-suppressed Binary Decision Diagram (ZDD)
Zero-suppressed Binary Decision Diagram (ZDD) [10] is a labeled directed acyclic
graph obtained by reducing a binary decision tree graph. Each node (drawn as circle) ina ZDD is labeled by an input variable, and has two outgoing edges, namely 0-edge and1-edge, which connect a node to its two child nodes, 0-child and 1-child, respectively.
0-edge (1-edge) of a node ei is denoted as ei = 0 (ei = 1), and represent a state after thedecision that 0 (1) is assigned to that variable. By traversing the nodes of a ZDD fromits root node (the node at the top of a ZDD), eventually we will reach either 0-terminal
or 1-terminal, which shows the output binary value of variables assignment in that path.
If a ZDD consists of n input variables, then it will have n + 1 levels (height). Eachlevel consists of several nodes which have the same label, and it is common to regard
the two terminal nodes as being together in level n + 1. In this thesis, we always refer
to an ordered ZDD, thus for the input variables e1 , e2 , · · · , en , they will appear orderedregardless of the path we traverse from the root to the terminal node (some variables
may be missing due to the ZDD reduction rules below).
A ZDD can be obtained from a binary decision tree graph by recursively applying
these two rules until no further reduction is possible.
1. Zero-suppression rule: eliminate all nodes whose 1-edge points to the 0-terminal
node. Then connect the edge coming from its parent node to the sub-graph previously pointed by 0-edge of the erased node. See the left figure of Fig. 2.1.
2. Merging rule: share all equivalent nodes which have the same label, 0-child, and1-child. See the right figure of Fig. 2.1.

2.1

Zero-suppressed Binary Decision Diagram (ZDD)

ei

ei
ei=0

f0

ei=0

ei=1

f0

0

ei=1

f0

ei

ei
ei=1

ei=0

5

ei=0

ei=1

f0

f1

f1

Figure 2.1. ZDD reduction rules

s

e1
e1

e2

e2

e3

e3

t
(a)

e1

0

0

e2
e3

1

e3
0

0

(b)

e2

e2

0

e2

e3

e3
1

e1

0

0

1

(c)

e3
0

1

(d)

Figure 2.2. (a) A triangle graph, (b) a binary decision tree, (c) a binary decision graph (unreduced
ZDD), and (d) a ZDD. Here 0-edges are drawn as dashed-line.

ZDD is proved to be ideal for compactly expressing family of sets [10]. For example,
Figure 2.2 (d) shows how the family of sets F = {{e1 , e3 }, {e2 }} is expressed compactly
using a ZDD compared to its corresponding binary decision tree graph (b).
This family of sets F = {{e1 , e3 }, {e2 }} is also representing all simple paths between
the source vertex s and the target vertex t of the triangle graph in (a). In the binary
decision tree (b), the set {e1 , e3 } is represented by the path with e1 = 1, e2 = 0, e3 = 1,
which is called as 1-path because it is connected to 1-terminal. Furthermore, the pathwith e1 = 0, e2 = 1, e3 = 0 which is representing {e2 } is also connected to the 1-terminal.
Strictly speaking, ei = 1 means that edge ei is selected, and if the set of selected edges isforming a simple path, then the corresponding branch in the binary decision tree will beconnected to 1-terminal. Thus, the number of simple paths of a given graph corresponds
to the number of 1-paths in the binary decision tree, which is also equivalent with thenumber of 1-paths in the ZDD.
Next, the number of 1-paths of a ZDD can be enumerated as follows. At first, weassign 0 to 0-terminal node and 1 to 1-terminal node. Then for the other nodes, the valueof a node is the same as the sum of values of its two child nodes. Finally, the value of the
ZDD’s root node is the same as the number of simple paths of the given graph. Thus, thetime needed for enumerating simple paths is proportional to the number of the nodes in
the constructed ZDD, not to the number of simple paths itself. If the compression rateof the ZDD is high, the enumeration time can be very fast.
5

6

2.2 Simpath
Let G = (V, E) be an undirected graph having vertices V = {v1 , v2 , · · · , vm } and edges
E = {e1 , e2 , · · · , en }. Let the source or the starting vertex of the paths be s and the targetof the paths be t, where s,t ∈ V . The goal of simpath is to enumerate all simple paths
between s and t and to store them in a ZDD.
A simple way to construct a ZDD is by recursively applying ZDD reduction rules
into a binary decision tree. The problem is, creating ZDD by this way is not only time
consuming, but also need a lot of memory because for n input variables, the size ofbinary decision tree is already O(2n ).
To speed up the process, simpath does not create a binary decision tree, instead it
creates a binary decision graph1 which then can be effectively reduced into a ZDD. The
construction of the binary decision graph is done in a breadth-first search manner, pruning out the branch that will not produce any simple path in the early stage as possible.
For example in Figure 2.2 (a), if both edges e1 and e2 are not selected, then no simple
path is able to be constructed, so the branch when e1 = 0 and e2 = 0 can be directly
appointed to 0-terminal without having to concern about the assignment of e3 . Simpath
also merges two nodes with the same label when it is known that the two branches willproduce the same output value for any combinations of the rest of the input variables.
A path from the root node to a certain node in a ZDD represents the selected edges
so far. These selected edges will form some path fragments, and each vertex will haveone of the following three states which need to be remembered by that particular node:
1. not included in any path fragments, or
2. intermediate point of a path fragment, or
3. endpoint of a path fragment.
Basically, simpath decides if a branch of the binary decision graph needs to be pruned
out and two nodes can be merged based on the state of the vertices.
In a computer memory, we can use an array to express the state of each vertex. In his
book, Knuth calls this array as mate array, which is a mapping from V to V ∪ {0}.
v if vertex v is untouched so farmate[v] = 0 if vertex v is touched by exactly two edgesu if vertex u(u ̸= v) and v are endpoints of a same path fragment
At first, each vertex is initialized to have a mate value equal to itself (mate[v] = v).
1 This binary decision graph is different from a binary decision tree, since two different nodes in it

can have the same child node. A binary decision graph here can also be regarded as an unreduced ZDD,
which generally has the size between a binary decision tree and a ZDD.

6

2.2
p̂

p

q

mate[p̂ ]=pmate[p]=p̂mate[q]=q̂

Simpath
q̂

7

p̂

p

mate[q̂ ]=q mate[p̂ ]=q̂qmate[p]=0 mate[q]=0q̂mate[q̂ ]=p̂Figure 2.3. Changes in the state of the vertices when an edge p–q is added

v5

v2
v4

v1

v6

v3

v7
(a)

v9

v5

v2

v8
v10

v4

v1
v3

v6

v7

v8
v9

v10

(b)

Figure 2.4. Two nodes which are considered to be identical, since both nodes have mate[v5 ] = v6 ,mate[v6 ] = v5 , and mate[v7 ] = v1

If an edge is selected, we need to update the mate value of some vertices2 . Suppose
mate[p] = p̂ and mate[q] = q̂. If edge p–q is selected, we need to assign mate[p] ← 0,mate[q] ← 0, mate[ p̂] ← q̂, mate[q̂] ← p̂, in exactly this order. Figure 2.3 graphicallyexplains what this assignment is actually doing.
A set of selected edges is accepted when the source vertex s and the target vertex t
are connected and no other path fragment exists, and is rejected when:
1. an edge is added to an intermediate point of a path fragment, or
2. it is known that s and t cannot be connected by current edges selection, or
3. a path connecting s and t is formed and some other path fragments remain.
Actually, the node does not have to remember the state of all vertices. All it needs
is the information of the vertices which shall be called frontier, the set of vertices contained in both processed and unprocessed edge. At the beginning when no edge isprocessed, the frontier is empty. Next when the first edge, let say e1 = u–v, is being
processed, then the current frontier is {u, v}. Eventually when all edges connected to avertex in frontier are already processed, then that vertex will be removed from frontier.
In Figure 2.4, if we let the thin solid line be the unprocessed edges and the other lines
be the processed edges, then the current frontier is {v5 , v6 , v7 } since they are containedin both the processed edges and the unprocessed edges. Furthermore if we let the thicksolid line be the selected edges those will be included in the simple path, and dashedline be the edges not selected, then further selection of the remaining unprocessed edges
2 At most the mates of 4 vertices need to be updated when an edge is selected.

7

8that makes Figure 2.4 (a) has a simple path will also make (b) has a simple path. If welook closer, then we will know that both (a) and (b) have the same mate values for eachvertex in the frontier. In this case, we do not need to process (b) further, instead we canmerge the node representing (b) to the node representing (a).
The Algorithm 1 below is the pseudocode for simpath. The CheckTerminal function
in line 6 is the part where the decision is made, whether we can proceed to the nextedge selection, or we have to appoint the current branch of the binary decision graph to
0-terminal, or we can appoint the branch to 1-terminal. The pseudocode for CheckTerminal function is shown in Algorithm 2. It uses GetDegree function which is shown in
Algorithm 3 to get the current degree of a vertex v. Line 10 of the code in Algorithm 1
is executed if there is already an equivalent node (node having the same mate configurations) created in the binary decision graph, thus the node needs to be merged with thisalready existing identical node.
Algorithm 1: Simpath [9]input : An undirected graph, s, and t
output: ZDD representing all simple paths
N1 ← {noderoot };2 Ni ← 0/ for i = 2, · · · , n + 1; // Ni holds nodes in level i
3 for i ← 1 to n do // processing edge ei
4
foreach node ∈ Ni do // processing nodes in level i5foreach x ∈ {0, 1} do // processing 0-edge and 1-edge
6childnode ← CheckTerminal(node, ei , x, s,t);// CheckTerminal returns 0-terminal,
1-terminal, or nil
7
if childnode = nil then8
Create a new node and set it to childnode;9
if there exists childnode′ ∈ Ni+1 s.t. childnode′ is equivalent tochildnode then10childnode ← childnode′
1

11
12
13

14

8

else
Ni+1 ← Ni+1 ∪ {childnode}Create x-edge to connect node and childnode.
Using ZDD reduction rule, reduce the binary decision graph into a ZDD;

2.2

Simpath9

Algorithm 2: CheckTerminal(node, e, x, s,t)
input : node, e = p–q, x, s,toutput: 0-terminal, 1-terminal, or nil
if x = 1 then2
if GetDegree(p) = 2 or GetDegree(q) = 2 then3
return 0-terminal;

1

4
5
6
7
8
9
10
11
12
13
14

15

if (p = s or p = t) and GetDegree(p) = 1 thenreturn 0-terminal;
if (q = s or q = t) and GetDegree(q) = 1 thenreturn 0-terminal;
if mate[p] = q and mate[q] = p thenreturn 0-terminal;if (mate[p] = s and mate[q] = t) or (mate[p] = t and mate[q] = s) thenforeach vertex v ∈ frontier do
if v ̸= s and v ̸= t and v ̸= p and v ̸= q thenif GetDegree(v) = 1 thenreturn 0-terminal;
return 1-terminal;

foreach v leaving frontier do
17
if v = s or v = t then18
if GetDegree(v) = 0 then19
return 0-terminal;
16

20
21
22

else
if GetDegree(v) = 1 thenreturn 0-terminal;

9

10

Algorithm 3: GetDegree(v)input : Vertex v
output: Current degree of v, which can be 0, 1 ,or 2
if mate[v] = v then // no path fragment is connected to v
2
return 0;
1else if mate[v] = 0 then // vertex v is an intermediate point
4
return 2;
3else // v is an endpoint of a path fragment
6
return 1;
510Chapter 3
Enumerating Eulerian Paths
In this section, two algorithms for enumerating Eulerian paths are introduced. The
first algorithm is the basic version, which in many ways is similar to simpath, thus
hopefully can be understood easily. In contrast to this, the second algorithm, whichis the improved version, uses many modifications to simpath. The first algorithm isintended as the introduction to make it easier to understand the improved algorithm. All
experiments in this thesis are done using the improved algorithm. In both algorithms,
we distinguish two similar Eulerian cycles having different direction. For example, theEulerian cycle v1 → v2 → v3 → v1 is counted separately from v1 → v3 → v2 → v1 .

3.1 Basic Idea
Suppose there are xi edges connected to a vertex vi ∈ V = {v1 , v2 , · · · , vm }. We wantto make pairing of edges in vertex vi , by at first disconnecting these xi edges and thenreconnecting them in a way such that every edge has a pair. The number of combinationsof such edge pairing1 is
) ( )
( ) (
n/2
xi !
2
1
xi − 2xi· xi = xi x = ∏(2i − 1).
····f (xi ) =222
2 2 · i ! i=1
2!

(3.1)

2

Using the counting rules in combinatorics, at first we choose 2 from the xi edges, thenchoose 2 from the remaining xi − 2 edges, and so on until no edge remains. But since apair of edges chosen in the first selection or second or third etc. are not differentiated,the overall number must be divided by x2i !, which gives us the Equation 3.1.
Now, if we disconnect all edges of the input graph and then reconstruct it by combining all of the possible edge pairing in the entire vertices of the graph, then the total

1 We assign x ← x + 1 for vertex s and t if they have odd degree.
i
i

12
start
1
1
3

2
3

2

5

7
4

4
9

6
11

5

8

10

6

12
13
14

targetFigure 3.1. Disconnecting the edges of a graph and relabelling its vertices

number of such constructions ism∏ f (xi).

(3.2)

i=1

Clearly, this number consists of all Eulerian paths of the input graph plus additionalgraph structures those have a cycle fragment. Our aim is to remove the latter kind of thegraphs.

3.2

The Basic Algorithm

In this algorithm, we start from disconnecting all of the edges and relabel the verticesof the input graph such that no two edges have the same vertex. More precisely, let
G = (V, E) be the input graph with vertices V = {v1 , v2 , · · · , vm } = {1, 2, · · · , m} andedges E = {e1 , e2 , · · · , en }. Let the starting vertex of the Eulerian paths be s and thetarget be t, where s,t ∈ V . Then, the algorithm disconnects the edges of the input
graph such that no two edges is connected and also relabels the graph vertices such thatvertices V ′ = {1, 2, · · · , 2n, start,target} and edges E ′ = {1–2, 3–4, · · · , (2n − 1)–2n},where start ← 2n + 1,target ← 2n + 2, and they are being isolated vertices.
Let us define γi (1 ≤ i ≤ m) as a set of vertices in the new graph that correspond to thevertex vi in the input graph2 . For example, if the left part of Fig. 3.1 shows an input graphwith s = 1 and t = 6, and the right part shows the disconnected and relabeled graph, thenwe have γ1 = {1, start}, γ2 = {2, 3, 5, 7}, γ3 = {4, 9}, γ4 = {6, 11}, γ5 = {8, 10, 12, 13},and γ6 = {14,target}.
The mate initialization in the algorithm is done by considering the disconnected graphas path fragments, thus mate[start] ← start, mate[target] ← target, mate[2i − 1] ← 2i
and mate[2i] ← 2i − 1 for (1 ≤ i ≤ n). Next if two vertices are going to be connected
2 The vertex start is in the set that corresponds to the vertex s in the original graph, and the vertex

target is in the set that corresponds to the vertex t in the original graph.

12

3.2

The Basic Algorithm

13

2

3

4

5

6

7

8

9

10

11

12

13

14

1

Figure 3.2. The DAG that stores all of the Eulerian paths of Fig. 3.1(during the edge pairing), we need to update the mates of the corresponding vertices
using the exactly same rules as in simpath.
The algorithm makes a breadth-first search to find all of the Eulerian paths by trying
all possible edge pairings in γi (1 ≤ i ≤ m)3 , while creating a multi-decision DAG that
stores all of the Eulerian paths. The DAG pruning and the node merging are carried out
with the similar manner as in simpath, that is by observing the state of the vertices infrontier. For example, the process when the algorithm is used for finding the Eulerianpaths in the left figure of Fig. 3.1 is shown graphically in Fig. 3.2.
The Algorithm 4 below shows the pseudocode of the basic algorithm for enumerating
3 For Eulerian cycles enumeration, vertex start and vertex target are not allowed to be paired.

13

14
Eulerian paths. Actually, this algorithm is time consuming, because the number of thepossible edge pairing in γi as shown in line 7 of the algorithm, which is also equals to theEquation 3.1, is growing fast as the size of γi grows bigger. Moreover, the algorithm isalso memory consuming since the node merging is expected to be done in an inefficientway. For example, we cannot merge the node having mate[a] = x, mate[b] = y(a ̸=b, x ̸= y) with the node having mate[a] = y, mate[b] = x even though vertex a and vertex
b are both representing the same vertex c in the original graph. The improved versionof this algorithm uses a different approach, it considers path fragments connected to avertex of the original graph as a set (more precisely, a weighted set). For example inthis scenario, the two nodes will have mate[c] = {x, y}, thus increasing the chance ofthe two nodes being merged.
Algorithm 4: The basic algorithm for enumerating Eulerian paths
input : An undirected graph, s, and t
output: Multi-decision DAG that stores all Eulerian paths
Disconnect the graph edges and relabel its vertices;
2 Initialize the mate;
3 N1 ← {noderoot };4 Ni ← 0/ for i = 2, · · · , n + 1; // Ni holds nodes in level i
5 for i ← 1 to m do // processing γi
6foreach node ∈ Ni do // processing nodes in level i7foreach posib ∈ possible edge pairing in γi do
8childnode ← CheckTerminal(node, posib);// CheckTerminal returns 0-terminal if acycle fragment is formed, otherwise nil
9
if childnode=nil then10
Create a new node and set it to childnode;11
if there exists childnode′ ∈ Ni+1 s.t. childnode′ is equivalent tochildnode then12childnode ← childnode′
1

13
14
15

16

14

else
Ni+1 ← Ni+1 ∪ {childnode}Create an arc to connect node and childnode in the DAG.
Connect the last node to the 1-terminal;3.3 The Improved Algorithm

15

3.3 The Improved Algorithm
In this algorithm, we disconnect the input graph and reconstruct it by putting theedges one by one while considering the edge pairing in the two vertices of each edge.
Every time we put an edge, generally we have two choices, whether to connect it to
one of the already existing unpaired edges or not. For example, let the edge p–q isbeing processed and is going to be added to the reconstructed graph so far. If we seeat the vertex p, then the possibilities are whether the edge p–q is connected to one of
the already existing unpaired edges in p, or it is not connected to any of them. The
same condition also applies for vertex q, whether we connect the edge p–q to one of thealready existing unpaired edges in q or not. In the other words, at each step we have toconsider edge pairing in the two vertices of the currently being processed edge.
As in simpath, we keep track on the state of the vertices in frontier4 by using a matearray. The difference is, since each vertex may appear in a simple path at most once,
each vertex in simpath has exactly one mate slot. In contrast to this, a vertex in an
Eulerian path can appear multiple times. Therefore, during the graph reconstruction
process we have to allow a vertex to hold multiple path fragments. This is done byassociating each vertex with a weighted set, and the mate array is now being an array ofweighted set instead of an array of integers which is used in simpath.
These are some reasons why we use a weighted set instead of the other data containers
such as a set, a linked list or an array of integers:
1. There will be some different path fragments those have the same two endpoints,
therefore using an ordinary set as mate is not possible since it cannot have multiple
identical elements.
2. The elements of a weighted set are sorted, which is very important because it
increases the probability of two nodes being merged. If we use a linked list or anarray of integers, then we have to re-sort its elements each time a change happens.
3. The weight of an element in the weighted set shows how many different pathfragments leading to the same other endpoint. We do not need to examine thesepath fragments one by one when an edge is connected to them, since eventually
they will result in the same mate configurations. As the result, this will speed up
the algorithm.
The weighted set associated with a vertex vi needs to be a resizable container. Initiallywhen the edges connected to this vertex are not yet processed, the size of the weighted
set is zero. If an edge is processed and is connected to a path fragment already in
4 The definition of frontier in this algorithm is exactly the same as in simpath, that is the set of vertices

contained in both processed and unprocessed edges.

15

16
1

2

3

e1
e4

v

4

5

6

7

8

9

e2

e3
(a)

(b)

Figure 3.3. Edge matching on a vertex

the vertex, then the size of weighted set is not changed. If the processed edge is notconnected to any of the path fragments in the vertex, then the size of the weighted set isincremented, for accommodating this newly added edge. Finally when all of the edges
connected to this vertex are processed, the size of the weighted set needs to be exactly5 :deg(vi )
.
2

(3.3)

which is equal to the number of appearance of vi in the Eulerian path.
Summarizing the discussion, we have these two options when an edge is added to avertex vi :1. connect to an unpaired edge in vi , or
2. do not connect to anything, thus creating a new unpaired edge. This choice is only
available if the number in Equation 3.3 is not reached yet.
For example, vertex v in Figure 3.3 (a) has four edges e1 , e2 , e3 and e4 . Suppose we
process the edges in that order. In our algorithm, when adding an edge to the being
reconstructed graph we need to consider the edge pairing in its two vertices. But forthe sake of explanation, let us take attention only on vertex v. At first when e1 is being
processed, there is still nothing connected to vertex v, so we just put edge e1 as a new
unpaired edge as shown in node 1 of Fig. 3.3 (b). Next, when we are adding edge v2
we have two possibilities, whether to connect this edge to the already existing edge e1 ,or we do not connect to any of the unpaired edges already in the vertex. In node 3,
we cannot make a new unpaired edge because the maximal number of Equation 3.3 isalready reached, so we just connect the edge e3 to the existing unpaired edges there.
In our algorithm, we do not necessarily process all of the edges connected to a vertex
at once. Sometimes we leave some edges unprocessed, and instead process another edge
5 Again, we need to make deg(v ) ← deg(v ) + 1 for vertices s and t if they have odd degree.
i
i

16

3.4

Mate in the Improved Algorithm

17
6

1
2

mate[1]={2}mate[2]={1}

1
2

1
2

3
1
2

1
2
4

3

1

3

3

5

1
2

5

1
2
4

3
5

1

1

5

5

43

3

5

5

4

3

2

2

mate[2]={0}mate[3]={1}mate[2]={0,1}mate[3]={4}mate[4]={3}mate[3]={4}mate[4]={3}mate[5]={1}mate[4]={1}mate[5]={5,5}2mate[4]={5}mate[5]={1,4}2mate[2]={0,4}mate[3]={1}mate[4]={2}mate[3]={1}mate[4]={5}mate[5]={4}

2

2

1

mate[4]={1}mate[5]={0}

1

1

4
5

mate[5]={0,1}

1
2
4

3

2

2

2
4

5

4

1
2

1
2
4

43

3

1

3

5

1
2

1
2

1
2
4

5

mate[3]={5}mate[4]={1}mate[5]={3}

5

2

43

3

2
4

3

4

mate[2]={0,3}mate[3]={2}mate[4]={1}

4

1
2
4

2

3

4

1
2
3

mate[2]={1,3}mate[3]={2}

3

6

5
6
1

1
mate[6]={1}11Figure 3.4. Enumerating Eulerian paths of the graph in Fig. 3.1 using the improved algorithm

not directly connected to this vertex. The actual example of edge pairing is shown in
Fig. 3.4, which shows what happen when the left figure of Fig. 3.1 is processed using
this algorithm.

3.4 Mate in the Improved Algorithm
The definition of mate in the improved algorithm is different from the mate in simpath
since we are using a weighted set. For a vertex p ∈ f rontier, we write mate[p] as{α1 , α2 , · · · , αg }, where α1 < α2 < · · · < αg (sorted) and each element αi (1 ≤ i ≤ g)
has its own weight. Since a frontier consists of several vertices, the actual mate of anode in a computer memory can be described graphically using Fig. 3.5. In this figure,the current frontier is { f1 , f2 , f3 , f4 , f5 }, and each f ∈ f rontier has its own mate table
which shows the path fragments connected to f . In addition, since the elements of themate table need to be always sorted, in our experiment we use a multiset class provided
by the Standard Template Library (STL) in C++ instead of an array. If we use an array,then we need to re-sort the mate table each time a change happens.
Similar to simpath, αi = 0 means an intermediate point of a path fragment, and αi = v
for an v ∈ V refers to a path fragment that has one endpoint at p and the other at v (in theother words, p and v are connected by a path fragment). Different from simpath, in this
17

18
f1

f2

f3=p f4

f5

mate[f1]…

mate[p ] α1 α2 … αgmate[f5]…

weight…

weight… w(αg)weight…

w(α1) w(α2)

mate[f2]…

mate[f4]…

weight…

weight…

Figure 3.5. The mate of a node having f rontier = { f1 , f2 , f3 = p, f4 , f5 }. The mate[ f ] for eachf ∈ f rontier is assumed to be sorted

algorithm αi = p does not mean that p is an untouched vertex, but it means that there isa path fragment which has two endpoints at p. An untouched vertex in the algorithm isknown by its mate size which is equal to zero.
In the implementation, mate[p] is wrapped in a class which has several operators.
• The most basic operator is called get(αi ), which return the actual address of theelement αi inside the computer memory (which is needed since the mate table ofa vertex is not necessarily an array, thus we assume that there is no such mate[p][i]to call αi ).
• new(α ) will create and add a new element α with weight 1 into mate[p]. This
operator is guaranteed to be called only if no element in mate[p] equals α .
• delete(αi ), to delete αi from mate[p].
• inc(αi ), to increment the weight of αi if αi is already in mate[p], or to call new(αi )otherwise.
• dec(αi ), to decrement the weight of αi if the weight of αi is more than 1, or tocall delete(αi ) otherwise.
• w(αi ), that return the weight of αi .
• size(), that will return the current size of mate[p] (which is equal to the total
weight of αi (1 ≤ i ≤ g)).
• The last operator is called replace(αi , αi′ ) which will call inc(αi′ ) and then calldec(αi ), in exactly this order.
Basically, all operators except new(α ) will use operator get(αi ) in order to get the actual address of αi inside the computer memory. Also, we assume that when a change
happens to mate[p], then its elements will be automatically re-sorted.
18

3.5

Updating a Mate in the Improved Algorithm

path fragment 1

path fragment 1

α1=q
α1=q

β1=p

α'1=0

β1=p

α1=q

p

β'1=0

α'1=0

β1=p

α1=q

path fragment 2q(a)path fragment 1edge p-q

path fragment 2ppath fragment 1

β1=p

α1=q

β'1=0

α'1=0

β'1=0
β1=p

path fragment 2

q
(b)

19

p

path fragment 2

q
(c)

p

q
(d)

Figure 3.6. Connecting α1 = q and β1 = p

3.5 Updating a Mate in the Improved Algorithm
Suppose there are k unpaired edges (path fragments) connected to vertex p and l unpaired edges (path fragments) connected to vertex q. More formally, let we assume
mate[p] = {α1 , α2 , · · · , αg } and mate[q] = {β1 , β2 , · · · , βh } do not have any element
equals zero, and mate[p].size() = k and mate[q].size() = l. Then the k × l combinations of possible edge pairing have to be considered if we add an edge p–q to the reconstructed graph so far. In addition, if there is still a slot to add a new path fragment6 to thevertex p and q, we have to consider in overall (k + 1) × (l + 1) possible edge pairings.
Similar to simpath, when an edge is added to the current constructed graph, we need
to update mates of some vertices. The difference is, since the mate of a vertex in ouralgorithm is a weighted set, the updating rule now is a little different from simpath.
Furthermore, identifying a cycle fragment being formed is also a bit tricky. In simpath,
we could not connect vertex p and vertex q if mate[p] = q and mate[q] = p since they
will form a cycle fragment. But in our method, αi = q(1 ≤ i ≤ g) and β j = p(1 ≤ j ≤ h)does not simply mean that connecting them will form a cycle fragment, since there isa possibility that they are actually belong to two different path fragments. For example
in Fig. 3.6 (c) and (d), we can still safely connect αi to β j despite αi = q and β j = p.
In contrast, connecting αi = q and β j = p which come from the same path fragment asshown in Fig. 3.6 (b) will cause a cycle fragment being formed, thus need to be avoided.
Since a mate only remembers the endpoints of a path fragment, the algorithm could
not differentiate which of αi = q and β j = p those belong to different path fragmentsfrom the ones those belong the same path fragment. But fortunately, we know thatany possible edge pairing that does not form a cycle fragment will result in the samemate configurations. For example in Fig. 3.6, connecting α1 which comes from pathfragment 1 to β1 which comes from path fragment 2 (as shown in Fig. 3.6 (c)) will havethe same identical result with connecting α1 which comes from path fragment 2 to β1
6 When the size of mate[p] or mate[q] is still less than Equation 3.3.

19

20

α

β

r

p

q

mate[r]={p}mate[p]={r}mate[q]={s}srmate[s]={q}mate[r]={s}

α

β

p

q

mate[p]={0} mate[q]={0}smate[s]={r}Figure 3.7. Connecting two path fragments in p and q with edge p–qαrmate[r]={p}

p

α

q

mate[p]={r} mate[q]={}rmate[r]={q}pqmate[p]={0} mate[q]={r}Figure 3.8. Connecting a path fragment in p to vertex q with edge p–q

which comes from path fragment 1 (as shown in Fig. 3.6 (d)), that is the weight of α1and β1 are decreased by one, and the weight of 0s in the both vertices are increased byone. Therefore, our problem can be solved by not examining the (k + 1) × (l + 1) cases
one by one, instead we need to examine just (g + 1) × (h + 1) cases, in which each casehas several identical results depending of the weight of αi and β j .
Generally, the number of identical results when αi and β j are connected by edge p–q
is equal to mate[p].w(αi ) × mate[q].w(β j ). The only exception is when a cycle fragment
is formed, which happens if αi = q and β j = p. Fortunately, we know that the numberof results having a cycle fragment is equal to the number of path fragments connecting
p and q, which is equal to the weight of αi , and which is also equal to the weight of β j .
Therefore in the case αi = q and β j = p, we need to subtract mate[p].w(αi ) from thegeneral number of identical results.
If αi = r and β j = s, then the result when a path fragment having endpoints at r
and p is connected to a path fragment having endpoints at q and s by edge p–q isobtained by calling mate[r].replace(p, s), mate[s].replace(q, r), mate[p].replace(r, 0),mate[q].replace(s, 0). This procedure is very similar with mate update in simpath, andcan be interpreted graphically using Fig. 3.7.
Next, if edge p–q is added to connect a path fragment in p which has another endpoint
at αi = r to vertex q (hence we do not connect edge p–q to any of the path fragments
in q, instead we create a new unpaired edge in q), then the result is obtained by callingmate[r].replace(p, q), mate[p].replace(r, 0), mate[q].inc(r), which is described graphically in Fig. 3.8.
The opposite condition, if edge p–q is added to connect vertex p with a path fragmentin q which has another endpoint at β j = s (hence we do not connect edge p–q with any
20

3.5

Updating a Mate in the Improved Algorithm

βpmate[p]={}

21

β

q

s

mate[q]={s}mate[s]={q}

p

q

s

mate[p]={s} mate[q]={0}mate[s]={p}Figure 3.9. Connecting vertex p to a path fragment in q with edge p–qpmate[p]={}qmate[q]={}pqmate[p]={q} mate[q]={p}Figure 3.10. Adding edge p–q without connecting it to any of the existing path fragmentsof the path fragments in p, instead we create a new unpaired edge in p), then the result isobtained by calling mate[p].inc(s), mate[q].replace(s, 0), mate[s].replace(q, p). These
procedures are described in Fig. 3.9.
Last, if edge p–q is added without neither connecting it to any of the path fragmentsin p nor q, then the result is obtained by calling mate[p].inc(q), mate[q].inc(p), which
can be described using Fig. 3.10.
Node merging in this algorithm is done in the same way as in simpath, that is two
nodes having the same mate configurations can be merged. In our method, we use aweighted set to express mate of a vertex to improve the possibility of nodes merging,since the elements of a weighted set is always sorted. If the elements of a mate is not
sorted, for example a node having mate[v] = {2, 1, 3} will not be merged with a node
having mate[v] = {3, 1, 2}. The condition may be different if they are sorted, sinceboth nodes will have the same mate[v] = {1, 2, 3}, thus increasing the chance of the two
nodes being merged.
In our method, we do not use a 0-terminal to express a dead end during the graph construction. A branch in the multi-decision DAG that needs to be pruned out will simply
be ignored without expanding it further, while a branch that corresponds to an Eulerian
path will be connected to 1-terminal. When the multi-decision DAG is completed, then
the number of Eulerian paths of the input graph is equal to the number of paths leadingfrom root node to 1-terminal in this DAG.

21

22

3.6 The Pseudocode for the Improved Algorithm
The Algorithm 5 below is the pseudocode for the improved algorithm. In this algorithm, Ni is a set of nodes in level i(1 ≤ i ≤ n + 1) of the DAG. As shown in line
1 and line 2, N1 is initialized to contain the root node of the DAG, while for i > 1,
Ni is initialized to be an empty set, which later will be filled with nodes during the
program execution. Next in line 5, the MateForChildNodes function tries all possible
constructible graphs (the uncompleted Eulerian path) when the edge ei (1 ≤ i ≤ n) is
added to the reconstructed graph so far. The details of this function are then described
as Algorithm 6.
Algorithm 5: The improved algorithm for enumerating Eulerian paths
input : An undirected graph, s, and t
output: A multi-decision DAG storing all Eulerian paths
N1 ← {noderoot };2 Ni ← 0/ for i = 2, · · · , n + 1; // Ni holds nodes in level i
3 for i ← 1 to n do // processing edge ei
4
foreach node ∈ Ni do // processing nodes in level i
5
MateForChildNodes(node, ei , Ni+1 );1

Algorithm 6 shows how to connect vertex p with vertex q using an edge p–q. Moreprecisely, line 1 up to line 9 shows how to connect one of the existing path fragments
connected to p to one of the existing path fragments connected to q. Next, line 10 is toconfirm that the mate size of vertex q is still below the number in Equation 3.3, thus wecan add an edge to vertex q without connecting it to any of path fragment there. The
next 5 lines shows how to connect one of path fragments connected to p with vertex
q (which is already explained using Fig. 3.8). Line 16 to line 21 shows the opposite,that is connecting a path fragment in q to vertex p, which is also already explained using
Fig. 3.9. The last part, line 22 to line 26 shows how to connect vertex p to vertex q usingedge p–q without connecting it to any of the existing path fragments. Since connecting
an edge to the intermediate point of a path fragment is not allowed, we assume that αi
and β j in the entire algorithm is not equal to 0.
Algorithm 7 is used for connecting the newly created child node to its parent node in
the multi-decision DAG using numO fChilds many arcs. Line 1 and line 2 are executed
when there is only one path fragment connecting vertex p with vertex q (for example inFig. 3.6 (a), there are two path fragments connecting p with q). Line 3 and line 4 are theparts used for node merging, while line 5 and line 6 are used to add the newly creatednode into the multi-decision DAG if there is no identical node in there.

22

3.6

The Pseudocode for the Improved Algorithm

23

Algorithm 6: MateForChildNodes(node, e, Nnext )input : node, e = p–q, and Nnext
output: –// Suppose node has mate configurations parentmate, and{α1 , α2 , · · · αg } equals parentmate[p] with 0 element being
removed and {β1 , β2 , · · · , βh } equals parentmate[q] with 0
element being removed
1 for i ← 1 to g do // processing αi
2for j ← 1 to h do // processing β j
3childnode ← node; // for the child node. Let themate configurations of childnode being named mate4
numO fChilds ← mate[p].w(αi ) × mate[q].w(β j );5
if αi = q and β j = p then6
numO fChilds = numO fChilds − mate[p].w(αi );789mate[αi ].replace(p, β j ); mate[β j ].replace(q, αi );mate[p].replace(αi , 0); mate[q].replace(β j , 0);CreateChildNodes(node, childnode, numO fChilds, Nnext );if parentmate[q].size() < deg(q)
then
2
11
for i ← 1 to g do // processing αi12childnode ← node;
13
numO fChilds ← mate[p].w(αi ) × 1;
14mate[αi ].replace(p, q); mate[p].replace(αi , 0); mate[q].inc(αi );15CreateChildNodes(node, childnode, numO fChilds, Nnext );10

if parentmate[p].size() < deg(p)
then
2
17
for j ← 1 to h do // processing β j
18childnode ← node;
19
numO fChilds ← 1 × mate[q].w(β j );20
mate[β j ].replace(q, p); mate[p].inc(β j ); mate[q].replace(β j , 0);21CreateChildNodes(node, childnode, numO fChilds, Nnext );16

and parentmate[q].size() < deg(q)thenif parentmate[p].size() < deg(p)2223childnode ← node;
24
numO fChilds ← 1;
25
mate[p].inc(q); mate[q].inc(p);26CreateChildNodes(node, childnode, numO fChilds, Nnext );
22

23

24

Algorithm 7: CreateChildNodes(node, childnode, numO fChilds, Nnext )input : node, childnode, numO fChilds, Nnext
output: –if numO fChilds = 0 then2
return1

if there exists childnode′ ∈ Nnext s.t. childnode′ is equivalent to childnode then4childnode ← childnode′
3

else
6
Nnext ← Nnext ∪ {childnode}
5

7

Connect node and childnode using numO fChilds many arcs.

3.7 Retrieving an Eulerian Path from the Constructed
Multi-decision DAG
To retrieve the number n’th Eulerian path from the constructed multi-decision DAG,
at first we need to give the nodes in the multi-decision DAG their values. The value ofa 1-terminal node is equal to 1, and the value of the other nodes are equal to the sum ofvalues of their children nodes. For example, the right figure of Fig. 3.4 shows a multidecision DAG with the value of each node being printed out next to the node. Once thisis done, we can determine the path in the multi-decision DAG that correspond to thenumber n’th Eulerian path by comparing n with the value of the nodes while traversing
the multi-decision DAG from its root node to 1-terminal. Later, this path can be used as
guidance to reconstruct the Eulerian path. The complexity of reconstructing an Eulerian2path is O(|E| · max( deg(v)2 ) ), since we are adding edges one by one, and each time anedge is added we need to search the right path fragments need to be connected by thisedge.
However, there is a limitation in our method since we could not extract a set of Eulerian paths that satisfies a given condition from the constructed multi-decision DAG. For
example, we could not get a set of Eulerian paths that has the property that e1 must be
followed by e2 from the multi-decision DAG.

24

Chapter 4
Experimental Results
In this section, we present the results of our experiments only for the improved algorithm. In all experiments, the computational time is measured in second unit. The
algorithm was implemented using C++11 and run on a machine with 4 GB memory
R
CoreTM i3-2330M CPU @ 2.20GHz × 4.
Intel⃝In this thesis we present the results of our experiments with five different types ofgraphs. At first, we show the results for graphs having multiple edges and compare
the results with the corresponding simple graph. Then, we also present the results forComplete graph. For the Aztec diamond graph [11], we present the results up to n = 8.
Next, we also show the results for Congolese drawings. At last, we present the resultsfor Ring graph and confirm these results by comparing them with the number of Eulerianpaths derived from a mathematical equation.

4.1 Multigraph
The proposed algorithm in this thesis is relatively fast for processing both multigraph1
and its “corresponding” simple graph. Although processing a multigraph is slightly
faster, we could not distinguish some edges once an Eulerian path is retrieved from theDAG, while in a simple graph we can easily distinguish the edges since there is no any
multiple edge. For example, let the left graph in Figure 4.1 be a(n) and the right one
be b(n). Starting from vertex 1, we want to enumerate all Eulerian paths if n is odd,
and all Eulerian cycles if n is even. The results for some n are summarized in Table 4.1.
For the same n, we can see in this table that the number of DAG nodes used to store
the Eulerian paths of a simple graph is more than the number of DAG nodes used for a
multigraph, which makes the processing time for a multigraph becomes faster.
Using a simple backtrack based algorithm to search the number of Eulerian paths
in both a(n) and b(n), we already running out of time for n = 12. In contrast, using
1 Here, a multigraph is a graph with multiple edge, but without self-loop.

26

1
e1

2

3

en

e 2 e3 e 4

4
en+1

1

en+2

5
en+3 en+4

e1 e2 e3n+1…

e4 … en

e2n

n+2

2

(a)

(b)

Figure 4.1. Simple Graph vs Multigraph

Table 4.1. Simple Graph vs Multigraph

1
2
3
4
5
6
7
8
9
10
11
12
13

a(n)
proposed algorithm
nodes
time
5
0.00033180.000484
140.00514319
0.00826433
0.014939
420.015787
67
0.025232
82
0.026160
112
0.028066
146
0.031964
205
0.029756
241
0.036714
324
0.036364

30
40
50
60
70
80
90
100

4236
11434
25276
48949
86267
141674220258327603n26

0.191787
0.599417
1.554008
4.022040
8.368751
16.148767
27.067279
44.423667

backtracktime
0.000138
0.000392
0.000822
0.002060
0.013594
0.065717
0.382385
3.187142
30.145249
320.352194
3612.151051
time out
time out
time out
time out
time out
time out
time out
time out
time out
time outb(n)proposed algorithm
nodes
time
4
0.00025860.000339
80.003770
110.004230
160.008759
210.01204530
0.018849
38
0.01617452
0.025878
64
0.028012
85
0.023074
102
0.034845
131
0.025434
1584
4169
9068
17364
30349
49523
76602
1135180.133952
0.412097
1.097576
2.497769
5.105830
9.789022
16.798351
28.106356

backtracktime
0.000159
0.000195
0.000385
0.001214
0.005399
0.021279
0.087972
0.650604
5.796462
58.130634
638.443941
time out
time out
time out
time out
time out
time out
time out
time out
time out
time out

solutions
1
2
6
24
120
720
5040
40320
3628803628800
39916800
479001600
6227020800
2.652529 × 1032
8.159153 × 1047
3.041409 × 1064
8.320987 × 1081
1.197857 × 10100
7.156946 × 10118
1.485716 × 10138
9.332622 × 10157

4.2

Complete Graph

27
1

1

1

2

1

2

2

5

3
3

2

9

7

8

6
4

3

3

4

4

5

7
5

6

Figure 4.2. Complete graph C(n) for n = 3, 5, 7, and 9
Table 4.2. The Results for Complete graph C(n)n nodestime
3
7 0.000442
550
0.020941
72168 0.100832
9 451162 33.361454

solutions
2528
389928960
3646080228084940800

our proposed algorithm, we are still able to enumerate the Eulerian paths for n = 100in considerably a little time. By comparing the number of nodes with the number ofthe solutions, we also understand that the compression rate of the DAG in this case isincredibly high. As example for n = 100, the number of Eulerian paths in both a(n)and b(n) is 9.332622 × 10157 , and they are stored in a DAG having merely 327603 and113518 nodes, respectively.
In these kinds of graphs, it is easy to check the number of the Eulerian paths by hand.
Especially for graph b(n), the number of Eulerian paths is the same as the number of
permutation of the edges e1 , e2 , · · · , en , which is n!.

4.2 Complete Graph
A Complete graph C(n) is a connected undirected graph having n vertices in which
each vertex is connected to the rest of the other vertices of the graph. Examples of suchgraph are shown in Fig. 4.2. It is known that a Complete graph has an Eulerian cycle if
and only if the number of its vertices is odd (which means that the degree of each vertex
is even).
The results of our experiments on these graphs are shown in Table 4.2, which confirm the results from McKay and Robinson in [7] up to n = 9. Their technique forenumerating Eulerian cycles is specialized only for a Complete graph, and they havebeen succeeded in computing the Eulerian cycles for n = 21. Unfortunately, they did
not write the computation time, therefore we could not compare with the results from
our algorithm.

27

28

8

11

18

22

11

15

19

23

2

4

3

6

9

12

4

8

12

16

20

24

1

3

1

4

7

10

1

5

9

13

17

21

2

5

2

6

10

14

3

7

Figure 4.3. Aztec Diamond for n = 1, 2, and 3

Table 4.3. The Results for Aztec Diamond Using Proposed Algorithm
n
1
2
3
4
5
6
7
8

nodes
8
40
286
2164
17271
148224138230214083862

time
0.000228
0.015503
0.032317
0.071024
0.500763
6.153548
73.527219
942.330957

solutions
2
8026432067131225600
1282298454848135168
1823958835474044219224391680
192178269775153104174170778660103782400
1495157006436041186484738405257449073460914460033024

4.3 Aztec Diamond
The Aztec diamond in this thesis is a bit different from the usual2 Aztec diamond.
The Aztec diamond here as shown in Figure 4.3 is the same as the graph described by
Audibert in his book, Mathematics for Informatics and Computer Science [11]. Startingfrom the lower vertex of the leftmost edge, i.e. vertex number 1, we want to count the
number of Eulerian cycles coming back to this vertex. Using backtrack algorithm, we
could only count the Eulerian cycles up to n = 3, which took 150.041790 seconds.
For n = 4, the running time is already more than 1 hour, so we stopped the program.
Audibert also only writes down in his book the number of Eulerian cycles up to n = 3.
On the contrary, using our proposed algorithm we could count the Eulerian paths up ton = 8. The detailed results are presented in Table 4.3.

2 The general term of Aztec diamond refers to a similar graph but with the leftmost, rightmost, upper-

most, and lowermost edges are 2.

28

4.5 Ring graph

29

25

31

13

19

26

32

7

14

20

27

33

2

8

15

21

28

34

3

9

16

22

29

35

4

10

17

23

30

5

11

18

24

6

12

21
7
1

1

3

2

4

1

4

8

2

5

9

3

6

9

13

5

10

14

2

6

11

15

3

7

12

4

8

1

16

11

16

22

6

12 17

23

2

7

13

18

24

3

8

14

19

25

4

9

15

20

5

10

1

36

Figure 4.4. Congolese drawings P(n) for n = 2, 3, 4, 5, and 6
Table 4.4. The Results for Congolese drawings P(n)
n
2
3
4
5
6
7
8
9
10
11
12
13
14
15

nodes
6
13
58
104
532
769
4586
5691
39989
44497
36652937636535946663473985

time
0.000323
0.000662
0.013032
0.023173
0.031281
0.036871
0.137933
0.184710
1.377636
1.709373
17.958141
19.629299
231.981171
236.014467

number of Eulerian paths
1
4328
111616632492400
16551741353984
6727963389195631296
13207065216910433569559552
388372864607037921166706218127104
56689167098449242454996209658960741289984
121038673236052304885122859695720284551676364284416
1307909773783592726788040275308591958297845516834378345349120
203169716673423007848573790043533223319371983390134005562204298549339136
162097094762071097285740713589869499024657858875098611949364517836115641457617010688

4.4 Congolese drawings
The figures in Fig. 4.4 are a kind of Congolese drawings, a pattern that is found in
Africa. In page 826 of the same book, Audibert calls these graphs as P(N, 2N) graph(in this thesis, we will call this graph as P(n)), and writes down the number of Eulerianpaths up to N = 5. Using our proposed algorithm, we are able to enumerate the Eulerianpaths up to N = 15 (n = 15), which are shown in Table 4.4.

4.5 Ring graph
Ring graph R(n) belongs to multigraph, since there are multiple edges connecting
two same vertices in it. Some examples of Ring graph are shown in Fig. 4.5 for n = 1, 2
and 3. It is named Ring graph, since there are n rings for an R(n). Ring graph has an
Eulerian path, since there are exactly two vertices with odd degree. The results of ourexperiments on Ring graph are shown in Table 4.5.

Figure 4.5. Ring graph for n = 1, 2 and 3

29

30

Table 4.5. The Results for Ring graph R(n)
n
1
2
3
4
5
6
7
8
9
10
20
30
40
50

nodes
9
15
21
27
33
39
45
51
57
63
123
183
243
303

time
0.002855
0.004163
0.005660
0.006528
0.007305
0.009961
0.010719
0.0121090.013711
0.014786
0.019302
0.022078
0.025394
0.031448

number of Eulerian paths
6
36
216
1296
7776
46656
2799361679616
10077696
60466176
3656158440062976
221073919720733357899776
13367494538843734067838845976576
808281277464764060643139600456536293376

100
500
1000
5000
10000

603
3003
6003
30003
60003

0.045438
0.450163
1.603632
37.794911
150.083619

6.533186 × 1077
1.190214 × 10389
1.416610 × 10778
5.704951 × 103890
3.254647 × 107781

…

R (n)

R (n)

R (n+1)Figure 4.6. Simplifying R(n + 1) using R(n)Using mathematical induction, one can prove that the number of Eulerian paths in
R(n) is equal to 6n . For the base case n = 1, it is clear that the number of Eulerianpaths in R(n) is 61 = 6. Assume for n > 1, R(n) has 6n Eulerian paths. To prove thatR(n + 1) has 6n+1 Eulerian paths, at first we need to observe that every Eulerian path inR(n) starts from the leftmost edge and ends at the rightmost edge. Therefore we may
replace the R(n) graph inside an R(n + 1) graph as an edge, then we can simplify theR(n + 1) graph as R′ (1), which is shown in Fig. 4.6. This simplified graph R′ (1) has 6
Eulerian paths, in which one of its edge is actually R(n). Thus, in overall R(n + 1) has
6 × 6n = 6n+1 Eulerian paths.

30

Chapter 5
Conclusion
We have explained the algorithm for enumerating Eulerian paths in an undirected graph,
which can be used for both simple graph and multigraph. The algorithm is based on
simpath algorithm, which is introduced by Knuth in his book The Art of Computer
Programming [9] (exercise 225 in 7.1.4) and used for enumerating simple paths.
The proposed algorithm is much faster compared to a naive backtrack algorithm inmany cases, which is confirmed from our experiments. In our algorithm, we store theEulerian paths of the input graph in a multi-decision DAG, and once it is created, we
2
can retrieve any Eulerian paths in O(|E| · max( deg(v)2 ) ).
When using a frontier based algorithm, it is preferred to process the edges of the
input graph in an order such that the frontier size during the graph execution is always
fairly small. The reason is because the domain of the possible mate values of a vertex
is {0, s,t, f rontier}, for a starting vertex s and target vertex t of the Eulerian paths. If
the frontier size is big, then this domain size also becomes big, which in turn makes
the possible combination of mate values become bigger, thus reducing the possibilityof two nodes being merged. Therefore, the order of edges (variable ordering) is very
important in a frontier based algorithm. Finding a good variable ordering to be used in
our algorithm is still an open problem1 , and beyond the scope of this thesis.
In addition, one problem still remains. In our method we could not extract a set of
Eulerian paths satisfying a given condition from the constructed DAG, which we will
leave as future work.

1 For a Binary Decision Diagram (BDD) [12], finding a good variable ordering is proved to be in

NP-Complete [13]

Acknowledgements
First and foremost, I praise and thank Allah s.w.t, the most beneficent and the most
merciful, for giving me strength and ability to complete this thesis. I am indebted to mysupervisor, Prof. Shin-ichi Minato, for his advises and helps, which improved both myresearch life and this thesis. I am grateful to Prof. Zeugmann Thomas, for encouraging
and giving me motivation in doing research. I am also indebted all members of Laboratory for Algorithmics and JST ERATO Minato Project, who help me with invaluablesuggestions in my research. I express my gratitude to my parents and my family who
are living in a far away country, Indonesia, for always supporting me. Finally, I owe mydeepest gratitude to my wife, Arfenda Puntia Mustikawati, for her love and support inevery aspect of my life.

Bibliography[1] van Aardenne-Ehrenfest, T., de Bruijn, N. G. Circuits and trees in oriented linear
graphs. Simon Stevin 28, 203–217 (1951)[2] Tutte, W. T., Smith, C. A. B.: On unicursal pahts in a network of degree 4. American Mathematical Monthly 48, 233–237 (1941)[3] Brightwell, G. R., Winkler, Peter: Note on Counting Eulerian Circuits. CDAM
Research Report LSE-CDAM-2004-12 (2004)[4] Euler, Leonhard: Solutio Problematis ad Geometriam Situs Pertinentis. Comment.
Academiae Sci. I. Petropolitanae 8, 128–140 (1736)[5] Hierholzer, Carl: Ueber die Möglichkeit, einen Linienzug ohne Wiederholung undohne Unterbrechung zu umfahren. Mathematische Annalen 6 (1), 30–32 (1873)[6] Fleischner, Herbert: X.1 Algorithms for Eulerian Trails. Eulerian Graphs and Related Topics: Part 1, Volume 2, Annals of Discrete Mathematics 50, Elsevier pp.
X.1-13 (1991)[7] McKay, B. D., Robinson, R. W.: Asymptotic Enumeration of Eulerian Circuits in
the Complete Graph. Combin. Probab. Comput., pp. 437–449 (1998)[8] Hiroyuki Hanada, Shuhei Denzumi, Yuma Inoue, Hiroshi Aoki, Norihito Yasuda,
Shogo Takeuchi and Shin-ichi Minato: Enumerating Eulerian Trails Based on
Line Graph Conversion. Hokkaido University, Division of Computer Science, TCS
Technical Reports, TCS-TR-A-14-79 (2014)[9] Donald E. Knuth. Combinatorial Algorithm, volume 4A of The Art of Computer
Programming. Addison-Wesley, Reading, Massachusetts, first edition, 2011.
[10] Minato, Shin-ichi: Zero-Suppressed BDDs for Set Manipulation in Combinatorial
Problems. In Proc. of 30th ACM/IEEE Design Automation Conference (DAC’93),
pp. 272–277 (1993)

34

Bibliography[11] Audibert, Pierre: Mathematics for Informatics and Computer Science. ISTE Ltd.
pp. 832 (2010)[12] Bryant, R. E.: Graph-based algorithms for Boolean function manipulation. IEEE
Trans. Comput., 35, pp. 677-691 (1986)[13] Bollig, B. and Wegener, I.: Improving the variable ordering of OBDDs is NPcomplete. IEEE Transactions on Computers, 45(9):993-1002 (1996)

34