代写Algorithm留学生、代做Minimum Spanning Tree、代写Java编程、Java语言代做

日期：2019-06-08 07:36

PA 9: Application of Graph Traversal

Algorithm and Minimum Spanning Tree

Checkpoint due (+5 extra credit): Monday, midnight

Submit all the part 1 except A*

Due: June 7th, Friday 11:59 PM (midnight)

200 points

Overview

In the first part of the assignment, you will build your own navigation system just like

Google Maps using four different graph traversal algorithms we learn from class: DFS,

BFS, Dijkstra and A*.

In the second part of the assignment, you will implement a data structure Disjoint Set

(Union Find) to help you implement Kruskal’s algorithm and find a Minimum Spanning

Tree for a given Graph.

This assignment is an individual assignment. You may ask Professors/TAs/Tutors

for some guidance and help, but you can’t copy code. You may discuss the assignment

conceptually with your classmates, including bugs that you ran into and how you fixed

them. However, do not look at or copy code. This constitutes an Academic Integrity

Violation.

START EARLY!

Style Requirements

You will be graded on your code’s style:

https://sites.google.com/ucsd.edu/dsc30/resources/style-guide

IntelliJ has a great plugin to check your style automatically. Use it!

There are style considerations beyond indentation and such.

● Choose names for test methods and for variables that are descriptive and useful

when you see them in test output.

● Consider writing helper methods if you repeatedly use the same set of

statements.

● Use Javadoc comments for descriptions of your methods and classes and inline

comments if the logic of your program is not captured by your variable names

and the natural flow of code.

Part 0 - Starter code and PA quiz

Our starter code will be distributed from

https://github.com/ucsd-ets/dsc30sp19-startercode.

Note that this assignment has two parts, and you should create two separate

projects in IntelliJ to implement each part, and submit each part on gradescope

separately.

Please follow the same procedures as before to get your starter code and set up intelliJ.

PA quiz (Due Monday)

Fill out this quiz about the PA to make sure you have understood the assignment

thoroughly. You have 5 attempts to complete it.

https://forms.gle/VSBimvhFPpUVG9SK6

Part 1 - Graph Traversal Algorithms

1.1 Intro and Analysis of Graph Traversal Algorithms

Graph traversal algorithms have many useful applications in real life. The four

algorithms we will discuss in class have various applications: DepthFirstSearch,

BreathFirstSearch, Dijkstra and A*. In this part of the assignment, you will use these

four algorithms to build your own navigation system (just like Google Maps).

First, let’s make a guess about which algorithm could potentially be used in Google

Maps to find the shortest path between two locations. For simplicity, assume that

there exists at least one path that connects two given locations. You will probably

cross out DFS first. From what we have learned, DFS will find a path that connects two

vertices, but most likely, this path will not be the shortest. In a large graph like the Earth,

the path generated by DFS will probably spend its whole life on heading towards a

wrong direction.

What about BFS then? We know that with a finite number of vertices in an unweighted

graph, we are guaranteed to find the shortest path connecting two given vertices using

BFS. However, in an actual map, edges between two vertices are typically weighted

rather than unweighted. Roads (edges) that connect different cities (vertices) vary by

length, so we need to assign different weights to each road (edge). Furthermore, traffic

condition could be another component of weight of edges in Google Maps to help you

avoid traffic. Since we know that BFS will most likely fail to find the shortest path in a

weighted graph, we need to continue to the improved version of BFS: Dijkstra.

As we all know, Dijkstra can be used to find the shortest path connecting two given

vertices in a weighted graph. However, once you understand the way Dijkstra explores

the graph, you will realize that Dijkstra is not an efficient algorithm for navigation

system. In a large graph, Dijkstra takes much longer to run for two vertices that are far

away from each other, because Dijkstra will find the shortest path from starting

node to all the other reachable nodes. Although it’s guaranteed that Dijkstra can find

the shortest path, it will search “blindly” for the shortest path: the algorithm will keep

looking for our destination in every possible direction (searching useless parts of the

graph), even if we already know the direction of our destination.

