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.
Leo PorterAssistant Teaching Professor
Mia MinnesAssistant Teaching Professor
Christine AlvaradoAssociate Teaching Professor
