Hello and welcome my name is William and today we're going to look at some source code for the oil arian path algorithm. This video follows off my last videos explaining the oil arian path algorithm 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 Piazza 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 arian path algorithm. This code works by first instantiating this we Larian path SolidWorks class and then calling a method to fetch the oil arian path itself should it exist. 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 pass in a graph. That's not no and it also initializes a few variables including n, the number of nodes in the graph and the path linked 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 method and that's get or Larian 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 know if no path exists. So those are few things that get Euler and path does, which we'll cover step by step.

The first thing in the Get over there and path method is the setup method. So let's have a look at that first. All this 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 get 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 earlier in path because most graphs don't. The graph has Euler 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 or Larian 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 Euler and path to exist there has to be at most one start and then 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 one in this case, return false because the path isn't Possible there will be no oil arian path in such an event. The other conditions we care about are whether the current node might be a start node or an end node.

And if it is, then we increment the start node and node counters respectively. The last step is to actually check that we have the correct number of certain nodes and then nodes and return the boolean value. Returning back to the get or they're in path method, the next thing and algorithm is to actually find the earlier in path now that we know when 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 out or they're in path anywhere, as we saw in the first video, because this doesn't ensure that we find an Euler path even though we know one exists. The find start node method does exactly what it sounds like.

It looks for a node which is a valid starting node means A node with exactly one extra outgoing edge or in the case of an or Larian 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 open path. Next up is the depth or search method where things get interesting. It turns out the depth research 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 First search method recursively. Each time we take an edge, we decrease the number of outgoing edges for that note, 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 point 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've finished executing the depth first search, the next thing to do is ensure that we found an oil arian 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 no because no No order and path exists. Checking that the graph is disconnected is not something the graph has Euler and 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 one. 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 caller to index an array than it is a length to list the rest of this 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 and Mathematics and Computer Science videos. I'll catch you next