(Dijkstra will explore every location within nearly two thousand miles of Denver before it

locates NYC.)

To solve this problem more efficiently, we will introduce you to an algorithm that “knows”

that we need to first explore east in the example above: A*. Given that we know the

location of our destination, A* can use a simple heuristic function to guide its search.

And with a heuristic function that satisfies certain conditions, A* can still find the shortest

path between two given nodes just like Dijkstra, but much faster. In fact, although

Google Maps is using more complex and efficient algorithms, the idea of the A*

algorithm is its basis.

1.2 Build the Graph

Before starting to implement algorithms for our navigation system, we first need to

consider a well-defined way to represent our “map” using a graph.

As you might know from class, a graph consists of two components: vertices and edges.

Therefore in order to define our “map” as a graph, it is quite natural for us to define

“locations on map” to be the vertices, and “all the roads that connects two locations” to

be the edges.

Since the goal of our navigation system is essentially finding a path that connects two

given locations on the map, we can define our problem as the following:

Given two vertices, find a sequence of edges that connects these two vertices.

Notice that with a finite number of vertices in our graph, if we apply DFS, BFS, Dijkstra

and A* to our graph to find a path (assume there exists at least one path that connects

two given vertices), we might end up with totally different results. We have provided a

wonderful GUI for you to visualize the result path. After you finish implementing each

one of the algorithms, you can use this GUI to check if the path match your expected

behavior of the algorithm. We will give more details about how to use this GUI later.

1.2.1 Vertex and Edge

One simple dataset you will use to build your graph consists of two input files: cityxy.txt

and citypair.txt.

In our graph, the vertices are defined by cityxy.txt, where each line has the name of a

city followed by its x and y coordinates. For example, a line “LasVegas, 160, 350” in

cityxy.txt means we should have a vertex with name “LasVegas”, x-coordinate “160”

and y-coordinate “350” in our graph.

Meanwhile, the edges in our graph are defined by citypair.txt, where each line has a pair

of cities followed by the distance between them, which implies the “weight” of this

undirected edge. For example, a line “LosAngeles, LasVegas, 100” in citypair.txt means

we should have an undirected edge between vertex “LosAngeles” and vertex

“LasVegas” with weight “100”.

In the starter code, we have provided the full Edge class, but only part of the Vertex

class for you. You need to think about what other instance variables and methods

you will need to add to Vertex class after you understand more details about

Graph class. More specifically, you need to decide how to represent all the adjacent

edges of a given vertex, so that it’s possible to traverse from this vertex to its adjacent

vertices. Furthermore, when implementing DFS, BFS, Dijkstra and A*, you need to think

about how you can keep track of some other important information in Vertex class to

make these algorithms work.

1.2.2 Graph

In this class, you will implement all the methods to help you find the path between two

given locations in our navigation system.

We won’t give you detailed instructions in this part, the comments in starter code should

give you an idea of the purpose of each method.

Here are some clarifications on implementation details:

1. We didn’t define any instance variables in this class. You need to think about

which data structure you can use to store all the vertices with edges so that you

can quickly access them.

2. Once you decide which data structure you want to use, check its documentation

to find a method to help you return a Collection of Vertices in getVertices()

3. Let vx

and vy

be x and y coordinates of a given vertex v . The Euclidean

distance between two vertices u, v is given by this formula

4. computeAllEuclideanDistances()will change the user-defined distance of

each edge in the graph to be the Euclidean distance between two locations on

the map.

5. Before you start exploring your graph using different algorithms, you need to

reset some of the instance variables of all the vertices using a helper method

resetAllVertices()

6. CostVertex is a completed helper class for Dijkstra and A* algorithm that you

might find handy. It wraps around a vertex with its “cost”, so that we can use the

“cost” to determine its priority in a priority queue.

7. Think about when you need to stop exploring in our four graph traversal

algorithms, so that you don’t spend time exploring the useless parts of the graph.

8. In these four graph traversal algorithms, the order for selecting children of a

