The Hierholzer's Algorithm Explained

Abstract

Since the beginning of time, people have gravitated towards trying to find the best paths in order to get work done in the most efficient way possible. As an example, if there are places a person has to go, they try to plan it in a way that takes the least amount of effort to get to each place. Ideally, there should be no overlap so, no extra work is done. Since this a very important idea, humans have created multiple methods in order to find this ideal path. From all the different methods, the ideal path can be easily found using an algorithm called Hierholzer’s algorithm. This is a revolutionary algorithm and it has been used in all facets of modern society from GPS services to networks. To understand the algorithm, its history and creation should be explored.

Background

Before the algorithm can be explained, the concept of Euler path and circuits need to be discussed. In 1700s, in the town of Königsberg, Prussia (current day: Kaliningrad, Russia), there were 7 bridges that connected this city together. These bridges in total connected 4 different land masses and its citizens would use all these bridges fairly regularly. From this situation, arose the idea in this community, on whether it was possible for a person to cross all these bridges in one pass while only crossing each bridge once. In 1735, the great mathematician Leonhard Euler, presented his idea on why this walk was impossible. He attributed each landmass to point and each bridge as a path. In this case there are 4 landmasses and 7 bridges. Below is the picture of the layout of the town created by Euler.

In this picture, the landmasses are labeled by upper case letters and the bridges are labeled by lower case letters. Below, the table mentions all the paths that connect to each point.

Point	Paths
A	a, b, c, d, e
B	a, b, f
C	c, d, g
D	e, f, g

From this, it was found that each point has an odd number of paths. Point A has 5 paths and points B to D have 3 paths. Euler found out that when there is an odd number of paths, there will be overlap and some paths need be passed again in order to go finish going through all the paths. This means, that in this scenario, it was impossible for a person to walk all these bridges in at one time while passing each bridge only once. This was the basis for graph theory. From this, the points are denoted as nodes and the paths are denoted as edges.

From this solution that Euler published, the Euler’s graph theorem was created. There are two concepts that come from this theorem; Euler path and Euler circuit. A Euler path is a path on an undirected or directed graph that where all edges are visited only once. A Euler circuit is a type of Euler path where the start and end node are the same. This means that, any node can be used as a start/end node. The basic rules for Euler’s graph theorem are summarized below (degrees mentioned are the edges that come in or out of a node):

A Euler path can be created when there are 0 or 2 odd degree nodes in a given graph
Euler circuit (cycle) can only be created when there are no odd degree nodes in a given graph
The graphs that don’t fall in the categories mentioned above, they have no Euler paths or circuits

Now that the basics have been discussed, the algorithm can be introduced. In 1871, Carl Hierholzer presented his paper on how to efficiently find a Euler path or circuit for a given graph. He only showed this to a few of his colleagues and unfortunately, he died in the same year. In 1873, one of his colleagues published this paper and from then, it was known as the Hierholzer’s algorithm. This algorithm made it possible to find the Euler path or circuit with a time complexity of O(E). In this time, as the number of edges increase, the running time will scale linearly. This algorithm was vastly superior to the Fleury’s algorithm where the time complexity of O(E2). In this time, as the number of edges increase, the running time will scale exponentially. Therefore, Hierholzer’s Algorithm is the most efficient way to find Euler circuit in a graph.

How To Use

To start, the conditions when this algorithm can work needs to be explained. As mentioned before, the degrees that a node has in a graph are important. Briefly mentioned before are the concept of degrees. A degree is either an incoming or outgoing edge from a node. These can be split into in-degrees and out-degrees. For a Euler circuit, this means the of all in-degrees and out-degrees of node needs to equal each other. For example, 1 in-degree and 1 out-degree added together will give an even degree and they are equal. This can be done for both undirected and directed graphs. So, if the graph passes these requirements mentioned before then, the algorithm can be can run. Below (written in Java) is how this algorithm can be implemented for an undirected graph for a Euler circuit.

Step 1

Initialize a graph and assign global variables.

Step 2

Create nodes (if doesn’t exist) and edges for created graph.

Step 3

Pick any node in the graph as the starting point (this will also be the end point). The code will randomly pick any node from the graph since a Euler circuit is possible for this graph.

Step 4

Now, after the graph has been initialized, the algorithm can be used. In this algorithm, from the starting node, a random edge is selected. Then, using the random edge, the program goes to the next node and that becomes the current node. Using the current and previous nodes, the edge that was used will be deleted. Doing this will help keep track of which edges have been used.

Step 5

Repeat step 4 until the current node arrives again at the starting node. When this happens, it means that a path has been completed. This is possible through recursion of the algorithm function.

Step 6

Now, once the starting node has exhausted all edges, it will pop that value out of the current path list and append it to the final list. Then, the next node in the current path list will be checked in the same way.

