Hello everyone and welcome back. My name is William and today we're talking about how to algorithmically find oil, Larian paths and circuits behind graphs. So this video is going to build off the concepts of my last video which talked about the existence of Euler in paths and circuits in graphs. So absolutely make sure you watch that video because it's essential to the concepts I'm going to talk about in this video. There should be a link to that in the description below. So finding always Larian paths and or they're in circuits are actually very similar problems for both directed and undirected graphs.

If you have an algorithm that finds an Euler in path finding an oil arian circuit comes for free. All you need to do is feed the graph with The Euler in circuit into the oil area and path algorithm and outcomes the oil arian circuit. For that reason, today we'll be looking at an algorithm that finds an Euler path on a directed graph. So the first step to finding an Euler path is to verify that one exists because maybe it's impossible to find an Euler path that traverses all the edges of your graph. And it's good to know that before you actually find your they're in path. So recall that point or they're in path to exist at most one vertex has out degree minus in degree equal to one and at most one vertex has in degree minus out degree equal to one and all other vertices have equal in and out degrees, we're going to count the in and out degrees of each node by looping through all the edges.

We'll be needing two arrays, which I've called in and out to track the in and out degrees of each node. So for each other increment the integral of a node if a node has an incoming edge and increment the out degree if it has an outgoing edge, and so on for all the other edges. Once we've verified that no node has too many outgoing edges, or too many incoming edges, and there are just the right amount of Start and End nodes, we can be certain that our oil arian path exists. The next step is to find a valid starting node because we can start the algorithm at any node we choose necessarily. node one is the only node with exactly one extra outgoing edge, so it's our only valid starting node. Similarly, node six is the only node with exactly one extra incoming edge so it will end up being Our ended node.

Note that if all in and out degrees are equal, then we have an oil arian circuit. And we can choose to start the algorithm at any node which has a nonzero degree. So we have everything we need to find an oil arian path. Let's see what happens if we try and do a naive depth first search to traverse as many edges as possible until we get stuck. Let's begin at our starting node and execute a random depth first search. Let's take a write another write up, down diagonally up diagonally right and right again, you'll notice that even though we started at the correct starting node, and that we knew in oil arian path existed, and furthermore, that we did end up at the correct end node that we still do not find the valid or Larian path since we didn't traverse all the edges.

So what's going going on. Well, what's happening is that we're doing our depth first search wrong, we need to modify the depth first search algorithm to force the depth first search to visit all the edges of our graph. To illustrate this, consider this simpler smaller graph. Suppose we start our depth first search at node zero and try to find an oil arian path. Suppose we take the edge to the right, then suppose the depth first search takes us right again, this causes us to accidentally skip the edges going to node two and back which we know will need to be part of the oil arian path solution. For now let's not worry about it and keep executing our depth for search.

So once we get stuck, meaning the current node has no unvisited outgoing edges, we backtrack and add the current node to the solution so far gets added to the solution and we returned to the node we were just at. We are stuck in Because node three has no outgoing edges that are unvisited, so we add three to the front of the solution and backtrack when backtracking if the current node has any remaining unvisited edges, that is white edges, we follow any of them calling our depth first search method recursively to extend the order and path, so we follow the edge up to node two and then there's still another edge going downwards. So we take that one, two, now we're stuck again because there aren't any unvisited edges anymore. What we do is we backtrack and add the current node to the front of the solution.

Effectively we do this until we return to the start node and the recursion unwinds. So in summary, how we forced the depth or search to take all the edges is to keep taking unvisited edges on the recursive call back until no unvisited edges remain. Coming back to the previous example. Let's restart the algorithm. But this time, let's track the number of unvisited edges we still have left to take at each node. In fact, we have already computed the number of outgoing edges for each node in the out array, which we can reuse, we won't be needing the inner array anymore.

Once we validated that an oil arian path exists, so we can ignore it. Let's begin at the starting node once again. Now one thing we're going to do slightly differently is that every time an edge is taken will reduce the outgoing edge count for that node. Doing this will enable us to know when a certain node has no more unvisited edges. So let's just follow the same path we had last time until we get stuck. So now we are where we were last time, but we're not going to terminate the algorithm just yet.

Instead, we're going to backtrack because we're stuck and there are no more outgoing edges to take from node six. One way to know this without looking at the graph is to check whether the outer array at index six has a value of zero and it does. So let's backtrack and add six to the front of our solution. Now we are at node four and node four has remaining unvisited edges. Those are the white edges, which we still need to take. So we call our depth first search method recursively and follow all the unvisited edges for notes for similar situation at node three, and node one and node two.

