0:00

[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.

Â 0:50

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?

Â 2:11

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.

Â 2:49

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.

Â 3:13

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?

Â 3:39

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?

Â 4:08

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.

Â 4:45

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.

Â 6:35

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.

Â 6:49

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.

Â 7:40

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?

Â 8:19

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.

Â