// Removes node from graph when all the edges have been used
// Moves the first element to the final_path list
// The second element in current_path becomes the current and starting node
private void removeNode(String nodeName) {
      this.current_path.removeFirst(); // Remove first element from list
      if(!this.current_path.isEmpty()) { // Checks if list is empty
            this.currentNode = this.current_path.get(0); // Makes current_path's first element the current node
            this.startNode = this.currentNode; // Current and starting nodes are the same
            this.counter = 0; // Resets counter so it can place elements in the beginning of the existing list
            this.final_path.add(nodeName); // The removed node is appended to the final_path list
      } else { // Executes when it's the last element in the final_path list
            this.final_path.add(final_path.getFirst());
      }
}

Step 7

Once all the nodes are checked to see all edges have been traversed, the algorithm is complete and the Euler circuit can be displayed.

// Runs the algorithm and posts the final Euler circuit path
public void printCircuit() {
      pickStart(); // Picks the starting node
      System.out.println("The Euler Circuit of this graph is: (Starting Node: " + this.startNode + ")");
      this.algorithm(); // Runs the algorithm function
      // Prints the Euler path in a pleasing format
      for (int index = 0; index < this.final_path.size(); index++) {
      	    if (index == 0) {
                System.out.print(final_path.get(index));
            } else {
                System.out.print(" -> " + final_path.get(index));
            }
      }
}

Example test code to run this algorithm is shown below.

import java.util.*;

public class algorithmTest {
     public static void main(String[] args) {
         hierholzer test = new hierholzer();
         
         // Adds nodes to the graph
         test.addNode("1");
         test.addNode("2");
         test.addNode("3");
         test.addNode("4");
         test.addNode("5");
         test.addNode("6");

        // Adds edges between two nodes
         test.addEdge("1", "5");
         test.addEdge("1", "6");
         test.addEdge("1", "3");
         test.addEdge("1", "2");

         test.addEdge("2", "3");

         test.addEdge("3", "4");
         test.addEdge("3", "6");

         test.addEdge("4", "6");

         test.addEdge("5", "6");

         test.printCircuit();
     }
}

Using the code above, this was a result of the code.

The Euler Circuit of this graph is: (Starting Node: 5)

5 -> 1 -> 3 -> 6 -> 1 -> 2 -> 3 -> 4 -> 6 -> 5

For a directed graph, the difference would be in the addEdge() and removeEdge() functions. Before, when two nodes were connected, there were two edges made: From first node to second node and from second node to first node. In a directed graph, there will only be one edge from first node to second node. Below are the changed functions.

public void addEdge(String Node1, String Node2) {
      LinkedList nodeList = this.graph.get(Node1);
      if(!Node1.contains(Node2)) {
      	nodeList.add(Node2);
            this.graph.put(Node1, nodeList);
      }
}

private void removeEdge(String Node1, String Node2) {
      LinkedList nodeList = this.graph.get(Node1);
      if(!Node1.contains(Node2)) {
            nodeList.remove(Node2);
            this.graph.put(Node1, nodeList);
      }
}

In Practice

Using this code and logic, an example is created below for each type of graph. The goal is to find the Euler circuit for the given graph. Shown below is, an undirected graph that can be used to test the Hierholzer’s algorithm.

Next, a table is created to check if the degrees of each node are equal to an even number.

Since the in and out degrees are even and equal, that means this graph can make a Euler circuit. Now, the algorithm can be utilized. First, randomly select any node from this graph. For this example, the node 5 will be selected. It will be denoted in green since it will be the starting/ending node.

Now, the algorithm will pick a random edge from node 5 and travel to a new node. After traveling to a new node, it will append that node number to a list called: current_path. Then it will keep looping the same function until it reaches the starting node. The nodes that been traveled to will be highlighted in blue and the edges that are used will be highlighted in green. Under each picture, the current_loop list will be shown.

The starting node, 5, has been reached. Now, since all the edges from node 5 are have been traveled to, node 5 will be taken out of current_path list and appended to the list: final_path. Next, the next node in current_path is node 6. The function checks whether node 6 has used all its edges. In this example, there are still 2 edges that have not been visited yet. This causes the function to create a new path. Each node from this loop will be appended to the current_path list. The new path is shown in red and the results are shown below.

After the new loop has been completed, the current_path will have 6, 1, 3, 6, 4, 3, 2, 1, 5. Each node will be checked if there are any missing edges. As shown in the diagram, all the edges have been visited so with each loop, the first element gets removed from the current_loop list and appended to the final list. At the end, the final_path list is 5, 6, 1, 3, 6, 4, 3, 2, 1, 5. This is the Euler circuit for this undirected graph. A circuit diagram is shown below.

This graph can be used in the directed graph example. The objective of this is to make a directed graph into a Euler circuit using the same Hierholzer’s algorithm. For this example, the node 2 will be selected as the starting/ending node. As mentioned before, any node can be selected when the graph is a Euler’s circuit. The starting node will be denoted as green.