For node two. We're going to take the edge going to the right, which brings us back to node four, but this time there are no more unvisited edges at node four. So what do we do we backtrack and add four to the front of our story. solution now we're at node two and node two still has an unvisited edge since the outer array at index two is not equal to zero. So what we do is we follow that unvisited edge, which brings us back to node two and node two now has no more unvisited edges, so we backtrack and add to the solution and we're back at node two, and we backtrack now we're at node one, and backtrack from node one. Now we're at node three, and so on since all the edges have been visited, and at this point, we're just going to unwind the stack and add the current node to the front of the solution.

I'll let the animation play and that's how you find an oil arian path on a graph in terms of the time complexity required to find or Larian path. We know that it has to be big op. The reason is that the capital As we're doing to compute the Euler and path are all linear in the number of edges. Think about computing the internet degrees, or the depth for search. Both of those only take big O of a time. So the whole thing is linear in the number of edges.

And now let's have a look at some pseudocode. To find an oil arian path, let's have a look at some of the variables we're going to need. The first three here are inputs to the algorithm, which are n, the number of nodes in the graph, and the number of edges in the graph. And lastly, g the graph itself stored as an adjacency list. Then there's the in and out arrays I talked about earlier to track the in and out degrees of every node. Lastly, there's a variable called path, which is a linked list, which is going to store the oil arian path solution.

You can also use An array or some other data structure to store the solution, but I find that a linked list simplifies the code to actually find an Euler path on our graph G we're going to call the find or Larian path method. The first thing we want to do is verify that an oil arian path exists. To do that, we first need to count the in and out degree of each node. And once we know that we can verify that the graph is a good candidate for nor Larian path. So here we are looking at the methods which count the in and out degrees of each node. And verifies that Euler in path can exist.

The count in and out degrees method is very simple. Simply loop over all the edges in the graph and increment the in and out degree arrays for incoming and outgoing edges. The graph has Euler and path method checks all the preconditions For an oil arian path, we're going to keep track of the number of start nodes and n nodes that we encounter. A start node is a node with one extra outgoing edge and an end node is a node with one extra incoming edge. If at any point we encounter a node which either has more than one extra outgoing edge or more than one extra incoming edge, we know that this graph is not only Larian, and we can return false immediately because of symmetry I believe you only need one of these checks. But to be explicit, I put both conditions there.

Next up I check if the current node is a start node or an end node. You cannot be a start node and an end node which is why this is an else if clause. The last thing to do is check if we have a valid number of start nodes and end nodes for our path either are no designated Start and End nodes that is the oil area and circuit case which is also an earlier in path or there are exactly one start node and one and notes. Coming back to the main method. The next step is to find that starting node and perform a depth first search to actually find the order they're in path. Let's begin with finding the starting node.

We're going to start by assuming that the start node is node zero, although this will likely change in the future. Since we know that at this point, our graph is an oil arian graph. This means that if we encounter a node with one extra outgoing edge that this node must be the unique starting node and we can return that nodes index immediately. Otherwise, we just want to ensure that we begin on a node with an outgoing edge. Our default node nodes zero might not have an outgoing edge. In fact, this check prevents us from Starting the depth first search on a singleton node, then return the start node after the the depth research method is where things start to get interesting.

This depth first search method takes one argument and that is the current node. We're at the while loop in the depth first search loops while the current node still has outgoing unvisited edges. It does this by looking in the outer array at the current node and checking if there are still outgoing edges. The next line selects the next unvisited outgoing edge from the current node from our adjacency list. It also decrements the number of outgoing unvisited edges from the current node. So if you haven't caught on already, the outer array is currently serving two purposes.

One purpose is to track whether or not there are still outgoing edges and the other is to index into the adjacency list to select the next outgoing edge. This assumes that The adjacency list stores edges in a data structure that is indexable in constant time, just like an array. If not, say you're using an adjacency list composed of linked lists, then you can use an iterator to iterate over all the edges. Once we've selected the next unvisited edge, we visit that edge by calling the depth first search method recursively. Once we exit the loop, append the current note to the front of the solution. Returning back to the main method, the last thing we need to do is check that we have actually found the correct number of edges for an order in path.

It might be the case that our graph is disconnected and we found an Euler and path on one of the many connected components of our graph, in which case it's impossible to actually have an order in path so we return null in that case, otherwise, we simply return our path. Alright everybody. Thank you for watching. As always, you can find a source code on github@github.com slash Wm is slash algorithms there should be a link in the description. Please give this video a thumbs up if you learn something and subscribe for more mathematics and computer science videos.