Hierholzer's Algorithm in Python

Introduction:

In this tutorial, we learn about the Hierholzer's algorithm in Python. The basic step of the Hierholzer's algorithm is to combine different circles to form a Euler circle. It starts from a random node. Then, it randomly moves towards neighbours along unvisited edges. Repeat these steps until you reach the starting node. The first circle results in the graph.

In graph theory, Euler's path is the path which visits all edges of a graph exactly once. The Euler path with the same vertical start and end point is the Euler circle, called an Euler diagram. We will use stacking and recursion to search for paths in the Euler diagram. Here, we give the Euler diagram and also print the Euler circuit. The Euler circuit is a path that passes through each graph's edge and ends at the starting vertex. The example is given below -

Example:

We discussed the problem of determining whether a particular graph represents the Eulerian graph. This tutorial discusses the algorithms for printing Euler orbits or circuits. The same problem can be solved using Fleury's algorithm. However, the complexity of Fleury's algorithm is greater than Hierholzer's algorithm. The time complexity is O(E*E) for Fleury's algorithm. We can find circuits or paths in O(E) using Hierholzer's algorithm, such as linear time. Here is the algorithm: ref (wiki).

Note that a graph has an Euler cycle if (1) all nonzero-degree vertices belong to a connected system. (2) The inner degree and outer degree of each corner are the same. This algorithm assumes that the given graph has an Euler circuit.

1. We need to choose a starting vertex, v. Then start from that vertex and follow the edge until you return to v. It is impossible to get stuck in a vertex outside v. This happens because when the orbit enters another vertex, then the inner degree and outer degree of each vertex must be the same. Vertex w must have an unused edge w. The tour created this way is a closed tour. But it does not cover the initial graph's vertices and edges.
2. When there is a vertex u which belongs to the current tour but whose adjacent edges are not part of the tour, start another path from u. It follows the use of edges until it returns to u and joins the tour that way to the previous tour.

So, the goal is to keep track of unused edges and remove them until they get stuck. Once we get stuck, we return to the nearest point on the current path with an unused edge and repeat the process until all edges are used. We can use another container to hold the last and final path:

Program Code:

Now, we are given the program code of Hierholzer's algorithm. Here, we use the Hierholzer algorithm in Python to print the Eulerian circuit in a given directed graph. The code is now given below -

Output:

Now, we compile the above code in Python, and after successful compilation, we run it. The output is given below -

0 - 1 - 2 - 0
0 - 1 - 5 - 3 - 4 - 2 - 0 - 3 - 5 - 0

The above code lists the number of edges for each vertex. This is unnecessary since we keep the names side by side anyway. We just removed the creation of the edge_count array. This algorithm replaces 'if edge_count[current_v]' with 'if adj[current_v]'.

The above code pushes the first or initial node into the stack twice. Although we collected the results correctly, the method needed to be clearer and more effective. We eliminate this problem by adding the next vertex into the stack instead of the current vertex. In the part of the testing algorithm, the beginning of the adjacency names "adj1" and "adj2" are slightly different. The potion has also been improved. The improved code is given below.

Program Code:

Now, we are given the improved program code of Hierholzer's algorithm. Here, we use the Hierholzer algorithm in Python to print the Eulerian circuit in a given directed graph. The code is now given below -

Output:

Now, we compile the above code in Python, and after successful compilation, we run it. The output is given below -

0 - 1 - 2 - 0
0 - 1 - 5 - 3 - 4 - 2 - 0 - 3 - 5 - 0