Project: Programming Assignment Walkthrough

Loading...

From the course by University of California San Diego

Advanced Data Structures in Java

891 оценки

University of California San Diego

Advanced Data Structures in Java

891 оценки

Course 3 of 5 in the Specialization Object Oriented Java Programming: Data Structures and Beyond

How does Google Maps plan the best route for getting around town given current traffic conditions? How does an internet router forward packets of network traffic to minimize delay? How does an aid group allocate resources to its affiliated local partners? To solve such problems, we first represent the key pieces of data in a complex data structure. In this course, you’ll learn about data structures, like graphs, that are fundamental for working with structured real world data. You will develop, implement, and analyze algorithms for working with this data to solve real world problems. In addition, as the programs you develop in this course become more complex, we’ll examine what makes for good code and class hierarchy design so that you can not only write correct code, but also share it with other people and maintain it in the future. The backbone project in this course will be a route planning application. You will apply the concepts from each Module directly to building an application that allows an autonomous agent (or a human driver!) to navigate its environment. And as usual we have our different video series to help tie the content back to its importance in the real world and to provide tiered levels of support to meet your personal needs.

From the lesson

Introduction to Graphs

This week we'll start getting technical, introducing you to the central data structure in the course: Graphs. You'll learn the basics and then have a chance to dive in a little deeper into the code, getting ready to start building that Google Maps-like application.

Project: Programming Assignment Walkthrough15:41

Meet the Instructors

Leo Porter
Assistant Teaching Professor
Computer Science and Engineering
Mia Minnes
Assistant Teaching Professor
Computer Science and Engineering
Christine Alvarado
Associate Teaching Professor
Computer Science and Engineering

[MUSIC]

Welcome in this video I'm gonna walk you through your first programming assignment

for this class.

In this programming assignment you're going to be implementing some basic graph

structures, filling in our starter code, and working with real transportation data.

So, this video is going to assume that you've already followed the setup guide

and you got the starter code, so let's dive right into the assignment details.

The assignment has two parts, and in both of those parts,

you'll be implementing some functionality in some graph classes,

and you're actually going to be working with three classes.

You'll be working with an abstract class, Graph.java,

and then two concrete implementations extensions of that graph class.

GraphAdjMatrix.java and GraphAdjlist.java.

And if we go over here to the starter code,

I'll show you where to find those classes.

So we go over here, into Eclipse, and

we can see that it's inside the package basic graph.

You'll see Graph.java GraphAdjList.java and GraphAdjMatrix.java.

These are the files you'll be working with this week.

Now you're going to see a whole lot more classes here.

We don't have all the code yet into the starter code project.

But you'll see a whole lot more stuff, but basic graph is going to be the same.

So find the basic graph package and

work with Graph.java GraphAdjList.java and GraphAdjMatrix.java.

Now, where are you going to find the methods that you need to implement?

Well, you'll find the method you need to implement for

part one in this graph.java class.

So you'll be implementing this method here, called degree sequence, and

you can find this method by clicking on this first to do over here.

So I click on this first to-do, and I see that the first thing I need to do in part

one is implement this method degreeSequence.

So you're going to implement this degreeSequence method,

and what this method is going to return is a list sorted from largest to smallest,

possibly with repetition, of the degrees of all of the vertices in the graph.

So that's all you need to do, just like Mia described in the video.

And you'll find a few of the methods that we already have implemented helpful for

this method.

Let's go over here to write up and you'll see that we say that, in fact,

there are a couple of methods that are going to be useful.

So, the getNeighbors method, it's abstract in the graph.java classes but

it's actually implemented in the sub=classes.

So, we implemented that for and you can use that in degreeSequence method.

We also provide for

you a method called getInNeighbors, which is again, already implemented for

you in both of the sub-classes, so you can rely on it in the graph.java file.

And it's just like the getNeighbors method, only it returns the InNeighbors,

all the nodes which have this node, v, as a neighbor.

So both of these methods together will be very helpful for

you in implementing the degreeSequence method.

So after you've written your method you'll need to test your code, and

to do that we've provided you with some code and some data files that will help.

So again,

the starter code orientation guide gives you an overview of all the data we provide

for testing and then I'm also gonna talk about some of that right now.

So what we recommend starting with is the simpletest.map file

which is a file that contains a pretend map so it's not real world data.

It's just a pretend map.

Effectively, it's just a graph representing the following

fake street map.

And this is in the folder data/testdata/simpletest.map,

I'll look at it in just a moment.

So this is what that test graph looks like.

And you can calculate the degree sequence for this test graph, and

you can make sure that the degree sequence that your method is returning is in fact

the correct sequence for this graph.

