Hello, and welcome back. My name is William and today we will be looking over some source code for Tarzan's strongly connected components algorithm. Make sure you watch the video prior to this one explaining how the algorithm works. This video is dedicated only to source code. The source code I will be presenting during this video can be found@github.com slash William slash algorithms, there should be a link in the description. Here we are in the source code for Tarzan's algorithm to find strongly connected components.

You'll notice that this source code is written in the Java programming language. So to get started, let's have a look at the constructor for the class. And you'll notice that it takes a graph as an adjacency list as an argument. But before we get into the details of this actual algorithm, I want to show you how the algorithm actually works in practice, if you're going to executed. So if we look at the main method, you'll notice that here is how the algorithm is meant to be used. You set up the graph, and then you run the solver.

So to begin with, you declare a variable called n, which is the number of nodes that are going to be in the graph. Then you create the graph. So this initializes, the adjacency, list for n nodes, and we look at that create graph method up here. All the does is it initializes, the adjacency list, and then populates that with empty lists, so that we can be ready to add edges to our directed graph. So if you want to add an edge to the graph, and you would call this method, give it the graph, give it the directed edge, so from a node to another node, and then it will add that edge to the graph. So I believe this graph is the one from The slides the the very last graph, if I recall correctly.

So to actually find the strongly connected components, you create an object of the solver, you give it the graph, and then you run the solver on the graph. So, this is what actually finds the strongly connected components and this will return the the array of low link values, then what I do is I dump all of these inside a Multimap so we can know for each connected component, which are the nodes associated with that connected component. And then all I do is I print out which groups which nodes are part of. So you notice that I print that there are three connected components, and here are the nodes and what connected components they belong to. So that's how you use the algorithm Let's see what it's doing. So we already went over the constructor, which passed in a graph extracts the size of the graph, and caches the adjacency list.

As other instance variables, we have a boolean variable with tracks whether or not we have already solved the problem, then two variables to count the number of strongly connected components and assign an ID to each node, an array to track whether or not a node is on the stack, and then two integer arrays to track the ID of each node and the loading values of each node, and finally, a stack. So if we look at the SEC count method, it runs the solver if has not yet been solved and simply returns the number of strongly connected components. Get SCC s method also simply runs the solver if it has not yet been run, and returns the low link values array. Now let's look at the solver itself. So it returns if it's already been solved because we don't want to do more work than we need to.

Inside the solid method, I initialize all our arrays, I also filled the IDS array with the unvisited token. So we can know whether or not a node has been visited or not. Recall that the IDS array keeps track of the ID of a node, but it also keeps track of whether or not a node has been visited. So iterate through each node and if node AI is unvisited, then start a depth first search at node i finally, mark that we have solved the strongly connected components for this graph. Inside the depth first search method, it's almost exactly like The slides, so do the housekeeping stuff, which is like push the current node on the stack, mark the current node as being on the stack, give the the current node and ID and the loading value because the first time we're visiting it, then iterate over all the neighbors of this node.

Do a depth first search if the node we're going to is unvisited. On the callback, check if it's on the stack and minutes loading value with where we were just at. And back here after we've visited all the neighbors of the node, then we check if we're at the start of a strongly connected component. And if we are we want to pop off all the nodes associated with that strongly connected component which are on stack. So I start with first node and myself conditionals to pop until I return back to the start of that strongly connected component. And as I'm popping off nodes from the stack, I mark the node as no longer being on the stack.

And I also assign every node part of that strongly connected component to have the same ID as the node which started the strongly connected component. Just so that we know after the fact, which nodes belong to which strongly connected component, finally, increment the number of strongly connected components in case we are interested in that. And that's basically Trojans algorithm in a nutshell, guys, thanks for watching. Let me know if you have any questions. And like this video and subscribe for more mathematics and computer science videos. Thank you