The same procedure as before will be used. The nodes that been traveled to will be highlighted in blue and the edges that is used will be highlighted in green. Under each picture, the current_path list will be shown.

Now, the first path has been completed, the function will check if node 2 has any remaining edges. Since it doesn’t, node 2 is removed and appended to final list. The function will move node 1 next and the function finds that there are edges that are not used. The new path is shown in red and the results are shown below.

The second path has been completed. Now the current_path list has 1, 5, 6, 1, 3, 2. Since node 1 has exhausted all the edges, that one is sent to final_list. Next, node 5 has no extra edges so it’s sent to final_list. Final_list is now 2, 1, 5. At node 6, there are unused nodes so, another path starts. This path will be colored yellow and results are shown below.

The third path has been completed. Now the current_path list has 6, 4, 3, 6, 1, 3, 2. Since node 6 has exhausted all the edges, it’s sent to final_list. After the function goes through all the remaining nodes, it is determined that no more nodes exist. The rest of the current_path is sent to the final_list. The Euler circuit for this directed graph is 2, 1, 5, 6, 4, 3, 6, 1, 3, 2.

General Use

Now that the algorithm has been thoroughly explained, why are Euler path or circuits so important? In the modern world, these are very important pathfinding concepts. They are used in many different jobs from the mail service to networks and even Google maps. In all of these scenarios, the ideal path needs to be found where there is no overlap. When there is overlap or when a path is taken more than once, this adds to the running time of that function. When there is a small number of edges, this doesn’t matter much. However, as the graphs and edges become more complicated, it adds up and leads to a slower solution. Also, the solution that is created is not the ideal case.

An example where this algorithm is valuable is garbage collection systems. In a garbage system, there are places the garbage truck needs to go to each time, pick up the garbage and then head back to the garbage plant. Using the Euler circuit idea, the garbage plant is the starting and ending node and the places where garbage is are the rest of the nodes. The edges between the nodes are the paths the garbage truck has to take in order to get to each of these locations. Ideally, the paths should only be traversed once so they the company can save on time and fuel cost for the truck. Using the Hierholzer's algorithm, the ideal Euler circuit for the garbage truck can be found.

Another example is a subway network. A subway network is an underground train network where trains move from stop to stop. Using graph terms, a subway station can be denoted as a node and the connections between the stations can be denoted as edges. So, in this network, the operators have to find the ideal paths between all these nodes and try to use all the edges to their advantage. All the edges should be used because this help spread the trains across the network so there is no overlap or waste. If there are too many trains near each other, this will cause traffic and decrease efficiency in the system. The Hierholzer's algorithm can be used to create the most efficient paths where all the nodes and edges are used.

Conclusion

The Hierholzer’s algorithm is an important algorithm that changed the way Euler paths and circuits have been found in graphs. Euler paths and circuits are used extensively in modern society. They have used in many jobs from garbage collection systems to GPS pathfinding of Google and Apple maps. Using Hierholzer’s algorithm makes it easy to find these paths and circuits. Even though it’s an older algorithm and was created before even computers were invented, it works perfectly and efficiently. It has a great running time which makes it an ideal algorithm to implement in a real-world scenario. Overall, an essential algorithm in modern computer science.

References

Inigo, Maxie, et al. “6.3: Euler Circuits.” Mathematics LibreTexts, Libretexts, 5 Sept. 2021, https://math.libretexts.org/Bookshelves/Applied_Mathematics/Book%3A_College_Mathematics_for_Everyday_Life_(Inigo_et_al)/06%3A_Graph_Theory/6.03%3A_Euler_Circuits.

Musings, Maths and. “Solving the Königsberg Bridge Problem.” Medium, Cantor's Paradise, 22 Mar. 2020, https://www.cantorsparadise.com/solving-the-k%C3%B6nigsberg-bridge-problem-bda0ab08d831.

Nazhimidinov , Nurgazy July. “Hierholzer's Algorithm.” SlayStudy, 12 July 2021, https://slaystudy.com/hierholzers-algorithm/.

Paoletti, Teo. “Leonard Euler's Solution to the Konigsberg Bridge Problem.” Leonard Euler's Solution to the Konigsberg Bridge Problem | Mathematical Association of America, https://www.maa.org/press/periodicals/convergence/leonard-eulers-solution-to-the-konigsberg-bridge-problem.

Patel, Jaival. “Eulerian Cycles: Why Are They so Unique, and Are They Significant to Us in the 21st Century?” Medium, Towards Data Science, 14 Aug. 2021, https://towardsdatascience.com/eulerian-cycles-why-are-they-so-unique-and-are-they-any-significant-to-us-in-the-21st-century-3ca489af585c.

Reddy, Ramprakash. “Hierholzer's Algorithm for Directed Graph.” Ramprakash Reddy, 15 Feb. 2017, https://ramprakasharava.wordpress.com/2017/02/15/hierholzers-algorithm-for-directed-graph/.