vertex should be the same as the order of the edges of this vertex (Start from the

first edge to the last edge). Since the order of the edges of any vertex is defined

by the user input in citypair.txt, we avoid ambiguity here when exploring the

graph. (Note that you should be using stack to implement DFS and push the

outgoing edges of a given vertex in the same order as mentioned above)

9. Notice that none of the graph traversal algorithms return a path at the end of the

methods. Instead, getpath() is the method we will use to return a list of edges

that connects two given locations (The order of the returned edges should be the

same as the order of edges you get when traversing from start vertex to end

vertex). Later in Display.java, it’s assumed that one of our four graph

traversal algorithms such as BFS() will be called before we call getpath() to

get the results.

10.Once you are done implementing one of the algorithms like DFS (make sure you

finished getPath() and all the methods on the top first), you can proceed to the

next part to use the provided GUI to visualize the results.

Note: feel free to create other methods here (public is OK) if you think the given

methods are not enough for you, you might potentially need some getters here.

1.3 - Fun with GUI

We have provided Display.java, a GUI for visualizing the output of your graph. You

don't need to know how Display.java is implemented (it'd be good if you want to

learn about Java GUI though). Although you do need to write two small parts in

paintGraph(), check TODO in Display.java for more details there.

To run the GUI, you can simply select Run on the top menu of IntelliJ and then click

Run “Display”.

Conceptually, you can imagine Display.java doing the following:

1. Instantiating a new instance of Graph and create vertices / edges from the files

cityxy.txt and citypairs.txt. You can change the file names to play around with

different graphs using the Load / Reset button to load different input files. Notice

that the input files should be placed in “PA9” folder for the GUI to be able to find

those files. You don’t need to handle any command line arguments here, just

type the name of the files and the GUI will do the work for you.

2. Notice that the weight of the edges are defined in the input file citypairs.txt by

default. Because the weight of the edge is not necessarily the distance between

two vertices, you can define the weight of any edges in your own graph.

3. If you only want the weight of your edges to be the true distance between two

vertices, you can simply click Compute All Euclidean Distances, it will call

graph.computeAllEuclideanDistances(). Then the GUI will show all the

updates on the distance variable of Edge objects in the graph. For example, let’s

say the user defined “LosAngeles,111,395”, “LasVegas,160,350” to be two

vertices, and “LosAngeles,LasVegas,100” to be the weight of the edge that

connects them. The default weight of this edge will be 100, but once you click

Compute All Euclidean Distances, our program will calculate the true distance

