COSC 2P03 Advanced Data Structures: Assignment 4 Transportation network is a model of the real-life transportation system. It is a typical example in graph theory research and plays an important role in a variety of real-life applications

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

need help with this assignment

 

 

COSC 2P03 Advanced Data Structures: Assignment 4

 

1Department of Computer Science, Brock University

 

1 Introduction to the Problem

Transportation network is a model of the real-life transportation system. It is a typical example in graph

theory research and plays an important role in a variety of real-life applications (e.g. planning and navigation).

In this assignment, you are given a simplified version of Ontario’s land transportation network (see Figure

1), and need to use graph algorithms to solve a few tasks.

2 Your Tasks (8 Marks)

1. Define a class named TransportNet which has data attributes to represent the graph (i.e. the transportation network) and has methods as required below.

2. Within the TransportNet class, define a method named readData to read the information from the two

attached CSV text files (cities.txt for vertices in your graph, distances for edges in your graph).

These two files will help you create your weighted undirected graph. You should use adjacency matrix

to represent edges. (1 mark)

3. Within the TransportNet class, define a method named findShortestPath based on Dijkstra’s algorithm to find the shortest path between two given cities on the graph. For example, if you call

findShortestPath( "Windsor", "Ottawa"), it should return the shortest path (i.e. a sequence of

city names) and the total cost (i.e. the sum of weights on the shortest path). You can either use Java’s

built-in priority queue implementation or implement it yourself. (2 marks)

4. Within the TransportNet class, define a method named MST based on Kruskal’s idea to return a

minimum spanning tree of your graph and the total cost of this tree (i.e. the sum of weights on the

tree). You are allowed to use code from the textbook and lecture slides. (3 marks)

5. In the main function, create an instance/object (with name tn) of your TransportNet class. Call

readData(<your data path>) to create your graph. Call functions findShortestPath( "Windsor",

"Ottawa") and findShortestPath( "Arnprior", "NOTL"). After each call of this function, you

should write your results into a text file named results.txt. Use file IO rather than copy-and-paste

printed messages from the screen. Furthermore, call MST() and then write the returned results to the

results.txt file. (1 mark)

Program comments: to maximize readability, you should properly comment your program. (1 mark)

3 Submission

• Your source code.

• A PDF printout of your source code.

∗E-mail address: yli2@brocku.ca

1

Toronto

Hamilton Grimsby Saint Catharines

London

Windsor

Chatham-Kent

Waterloo

Guelph

Sarnia

NOTL

Niagara Falls

Fort Erie

Kingston

Renfrew Arnprior Ottawa

Thunder Bay

Sudbury North Bay

334 262

73

89

257

251

370

423 398

1196

45 28

14

21

33

115

102

30

19

121 20

56

14

65

20

85

157

60

348

376

Welland

280

219

Figure 1: A simplified transportation network for Ontario’s land transportation system.

2

• The text file results.txt that shows all saved results as required above.

• Compress the above files in a zipped folder named COSC2P03 A4 YourFirstname YourLastname StudentNumber.zip

and submit it through Sakai before indicated due time.

• Late submissions will not be accepted.

• Note: you should submit both your Java source code and your PDF printout. Missing any of them will

result in a zero grade for this assignment.

4 Academic Integrity

This assignment should be tackled individually. Outsourcing or teamwork is not allowed. Violation of this

requirements will be seriously processed in accordance with university policies.

3

Attachments:

Expert's Answer

840 Times Downloaded

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of