Eulerian Path Algorithm | Graph Theory | Source Code

Key Takeaways

[Music] hello and welcome my name is William and today we're going to look at some source code for the oil aryan path algorithm this video follows off my last videos explaining the oil aryan pathaayiram itself so I highly recommend you watch those videos before watching this one there should be a link to that in the description below also all the source code I'm going to present today is available on github github.com slash William fizzy slash algorithms also link to that in the description so without further ado let's dive right in awesome here we are in the source code for the oil aryan path algorithm this code works by first instantiating this boil aryan path solver class and then calling a method to fetch the oil aryan path itself should it exists let's begin by taking a look at the class constructor in the constructor what you do is you pass in a directed graph to the algorithm as input and then the constructor verifies that you actually passed it in a graph that's not null and it also initializes a few variables including n the number of nodes in the graph and the path link to list before we go too far let's have a look at some of the instance variables for this class we already talked about n the number of nodes in the graph next we have edge count which we will compute dynamically from the input graph followed by in and out which are integer arrays to track the in and out degree of each node then we have path which is the Euler in path solution as well as a reference to the input graph so once you create an instance of this class there's only one public and method and that's get euler Ian path which does exactly what it says it will return to you an integer path consisting of the nodes you need to traverse to get a valid or they are in path or null if no path exists so there's a few things that get over there and path does which we'll cover step by step the first thing and they get where they are in path method is the setup method so let's have a look at that first all the set method does is loop through all the edges and increment the in-and-out array degrees as well as compute the number of edges in the graph which is being tracked by the edge count variable back to the ghetto Euler in path method the next thing is to check if the edge count is zero and return null if we don't have any edges to work with following this I call the graph has Euler in path method which verifies that our graph actually has no other in path because most graphs don't if the graph has or there and path method is also fairly simple what we want to do is make sure that no node has too many outgoing edges or too many incoming edges as well as ensure that there's the correct amount of start and end nodes for an Euler in path to exist the variables start nodes and end nodes keep track of how many nodes have either exactly one extra outgoing edge or one extra incoming edge for an Euler and path to exist there has to be at most one start and end node so when we're inside the for loop we have three conditions the first is to identify if the current node has too many incoming or outgoing edges which mathematically means that the difference between the in and out degree or vice versa is greater than 1 in this case return false because the path is impossible there will be no Euler in path in such an event the other conditions we care about our whether the current node might be a start node or an end node and if it is then we increment the start node and end node counters respectively the last step is to actually check that we have the correct number of start nodes and end nodes and return the boolean value returning back to the ghetto layer in path method the next thing and algorithm is to actually find the earlier in path now that we know one exists to do this we find a valid starting node and feed that as the first node to the depth-first search method so let's have a look at both of those we don't want to start our or therein path anywhere as we saw in the first video because this doesn't ensure that we find an Euler and path even though we know one exists the finds start no the method does exactly what it sounds like it looks for a node which is a valid starting node meaning a node with exactly one extra outgoing edge or in the case of an or there in circuit just any node with an outgoing edge it's important that we start at a node with an outgoing edge because our graph might contain singleton nodes that have no outgoing edges but another component in the graph might have outgoing edges which is where we really want to start if we are to find an order in path next up is the depth-first search method where things get interesting it turns out the depth-first search method is really short and could even be shorter but at the expense of readability remember that when calling this method the first note is the starting node which is the at variable in this method which if you haven't guessed it yet is the current node index we're currently at in essence what's happening in this method is that while the current node still has unvisited edges we're going to select the next node to explore and call the depth-first search method recursively each time we take an edge we decrease the number of outgoing edges for that node which means that eventually there will be no more outgoing edges for the current node and the loop will terminate once this happens we can add the current node to the front of the solution the key realization in this method I think is that you have to notice that the out array is being used as both a way of determining if there are any unvisited edges left at the current node as well as an index for reaching into the adjacency list to grab the next note to visit let's go back up to the get oil Arian path method once we finished executing the depth-first search the next thing to do is ensure that we found in order in path it could be the case that the graph is disconnected into multiple components in which case the correct thing to do is to return null because no Euler in path exists checking that the graph is disconnected is not something the graph has oil errand path method verifies and this is intentional because it's easier to do after running the depth-first search by ensuring that the solution actually has a size equal to edge count plus 1 the next thing I do before returning the solution which is optional is simply to empty the contents of the linked list into a primitive integer array just for convenience I do this because it's easier for the color to index an array than it is a linked list the rest of the file are just helper methods for creating a directed graph and adding directed edges to the graph I also provide two examples one from the previous slides and another that I made up I encourage you to look them over to understand how this program works thank you for watching please like this video if you learned something and subscribe for more mathematics and computer science videos I'll catch you [Music]