[APPLAUSE] >> All right, in the last support video we looked at code for finding the one-hop neighbors for nodes in graph that's represented as adjacency list as well as in adjacency matrix. But in your assignment you're going to have to write some code to generate the two-hop neighbors, so all the neighbors you can reach and not just one edge hop, but two edge hops. So what we're gonna do in this support video is give you some help with that task. Now spoiler alert. This is going to give away most of the code that you'll be writing in this part of the assignment, but it's also going to introduce you to a really cool trick for doing matrix multiplication for finding these two-hop neighbors. So if you don't want the spoiler of the code, but you just want that cool trick about the matrix multiplication you can jump to part two of this video. So by the end of these two parts you'll be able to write the code for generating the two-hop neighbors in both the adjacency list implementation as well as the adjacency matrix implementation of a graph. And you'll also be able to describe how matrix multiplication in an adjacency matrix representation can generate the two-hop neighbors for all of the nodes in the graph. So lets get started. Let's go back to our graph representation. Here's a graph. It's a fairly simple graph that you can see here. That's the graph example that we're going to be working with in these two videos. So our problem again on the assignment is to write a method that given a vertex say vertex 0 comes back with a list of all of the neighbors that you can reach in two hops. So not one, but two hops away. So if we start with that vertex 0 we can see that well we can't reach node 0 in two hops, but we can reach node 1 in two hops. We go down through node 2 and then up to node 1. We can't reach node 2 in two hops. We can only reach it in one because two hops and we go away from node 2, but we can reach node 3, and in fact we can reach node 3 in two different ways. We can go through node 2 down through the bottom, or we can go through node 1 up across the top, so there are two different paths from 0 to 3. So that's the problem that we're working with. Now our solution is going to be similar, but slightly different depending on our graph representation. So let's get started right away with our adjacency list representation. So here's our adjacency list representation of this graph. You can see that each node is an entry into this map, and the values of the map are just the lists of connected vertices. So we looked at the code for finding the one hop neighbors in the last support video, and it looked like this. And we saw that this code was actually almost trivial. It was extremely easy to find the one-hop neighbors using the adjacency list representation. Turns out that finding the two-hop neighbors is really not that much more complicated. So what you're going to do to find these two-hop neighbors is well you've already got a way to find the one-hop neighbors. Here it is. So instead of just returning the one-hop neighbors all you need to now do is from each of the one-hop neighbors just loop through them and find their one-hop neighbors. So the one-hop neighbors of the one-hop neighbors are the two-hop neighbors of the original node. So that's a pretty big start on your two-hop neighbor implementation for your adjacency list representation of your graph. So next let's go on to consider how you would do this for an adjacency matrix. So before we do that I want you to take a minute pause, and actually draw the adjacency matrix for this graph example here. All right welcome back. Hopefully this is the adjacency matrix that you came up with. You know that each row corresponds to neighboring vertices in the graph, so for example in row 0 we have a connection to vertex 1 and vertex 2, because we have edges from vertex 0 to vertices 1 and 2, but not to 0 and 3. Now let's look again at the code for generating the one-hop neighbors in this adjacency matrix representation. It was a little bit more complicated than the code for generating the one-hop neighbors in the adjacency list presentation, but it wasn't terribly difficult either. So what we did is we went to the row V for the vertex that we're looking for, and then we just looped through that row, and for every entry that we found that was greater than 0 we knew there was an edge to that vertex. And so we added it to our neighbors list, and in the end we just returned the neighbors list. That's the code that we looked at, but if you look at the starter code what you are going to find is that the code looks just a little bit different so it actually looks like this. So there's a change. Instead of that if statement we now have an inner loop, and that inner loop starts at 0 and it goes up to the value stored in the adjacency matrix at position v i. So my question for you that I want you to think about is what is this change doing? All right. So you see that we made this change. What in the world is this about? Well it seems like what we're doing is we're going into the adjacency matrix, and we're getting the value there and if that value is 1 we'll only add the neighbor once, but if that value is greater than 1 we're going to add that neighbor multiple times. So the question becomes why would the value in the adjacency matrix ever be greater than 1, and the reason is when we have multiple edges between nodes. So it's entirely possible the node graph we actually have two edges between say node 0 and node 1 in this case. And so the way we're gonna represent that in the adjacency matrix is we're just gonna change the value of that entry to represent the number of edges between that pair of nodes. So in this case we'd have a two between the vertices 0 and 1. And you'll see that this actually does happen in our row data, so sometimes there's a street that actually just makes a loop and there's an intersection here and an intersection here, and you can get from this intersection around this way and this intersection around that way, and we have two edges between those two nodes. So this is real world data here. And so what we want to do is for get neighbors is we want to count each neighbor the number of times that we can get to it from a particular node, so because we can get to vertex 1 twice following two different edges from vertex 0, vertex 1 is gonna go into that neighbors list twice. We're going to maintain this convention in our get two-hop neighbors, so if you can reach a two-hop neighbor via two different pods it's going to go into the two-hop neighbor's list twice. So let's go back to this original example that we were working with and talk about how to turn this get neighbors method into a get two-hop neighbors method. And again it's pretty straightforward. We already have the code that gets the one-hop neighbors, so now instead of just adding i as we did for the one-hop neighbors to our list to return what we want to add instead is the neighbors of i. The one-hop neighbors of i, and if you think about it you actually already got some code that will do that for. So it's just a matter of calling a method that already exists. So again here's your spoiler. This is a lot of the code that you're going to need in order to solve this part of the assignment.
