[MUSIC] All right, so now that we've seen a graph representation for maze world, let's actually turn that into some Java classes. So last week, Mia, talked to you about two core representations we can use for a graph, adjacency lists and adjacency matrices. And she showed you Java code for each. But it turns out that when you're actually going to represent a real world problem with the graph. And we wanna get beyond representing just integers as the vertex values, things get a little bit more complicated. So, even if you understood everything that Mia did last week, this week's assignment of implementing your own graph classes will still likely be pretty challenging. So, the goal of this video is to walk you through an example of taking a problem and turning it in to some Java implementation, of this graph and these graph algorithms. All right, so again, we're working with a problem that's slightly different from the problem that you'll be working with on your assignment this week. On your assignment this week, you'll be looking at cities, and roads, and intersections, and connecting them. And then finding paths which would be essentially driving directions from one point in the world to another. Here, we're just talking about a very constrained problem, which is this little two dimensional grid world, where the robot is trying to get from one place to the goal, the gold in this case. And our goal of this video is to turn this problem into Java classes, so that we can solve it. So in doing your class design, when you start within a blank slate and a problem to solve, there's some questions that you consider that can help you plan your classes. And what classes you're going to need, and what methods and data each of those classes should have. So, you want to start by thinking about what am I trying to do with this graph? What is the goal here of this graph representation? Another important question to consider is, what is the ratio of graph vertices to edges? That can help you decide between an adjacency list representation and an adjacency matrix representation. Another question to consider is how to I need to access the vertices in my graph? What is the user gonna be using in order to access the different nodes in the graph? We need to do those operations fast. And then finally a question you might wanna think about is, what properties, if any, about nodes and edges do I need to store in my graph? So, let's look at that first question. What am I really trying to do with this graph? Well, we know that we're trying to find pads to the graph, and in particular, here's the output of the program that I'm trying to write. I wanna be able to print out the maze, so there's the maze, the horizontal dashes are empty spaces, they're the nodes in the graph, and then the stars are the walls. Those are the nodes that don't actually appear in the grid at all. They're not in my graph. And then, I wanna be able to do depth research and print out the path that was found using those little Os. And then, I wanna be able to do breath research and print out the path that breath research found, again, using those little Os. So, that's my goal. So, I'll definitely need a class to represent the whole graph, the maze itself. And I know now what methods, or at least some of the methods I'm going to need to put into that class. I'll need a method to do depth research, a method to do breath research, and a method to somehow print out the graph. Now, these aren't the only methods that I'm gonna need, but they'll give me a starting point to think about, what do I need to put into this graph. So, the next question becomes what data do I need to store in this class? Well, obviously I need to store some representation of the vertices and the edges in this graph. So, that's our next question to consider. Should I use an adjacency list representation or an adjacency matrix representation? Which is better for this particular graph, and this particular problem? So take a minute to think about Which representation is better here? All right, hopefully you determined that an adjacent list representation is much better for this problem, because we've got a very sparse graph. Each node in our graph is going to have at most four edges going out of it, and that's an extremely small number relative to the size that this graph could potentially be. So adjacency lists are gonna make the most sense. So the next question becomes how? How do I put that adjacency list representation into my maze class? So one thing that we might think about doing is, Mia was using just numbers to represent each vertex in the graph, but, we're probably gonna need a little more information for this problem here. So instead of just using a number to represent each node because it's not even clear how we would number the nodes in this case. I am going to create a class that represents each node. And my class now is capable of storing some information about each node. Like it's row and it's column and the grid and perhaps the display character that it's gonna print out. When we do that printing of the graph with the path. And then I'll have some getters and setters for those internal variables. Now, how am I going to store those nodes in my maze class, such that I get both the node stored away, as well as some information about the edges? Well, we could just take that example that Mia used and extend it, so that instead of a HashMap linking integers to lists of integers, I'll have the HashMap linking MazeNodes to lists of Mazenode's. So, each MazeNode is going to go in as a key and then the list that's associated with in the hash map is the list of all of its neighbors. That will represent the edges. So this is good. This is fine. We can definitely use this implementation. There's just one problem, which is that if we think about how we're trying to access these notes. We're try to call duck first and breath first search, giving a start position and a goal position. But unfortunately the user of these methods is not going to know what Maze Node at the start position is. They're going to be representing a star position in terms of the row and column where the robot's supposed to start and the goal as well in terms of the row and column. So somehow, we need to get from a row, column representation to the node representation so that we can start doing our search to the graph. So we need quick access to translate a row and column into a node. And this hash set really isn't gonna do that because in order to do this we have to essentially iterate through all the keys and the hashmap, and look at each particular node to see if it matched the row and the column. That's gonna take order n where n is the number of nodes in our graph. That's not really a good thing, we'd rather do this in constant time. So instead of using this hash map to store the nodes, what I'm gonna do instead is use a two dimensional array to store these nodes. So now I can have instant access to anywhere in the grid, and if that position doesn't have a node, then I'll just store null in that two dimensional array. So, the key point here is that we want to make common operations that we know are gonna happen fast. But at the same time we don't need to go overboard here. So, do this within reason. Consider which operations are really important and try to make those fast. All right. So we can represent the nodes in this way. But now we've lost the edges, right? That hash map representation before was implicitly encoding the edges. We don't have that anymore. So, the question becomes, where should I put them back. I could put them back here in to the Maze class just where I lost them before, but there's another place I can put them. Since, I'm representing each node as an object, I can put them over here, in the MazeNode class, which is better well, not really one or the other. It's really up to you. This is just a sort of judgment call on your part. Which do you like better. That's a deciding decision you can make. The decision that I made is to put them over here in the maze node class. Each maze node is going to store a list of its neighbors, and you'll be able to access the nodes that are connected to a particular node from the node class itself, the maze in our class. All right! So that's really all there is to our class design, and now we've also got a whole bunch of other methods that help load the data from a file, that actually do the [INAUDIBLE] in-depth research, that do the printing, and so on and so forth. So we really want you to go check out our code. We've provided you all the code that we've done. This'll be a good example for you to follow. It has some parallels, to what you're going to be doing in your assignment this week. And what are you gonna look for when you're looking at this code? Well you wanna look for things like do the objects make sense? Do they kinda all hang together? Are the interfaces clean, are we not exposing private data or data structures that we shouldn't be? Is it easy and fast do the operations that you need to do a lot, and are methods short and relatively easy to read? And I will tell you now. I'll foreshadow the next video. Not all of these criteria are perfectly satisfied. There's some room for improvement in our code as it stands. So the next video, we're going to critic these codes and make some improvements.