between LosAngeles and LasVegas: √(111 ? 160) 395 50) 6.5 . And the 2 + ( ? 3

2 ≈ 6

weight of this edge will be updated to 66.5.

4. Clicking on the blue button Draw Dijkstra's Path, it will call graph.Dijkstra()

with the starting city and targeting city names as the parameters. Then it will

highlight the edges returned by graph.getPath() between the starting city

and the targeting city. Same idea for the other 3 buttons.

Graph graph = new Graph();

String startingCity = // get text from selected value in dropdown

String targetingCity = // get text from selected value in other dropdown

graph.Dijkstra(startingCity, targetingCity);

List<Edge> path = graph.getPath(startingCity, targetingCity);

1.4 More Input files and Testing

Right now we only have 2 set of input files: cityxy.txt and citypairs.txt and smallcityxy.txt

and smallcitypairs.txt. Notice that you can customize your input files (need to be in the

right format) and play with the new resulting GUI. You can potentially use your own

input files to create a maze here for your algorithms to solve!

Check this out if you want to further visualize how each algorithm explore the graph

:https://qiao.github.io/PathFinding.js/visual/

Be aware that matching all the outputs below doesn't necessarily mean that you will

pass the autograder test. The test will compare the outputs of your getPath() against

the outputs of our solution code. You need to make sure you put all the edge in the right

sequence (The sequence of edges starting from the start vertex to end vertex).

Test case 1 (input files cityxy.txt and citypairs.txt)

After clicking Compute All Euclidean Distances:

From Los Angeles to Atlanta, using DFS

From Los Angeles to Atlanta, using BFS

From Los Angeles to Atlanta, using Dijkstra / A* ( hvalue: Euclidean distance )

Test case 2 (input files cityxy.txt and citypairs.txt)

After clicking Compute All Euclidean Distances:

From Vancouver to Miami, using DFS

From Vancouver to Miami, using BFS

From Vancouver to Miami, using Dijkstra / A* ( hvalue: Euclidean distance )

Test case 3 (input files smallcityxy.txt and smallcitypairs.txt)

After clicking Compute All Euclidean Distances:

From SanFrancisco to NewYork, using DFS

From SanFrancisco to NewYork, using BFS

From SanFrancisco to NewYork, using Dijkstra / A* ( hvalue: Euclidean distance )

Test case 4 (input files ucsdxy.txt and ucsdpairs.txt)

After clicking Compute All Euclidean Distances:

From Warren to Revelle, using DFS:

From Warren to Revelle, using BFS:

From Warren to Revelle, using Dijkstra / A* ( hvalue: Euclidean distance )

Test case 5 for A* only (input files cityxy.txt and citypairs.txt)

Change your hvalue method to make hvalue to be 4 times Euclidean distance here.

The large factor here will make A* become too greedy (make it behave more like best

first search, quickly approach the goal but the path is not the shortest).

From Vancouver to Miami, using A* ( hvalue: 4 * Euclidean distance )

You should get the results below:

Part 2 - Disjoint Set and Minimum Spanning Tree

2.1 Graph Class

You will start this part of the assignment by first implementing most of the methods in

Graph class (except for runKruskalsAlg()).

This part should be quite similar to how you implement the Graph class in part 1.

However, there are some slightly different details here.

1. Notice that now when we add a new undirected edge to our graph, we also need

to add this new edge to allUndirectedEdges, which is an ArrayList of Edge

in this class to store all the undirected edges. As allUndirectedEdges will be

used in Kruskal’s Algorithm, you must use the following rules to make your

Kruskal’s Algorithm return the correct set of edges: when adding a new

undirected edge between nameU, nameV, you will additionally add a new

edge with nameU as source vertex, nameV as target vertex and given

weight as weight to allUndirectedEdges.

2. Another main difference here is that our constructor for Graph has a boolean

value edgesGiven, which indicates if the user will provide self-defined edges in

the graph. If edgesGiven is given as true, the method populateAllEdges()

should be disabled. Otherwise if edgesGiven is given as false, addEdge(),

addUndirectedEdge(), computeAllEuclideanDistance() should be

disabled. (To disable any method here, check the boolean and if disabling is

necessary, print any error message then directly return at first)

Note that the purpose of this boolean and disabling appropriate methods is to

accommodate our GUI later. In our GUI, the users are given two options to

compute the minimum spanning tree of the graph defined by input files.

The first option is computing the minimum spanning tree using edges defined

by the input edges file. In this case, edgesGiven will be true.

The second option is computing the minimum spanning tree using all the

possible edges for the given vertices without considering the edges input

file. In this case, edgesGiven will be false. (More on this later)

It is easy to see that if the user wants to use the first option, which is computing

the minimum spanning tree using edges defined by the input edges file, then a

call to populateAllEdges() should be disabled since it will add additional

edges that is not defined by input edges file.

3. In populateAllEdges(), you should add all the possible n(n ? 1) / 2 undirected

edges with weight as Euclidean Distance to allUndirectedEdges in a

graph with n vertices. (You don’t need to add these edges to the adjacent list of

any vertex here.)

You need to think about how to add exactly n(n ? 1) / 2 undirected edges without

adding any duplicate undirected edges. (i.e if undirected edge from u to v was

added, then undirected edge from v to u should not be added)

Hint: Consider using the following code to convert your vertices collection to an

array of vertex, which provides easier access to each vertex in your graph.

Collection<Vertex> vCollection = getVertices();

Vertex[] vertices = vCollection.toArray(new Vertex[vCollection.size()]);

2.2 Disjoint Set Implementation

In this class, you will implement Disjoint Set, which will be useful in Kruskal’s algorithm

to determine if adding a new edge will create a cycle in the graph. Disjoint set has a

simple and beautiful implementation and can check if two vertices are connected in

nearly constant runtime.

You probably need to add some additional instance variables to Vertex class to make

your Disjoint Set work on vertex in your graph. Please read the starter code in Vertex

class for more details.

public Vertex find(Vertex v)

Returns the “sentinel node” representing the set that this vertex belongs to. You must

apply path compression here to optimize the runtime.

public void union(Vertex v1, Vertex v2)

Merges the two sets that two given vertices belongs to. If two given vertices belongs

to the same set, return. Otherwise, apply union by size: make the “sentinel node” of

smaller set as child of “sentinel node” of larger set.

(The union operation here can be done using either union by height or union by size.

The choice here is up to you, but we suggest using union by size here as it is slightly

easier to implement. )

2.3 Testing Disjoint Set

Now you should create a tester named DisjointSetTester.java to verify the

correctness of your disjoint set data structure.

Make sure you have tested the following cases:

1. After you union a set of vertices, calling find on each of them should return the same

sentinel node.

2. For two vertices that are not in the same set, calling find should return different

sentinel node.

2.4 Implement Kruskal’s Algorithm

Now go back to your Graph class and implement the method runKruskalAlg(), now

that Disjoint Set can help you efficiently check if two vertices are in the same connected

component. Here are some notes that you need to know to implement this algorithm:

1. To save us from recomputing the same result, if the result was already

computed before, directly return the result at first.

2. Use the code below to sort allUndirectedEdges in increasing order of weight:

Collections.sort(allUndirectedEdges, Comparator.comparingDouble(e ->

e.getDistance()));

3. Assume that there are v vertices in your graph and all the vertices are in the

same connected component, notice that when your result contains v - 1 edges,

the MST of this graph should already be defined by these edges. The reason is

knowing that the graph is connected and there is no cycle in the MST (since MST

is a tree) implies that there are v - 1 edges in the MST. Using this property, think

about how you can slightly improve the runtime of Kruskal’s Algorithm.

After you finish implementing Kruskal’s, just as in part 1, you should check the

TODO in Display.java to implement two small parts in order to display the

graph correctly.

2.5 Testing Kruskal’s Algorithm

Test case 1 (input files cityxy.txt and citypairs.txt)

Click Load Graph With Edges -> Click Run Kruskal’s Algorithm.

You should see the following result:

Qi

Click Load Graph With Edges -> Click Edge Weight: Euclidean Distance -> Click

Run Kruskal’s Algorithm. You should see the following result:

Click Load Graph Without Edges -> Click Run Kruskal’s Algorithm. You should see

the following result:

Test case 2 (input files ucsdxy.txt and ucsdpairs.txt)

(Imagine you are working for AT&T, and you want know a internet/phone network

design that connects all the locations below on UCSD campus with minimum total cost.

Then you should use MST algorithm such as Kruskal’s to find the MST as your network

design)

Click Load Graph With Edges -> Click Edge Weight: Euclidean Distance -> Click

Run Kruskal’s Algorithm. You should see the following result:

Click Load Graph Without Edges -> Click Run Kruskal’s Algorithm. You should see

the following result:

Submission

There are two parts of submission: PA9 Part 1 and PA9 Part 2

Submission for PA9 Part 1:

Note: You can try using Manhattan distance or manipulate the factor of your hValue

before the final submission, but in the final submission, make sure you are using

Euclidean distance as the heuristic function.

Files to submit:

1. Vertex.java

2. Graph.java

3. Display.java

Submission for PA9 Part 2:

Files to submit:

1. Vertex.java

2. DisjointSet.java

3. DisjointSetTester.java

4. Graph.java

5. Display.java

After you submit your files to GradeScope, wait for the output of submission

script. Make sure you see this after your submission:

THIS IS A SUCCESSFUL SUBMISSION. YOUR SCORE WILL BE UPDATED ONCE

GRADED.

Otherwise, please fix the error and resubmit your files.