Now this picture shows an undirected graph, but when you look at the file,

which we'll look at in just a moment,

you'll see that this is actually a directed graph structure.

So there are two edges in between each node, one going in each direction.

So let's take a look at that file and then we'll take a look at how that file gets

loaded in the main method of graph.java.

So go over here into data, testdata, and we can open up simpletest.map.

So what you can see here,

the format of this file, is that there are pairs of points, so this is a fake.

In this case, lattitude-longitude pair, another latitude and longitude pair and

then the name of the street, and then the type of the street.

So latitude longitude pair, latitude longitude pair,

those are the two end points of an edge.

And then here's the name of the street and the type of the street.

And you'll see that there is one edge in each direction for

each of the edges in that graph that I just showed you.

So, if you want to change a graph structure

you can simply make a copy of this file and then modify it by adding the edges

of the graph that you wanna think about and you wanna test with.

Just make sure you always include a start point to the edge,

an end point to the edge, and then a street name, and a street type.

Those fields are all required.

So let's look at how this is used and how it's loaded in in Graph.java.

So we go down here to Graph.java, go down to the Main method, and

you'll see that we've already provided you with a lot of code for testing.

So let's skip over the first part of this method here.

I' ll talk about this part later.

But let's just take a look at how we're actually loading these data files.

So if you look at this line right here, this GraphLoader.loadRoadMap,

you can see that we're passing it in the path to that simpletest.map

file I just showed you, as well as, a newly created graph to test with.

So here, I'm creating a GraphAdjList object.

So I just created a new one and then I I pass it in to this loadRoadMap method and

it's going to load up all of the data from this file into this graph.

And then I can test with this graph.

I can print it out, I can print the degree sequence,

I can do any testing that I want with this newly loaded graph object.

So that's it, and by creating new test files, you can load different graphs for

testing into your code here in Main.

And for this method, for the degreeSequence method,

it doesn't really matter whether you use an adjacency list or an adjacency matrix.

Because, of course, it's calling the method from the Graph.Java

from the abstract graph class, so that's how you'll do your first basic testing.

Now once you get a little bit more confident that your code is

working correctly, we encourage you to do some heavier dutier testing, as well as,

some visualization of these graphs.

So what we want you to do is run, not only on this very simple test dummy data file,

but we also provide you with a bunch of real world data files to test with.

So if you go over here into data into the maps folder,

you'll see that there are a whole bunch of data collections.

Hollywood large, Hollywood small, New York, Newberry small.

So, all of these are data collected from around the United States.

You can change this file right here, change the path of the for the file or

add new commands, load up new graphs, print out the degree sequences for

these graphs as well.

Now before you do that, we want you to try to make a prediction about what you

think the degree sequences will look like with these different road maps.

You can also test with some airport data, so we have available for

you some roots that United Airlines flies, represented in graph form.

So you could also load up this data.

The way you do that, you can see right here that we've already done it for you.

Instead of using LoadRoadMap, you'll use this method called LoadRoots.

And then you can pass in this path to this rootsua.date dat file.

So these are the methods that you use to load the graphs and to test them out.

And that'll just give you some printed information about the graph.

But what's even cooler is that in addition to printing the degree sequence,

what we want you to do is visualize the data.

So if you scroll down here to visualizing the data

you'll see that you can run this tool right here.

So we want you to download this tool and run it.

So why don't we just go ahead and,

Open up this tool and we can import the data.

So you import the data and you'll see that it's looking for some kind of a file.

Now, we provide for you, this is not the same .map file, or

the .dat file that you've used before.

The data that you need to paste into this window here are these intersections files.

So go over here into data, into the intersections folder, and

you can see that there are a number of files here that

correspond to the maps files that we just talked about.

But they all end in this .intersections extension.

So let's just pick here hollywood_large.intersections.

I'm gonna open that up.

And then I will select all of the data in that file.

Copy it out.

I go back over here and I click here and paste it in.

So now when I do this and I click Import, it's going to show me the graph.

So what you'll notice here is that this is, or you may not recognize this,

this is actually street data, a graph of the street data for the Hollywood Hills.

So each of the blue dots here is an intersection between the roads, and

each of the lines in the graph are a road themselves.

And you can do things like explore the graph.

So you can see that this is the degree distribution of this graph,

and you can see that I can actually also do things like click on

an individual node and see some information about that node.

So it has degree 6, and in-degree of 3, and an out-degree of 3.

And I can look and see like, yep, that looks about right, so one, two,

three going out, one, two three going in.

I can even view that particular point on Google Maps.

So, I'll go over here and I see that oh, look, that's right here.

And the cool thing about this is that if I look at the data area that I've just

