Find Euler Tour

Introduction

Let G = (V, E) be an undirected, connected, simple graph. The goal of the project is to find if an Euler tour exists for given undirected, connected, simple graphs, and to print such a tour, if they do indeed have one. Here, I have described the algorithm used, the run-time complexity analysis of the algorithm, and result analysis of one of the given input graphs.
Note that an Euler tour in an undirected graph is a tour that traverses each edge of the graph exactly once. An instance of an Euler tour can be seen in the figure below.

Euler tour found for one of the input graphs

Algorithm

The algorithm is simple (See Algorithm-1). Given a graph in the form of adjacent list using a text file, I, the algorithm first converts the text input into a graph, G, in the form of adjacent list using Create-Adjacent-Lists. We, then, check if an Euler tour exists in the given graph using Check-Eulerian. Finally, after verify that an Euler tour exists in the graph, the tour is found using a method called, Find-Tour. Note that adjacent lists refer to an array of linked lists in code.

Algorithm 1: EULER-TOUR(I)
// Convert text input into graph
G ← Create-Adjacent-Lists(I)
// Check whether an Euler tour exists for the given graph
eulerian ← Check-Eulerian(G.V)
// If an Euler tour exists, find it, else return null
if eulerian:
   tour ← Find-Tour(G)
   return tour
return ∅

Note that, for implementation purposes, Create-Adjacent-Lists and Check-Eulerian have been merged together as both of them require iterating through each vertex, v ∈ V, of the given graph, G(V, E). Let’s call this new merged algorithm as Mod-Create-Adjacent-Lists that takes the text file as input and returns back the outputs both the graph in the form of an adjacent list and whether an Euler tour exists in the graph. Mod-Create-Adjacent-Lists replaces the first 2 lines in Algorithm-1.
Now, Algorithm 2 describes how Mod-Create-Adjacent-Lists works. We go through each line of the input text file. The first number in each line is the source vertex and the numbers after it are the vertices with which it forms edges. The vertices after the source vertex are stored in a linked list one-by-one. Since, the vertices are in an ascending order in the text file, we will have them in a decreasing order in the linked list. For every vertex after the source vertex, a degree counter is incremented by 1 and hence finding the degree of the source vertex. We then check whether the degree of the source vertex is even to verify that an Euler tour may exist for the given graph. If degree of the source vertex is odd, we immediately break out of the loop as an Euler tour cannot exist in the graph and there is no point in continuing to create the full adjacent list.

Algorithm-2: MOD-CREATE-ADJACENT-LISTS(I)
// Initialize G as an array for linked lists
eulerian ← TRUE
// Iterate through each line of text input
for line ∈ I
   // Initialize degree of each vertex as 0
   degree ← 0
   src ← line[1]
   // Iterate through other adjacent vertices and increase degree
   for i ∈ (2, length(line))
      if line[i] is a number
         Push line[i] to G[src]
         degree ← degree + 1
   // Check if degree is odd
   if (degree is odd)
      eulerian ← FALSE
      break
return G, eulerian

Let’s talk describe the working of Find-Tour that actually extracts the Euler tour present in the given graph. We start with the first vertex, v = 1, and add it to the tour. We start a loop to visit all the edges in the graph and find our Euler tour. At each iteration, we visit the first edge, (v, w), of the vertex, v, according to the adjacent list of v, G[v]. After visiting the edge, we delete all instances of that edge from the array of adjacent lists. We, then, update the value of v with the value of w and add v to the tour. Since we are deleting edges from the adjacent lists, our graph will become empty when we complete our tour and the algorithm will terminate. The same can be seen in Algorithm-3. Note that an edge, (v, w), will have 2 instances in the graph: one in the adjacent list of v and the other in the adjacent list of w.

Algorithm-3: FIND-TOUR(G)
// Assign the first vertex as the start vertex
v ← 1
// Add the first vertex to the tour
tour ← v
// Continue until all edges have been visited
while G[v] ≠ ∅
   // Visit the adjacent vertex
   w ← G[v].head()
   Delete edges (v,w) and (w,v)
   // Assign w to v and add it to the tour
   v ← w
   Push v into tour
return tour

Time Complexity Analysis

