[APPLAUSE] >> So one of the big problems when working with real data is knowing whether or not your solution is correct. So there's a real temptation when you start working with a big data set. You start writing some code for it, you start writing the code and, of course, everyone runs into bugs. So your code doesn't compile initially or might not run correctly. You might get a null pointer exception. But eventually your code is gonna run and you're going to get an output from that. And is it right? Well, for you to figure out whether or not it is actually right or not it's often best to come up with some small sample problems that you can work through on your own and then test your code to make sure that your code comes up with the same answer. And then you can feel more confident about the code's correctness. So by the end of this video, I hope you recognize the value of small examples in testing your code. So let's think about this real data piece. So this is a map of San Diego. And if you think about the graph data there, there's a lot of data, right? For all the roads that connect within the City of San Diego. And if I ran a search, and this is Google Maps, if I ran a search within Google Maps, and asked, what's my fastest route from UC San Diego to the San Diego Zoo, it's gonna give me back this route. And, I actually know San Diego pretty well, and this is actually probably the best route. But there is this real question. If you didn't know San Diego really well, how do you know that's the shortest? Is this really the best route? Well, what you want to do is come up with some small sample cases. And what I have here is an example problem. This is a smaller map than your real data set is gonna look like. And this is the one that's actually included in the project write-up. But when both Christine and I started this project, we both did the same thing in parallel, which was come up with small sample problems in order to try to check your own work. This is one of those sample problems. So, with this sample problem I can look at this problem and know properties of it because, it's, again, small. So let's try to do just breadth-first search on this. So I'm gonna start at 1,1, and I'm going to go to 8,1. And what's my breadth-first search gonna get me? What it should give me as a result is it should give me a path from 1,1 to 4,1, to 7,3, to 8,-1. That's the shortest, the fewest number of stops, which is what breadth-first search will give you. Now that I know that, for this simple problem what I want to do then, is have my code come up with the same answer for the same problem. And the first step to do that is to convert this graphical representation of it into data that we're gonna be able to use. And this is actually within your project folder under data/simpletest.map. But before we get into the details of how to convert that, let me do a quick example of us actually running this to see how well the code works. So what we're gonna do is we're actually just gonna try to run this in our code. We're going to take the example that we already worked, we're gonna pull in that graph into our code and then we're gonna actually execute a breadth-first search and see if it comes up with the same answer as we expect. So diving into the code itself, I've written this class called MapTester and the first five, six lines of this is code that we provide you as part of the starter code. I'm gonna essentially create a map and pull in the initial data from a map file. So let's walk through those steps. So first, we're going to create a map using the MapGraph constructor. And then, we've written this utility class called GraphLoader, which allows you to load in a road map just by providing that map file. And we'll talk about the structure of that map file in just a second. Now, this class we have written for you to essentially do the parsing, but it is gonna call your methods within MapGraph. Which are gonna build the map itself, and that's your responsibility as part of this project. After we pull in this map, I'm gonna gonna do two things just to test to see whether or not my small set is actually loaded in properly. I'm gonna print out the number of vertices, and then I'm gonna print out the number of edges, and then I'm gonna call in my solution code, the breadth-first search. And I'm gonna feed it a starting point of (1.0,1.0) and a destination point of (8.0, -1.0). And that's what we did in our simple example that we just worked through. And then what I'm hoping to see once I've got that route, I'm gonna print back out that route and it should match what we did by hand. So, let's try this. Let's run this. And first off, let's focus in on the number of nodes and the number of edges. So in our sample graph there are actually nine nodes. And that's exactly what it says here we got loaded. There are 11 undirected edges which is really 22 directed edges. So that actually makes sense, too. And then when I look for the breadth-first search path that it finds, it finds me a path from 1.0,1.0 to 4.0,1.0 to 7.0,3.0 to 8.0,-1.0. And this is exactly what we expect to find based on having worked through this example by hand. So let's go back and look at the structure of how we make these .map files so that you can create your own test cases yourself. All right, so what we saw by running our code on our example was that it actually produces the same result that we worked through by hand. So we found that same path from (1,1) to (4,1) to (7,3) to (8,-1). And that's fantastic. So how do I take that graphical representation that I have here on the left and produce an example that I can actually work with within my code? To do this, what you're gonna do is create a file just like this, where the format is very particular, make sure you follow this format exactly. You're gonna have a start lat lon, followed by an ending lat lon, followed by a street name, and followed by a streetType. And that is how you denote an edge. And that's an edge between the starting location and the end location. And it's directional, so if you wanna have an undirected edge from 1,1 to 4,1, you'd actually have to reverse it, to have it both be a start on the end, and then reverse the end to now be the start. So you do 1.0,1.0 to 4.0,1.0 and then 4.0,1.0 to 1.0,1.0. And this is how you are going to express these edges when you make these examples. Now, I strongly encourage you to try to do one of these examples on your own. So come up with an example on your own, do the graph by hand, and then convert it into this kind of file and pull it into your own data set. And this is useful for a couple of reasons. The first is, again, it's a great way to test to make sure your code is actually producing the right result. And the second reason it's great is, it's an incredible morale booster. It's really satisfying when you work through something by hand, and you see your code find the exact same right solution. So again, I hope you do this on your own.