plotted, it's basically this area right here, the Hollywood Hills.

And you could see how this data right here

really matches well with the structure of the graph that you see there.

So here are the mountains where there's no streets, and here's

where the streets become more regular down here, but these are the Hollywood Hills.

So we encourage you to explore with this tool.

Now what's even cooler is that you can generate street data of your

own and explore it.

And let me show you now how to do that.

So the way you're going to do that is

you're going to be able to go into the application.

So you'll run the application just like you saw in that

demo video at the beginning, the project overview video.

And I'm gonna run it from the solutions folder, because I have it all implemented

in the solutions folder but it's not yet implemented in the starter code.

So let me run it from the solutions folder.

I go up here and I go into the application folder and I click on MapApp.

And then I'm gonna run that.

So there's the application, and I can zoom in.

So let me just zoom in.

Say I want to get some data around, say, UCSD.

So I can zoom in to a piece of UCSD, this is right around where I am right now,

and I can then go down here and I can fetch that data.

So let me enter in a name for this file, so

I'll call it myucsd.map and

I'll fetch this data and it takes a little while, so I just say OK.

It's fetching the data for the current map and I just wait.

And then after a time, you'll see that it was written to a file and so

it's written into the folder data/, it's actually maps/myucsd.map.

So after the application reports that it's saved that data file,

the place you'll find it is in your maps folder.

So you may have to go over here in your clips and

right click on maps, you will have to do this, and click Refresh.

And then you'll see the file that you just saved appear right here.

So here it is.

However, this is not yet suitable for

loading into that graph visualization tool that I told you about.

So what you'll do next, is you'll go back into the main method for graph.java, and

you can see that there are these calls at the top.

GraphLoader.createIntersectionsFile and then there are some file names.

And what I'm gonna do is I'm gonna change these file names to be the path of that

data file I just saved.

So maps/myucsd.map.

And then this is the destination file so, data/intersections

/myuscd.intersection and then I don't want the .map.

So just myuscd.intersections.

And I'll get rid of these two lines because I don't really need them and

then I can go ahead and save that and run it again.

And if I run this what I'm going to see is I'll see in just a second.

So I run this.

There's some output that will help you with de-bugging.

But now if I go into this intersections file and

I refresh it you can see that myucd.intersections has appeared.

It's this file that I can load into that into that visualization application.

So I select all of these points, I go back over here,

to the viewer, I click import Data, I paste in all that data, and I import.

And lo and behold, I can see this data that I just saved.

Now, it wasn't a very large region that I just saved, and so if I go back over here

and look at this region, there are relatively few intersections.

So, there's this, this, this intersection.

Yeah, so, there's very, very few intersections in

that file that I just saved, so I see a very, very small graph, but

you're welcome to download larger graphs we recoomend that if they're not too big.

We recommend neighborhood size or small city size.

Otherwise, the files will be very, very large, and take a long time to download.

But that's the process for

how you can use this visualization tool to visualize your custom data.

So it's pretty cool stuff, and we encourage you to play around with that.

But for the moment, let's finish walking through the project.

So that's the end of part one, and again, this walkthrough was very long but

the actual work you're going to do is not very long.

When you're all done and you think your file is working correctly,

your method is working correctly, you will zip up Graph.java,

GraphAdjList.java, and GraphAdjMatrix.java.

So, GraphAdjList.java and GraphAdjMatrix.java, and

submit this zip file for part one of the assignment.

We'll run some tests on your code to make sure it's correct, and if it's not,

you're gonna find some files in the starter code.

And you'll see a file called DegreeGrader.java in the basic graph

package.

That is our part one grader, and you can run that to see what went wrong.

Very quickly, just to finish it up, the next part of the assignment is to

implement the getDistance2 method in both the GraphAdjList and

the GraphAdjMatrix representations or implementations.

We already have a support video on this, so I won't go in to too much detail, but

essentially all you're doing is implementing this method right here.

Public list integer getDistance2

which returns all of the two hop neighbors from this vertex V.

When you're confident that that's working correctly, again use the same method for

testing your file.

You create a zip file containing those same files as in part 1,

and submit that zip file for part 2 of the assignment.

You can again run our grader.

That grader is going to be in the basic graph package,

and it's called GraphGrader.java.

So if you get anything wrong here, and you can't figure it out,

just run our grader and that'll help you with your debugging.

So that's about all you need to know.

This was a rather more lengthy walkthrough than usual, but

that's what you need to know, and good luck with this assignment.

Ознакомьтесь с нашим каталогом

Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.

Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.

© Coursera Inc., 2018 Все права защищены.

Загрузить из App Store

Загрузить в Google Play