The time complexity of the entire project can be analyzed by studying Algorithms 2 and 3. There are around 5 commands pertaining to initialization and |V| commands to initialize the graph as an array of linked lists. In Algorithm-2, we have 2 loops: an outer and a inner loop. We will analyze the run-time complexity of Algorithm-2 is in terms of edges. In Algorithm-2, we essentially go through each element of the adjacent list. A graph represented in the form of adjacent list contains 2 instances of every edge and hence has 2|E| elements. If a graph contains an Euler tour, we go through the entire adjacent list otherwise we terminate before. This gives us a lower bound run-time complexity of Ω(1) pertaining to the immediate termination case mentioned before and an upper bound run-time complexity of O(|E|) corresponding to running all the 2|E| iterations. Hence, we can attribute a tight bound of Θ(|E|) on the run-time complexity of Algorithm-2. Since commands related to reading an input file do not have to be included in count of operations, the outer loop only executes 3 constant-time commands per iteration excluding the 2 extra constant-time commands break out of the loop if the graph does not contain an Euler tour. The inner loop only executes 1 constant-time command per iteration for counting degree of a vertex.

In Algorithm-3, we use a loop to go through each edge, (v, w), in E. Hence , the loop runs |E| times. Each iteration 4 operations are executed: 2 constant-time operations, 1 operation to push a vertex into the linked list storing the tour, and 1 deletion operation. The push operations executes 4 constant-time commands each time it is called. Hence, each iteration of the loop executes 6 constant-time commands plus commands needed for deletion. The deletion operation is used in the loop that searches for the element to be deleted in a linked list corresponding to a vertex, v. If the element is at the head of the linked list, then takes 6 constant-time operations for deletion. Otherwise, it takes 2 additional constant-time operations to the find the next element in the linked list. Since there can be a maximum of (|V|-1) elements in any linked list, it would take a maximum of 2(|V|-2) operations find the last element. Hence, deletion of the element in the linked list would take a total of 2(|V|-2)+6 operations and this would be the maximum number of operations for deletion. We get a lower bound of Ω(1) and upper bound of O(|V|) on the run-time complexity of deletion. With deletion happening at each iteration, we get a lower bound of Ω(|E|) and upper bound of O(|V||E|) on the run-time complexity of Algorithm-3. Hence, we can say run-time complexity of Algorithm-3 is Θ(|V||E|) and the overall algorithm is also Θ(|V||E|) as Algorithm-3 takes Θ(|E|) time.


Results

Let us analyze the execution of the graph given in In1.txt. The algorithm would start by creating the adjacent list while simultaneously checking whether an Euler tour exists in the given graph. Since, the 4th vertex has an odd degree, the algorithm would terminate printing out that an Euler tour does not exist for the given graph and total time taken for execution in seconds. It would also generate suitable output files.
Since the code terminates early, we only have deal with counts of vertices pertaining to degree counting of each vertex. There are no commands executed on an edge in Mod-Create-Adjacent-Lists as only deletion is performed on an edge which is done in Find-Tour. Hence, commands executed on any edge is 0. For vertices {1,2,3,4} , we can count 3 commands for the outer loop in Algorithm-2 and commands equal to the degree of the vertex. For the 4th vertex, additional 2 commands need to be counted for breaking out of the loop. For vertices 5 and 6, no commands are executed as we break out of Mod-Create-Adjacent-Lists and terminate the algorithm. The actual calculations for vertices 1 to 4 have been illustrated across each of them below where output files: A.txt and B.txt have been printed.

A.txt:
0
B.txt:
Vertex 1: 5=3+2
Vertex 2: 7=3+4
Vertex 3: 5=3+2
Vertex 4: 8=3+3+2
Vertex 5: 0
Vertex 6: 0


Edge (1, 2): 0
Edge (1, 3): 0
Edge (2, 4): 0
Edge (2, 5): 0
Edge (2, 6): 0
Edge (3, 4): 0
Edge (4, 5): 0
Edge (5, 6): 0

Maximum number of operations charged to any single vertex is: 8
Maximum number of operations charged to any single edge is: 0
Total number of operations is: 39


Future Work

Every project can be improved in some or other way so take a look at the issues I have added for the project on my GitHub. One of the main things bothering me about the project is that even though abstract algorithms offer Θ(|E|) time complexity for finding an Euler tour, I have not been able to find a way to practically implement the algorithm in Θ(|E|) time. If you know of a way to do the same or know why we can’t, I will love to have a discussion with you, please do contact me.


GitHub

The source code for my implementation can be found here.

%d bloggers like this: