1. Homepage
2. Programming
3. CSI 2110 Data Structures and Algorithms - P2: Paris Metro: Exploring the Paris Subway Network

# CSI 2110 Data Structures and Algorithms - P2: Paris Metro: Exploring the Paris Subway Network

OttawaCSI 2110Data Structures and AlgorithmsJava

Paris Metro: Exploring the Paris Subway Network

The objective of this assignment is for you to get practice applying several graph algorithms in a relatively complex graph. For this, we will use the subway (metro) of the City of Paris. In this handout the word “lines” refer to subway lines, which in the picture below are "lines" of different colours (note that lines can be more complex than simple paths in a graph).

The information for you to build the graph for Paris subway network is contained in the textfile metro.txt. This graph is directed in order to take into account for some cases where the link is only one-way. This file is organized as follows:

• The file starts by specifying two integers: the number N of vertices and the number M of edges

in the graph.

• The next N lines in the file specify N vertices (stations). Each vertex has a unique number

followed by a station name. Each vertex corresponds to a point in a subway line corresponding to a particular station in that line. Note that different vertices can be followed by the same station name when several subway lines pass by the same "physical station" (e.g. Bastille).  Examples of vertices:

• 0016 Bastille

• 0017 Bastille

• 0018 Bastille

• 0119 Gare de Lyon

• 0135 Hôtel de Ville

• 0331 Saint-Paul, Le Marais

• The symbol \$ denotes the end of the vertex list.

• The rest of the file lists the edges of our graph, i.e. the existing connections between the

subway stations. The format is v1 v2 w, where v1 and v2 are vertex numbers and w is a number representing the weight of the edge.
If the weight is positive it indicates the time required (in seconds) to go from one station to the other station as adjacent stations on a subway line. For example the following edges connect adjacent stations in the light yellow line from right to left in the center of the map, connecting 0119 Gare de Lyon -> 0016 Bastille -> 0331 Saint-Paul, Le Marais -> 0135 Hôtel de Ville, taking 98 secs, 62 secs and 65 secs, respectively:

! 119 16 98 ! 16 331 62 ! 331 135 65

If the weight of an edge is -1, this edge indicates that it is possible to walk in order to switch from a station in one line to an station in another line. The time estimated when traversing an edge of weight -1 is a constant specified in your program for the walking time, which you must set as 90 secs. For example, the following links represent that we can walk among the three vertices in Bastille (16, 17, 18):

• !  16 18 -1

• !  16 17 -1

• !  17 18 -1

• !  17 16 -1

• !  18 16 -1

• !  18 17 -1

1. You must read the file and create a graph using the representation of your choice.

2. Usingthisgraph,yourprogramneedstoallowtoautomatically:

1. i)  Identify all the stations belonging to the same line of a given station.

2. ii)  Find the shortest path between any two stations, i.e. the path taking the minimum total

time. Print all the stations of the path in order, and print the total travel time.

3. iii)  Find the shortest path between two stations when we have the information that one given

line is not functioning (the line is identified by one of its endpoints). The same type of

information will be printed as in ii).

4. iv)  Bonus question (optional): this is a harder question, dependent on the previous questions

and described separately in the last page of this handout.

Note: when we mention "station" in items above we mean the station number.

You should create the following classes:

class Graph: This class stores the vertices and edges of a graph and implements the required basic graph methods.

class ParisMetro: This class deals with the operations for dealing with the Paris subway network. It will have a member object of the graph class to store the subway graph, a static method readMetro(String fileName) to read the input file, any auxiliary methods implementing algorithms you need to answer the assignment questions and a main method to run the program with the input arguments specified next.

You have freedom in the way you design these classes and you may use other classes if you wish.

In order to run your program from the command line, the call should be as follows:

```     java ParisMetro N1 N2 N3
```

with N1, N2 and N3 being numbers identifying subway stations.

identifying the line to be printed.

• If N1 and N2 are specified the program must answer question 2-ii) where N1 is the

departure station and N2 is the arrival station.

• If N1, N2 and N3 are specified the program must answer question 2-iii) where N1 is the

departure station, N2 is the arrival station and N3 is the endpoint of a broken line (line that is

not functioning).

• If no parameter is specified the program must answer 2-iv) the bonus question (optional).

## Get in Touch with Our Experts

QQ
WeChat
Whatsapp
Ottawa代写,CSI 2110代写,Data Structures and Algorithms代写,Java代写,Ottawa代编,CSI 2110代编,Data Structures and Algorithms代编,Java代编,Ottawa代考,CSI 2110代考,Data Structures and Algorithms代考,Java代考,Ottawahelp,CSI 2110help,Data Structures and Algorithmshelp,Javahelp,Ottawa作业代写,CSI 2110作业代写,Data Structures and Algorithms作业代写,Java作业代写,Ottawa编程代写,CSI 2110编程代写,Data Structures and Algorithms编程代写,Java编程代写,Ottawaprogramming help,CSI 2110programming help,Data Structures and Algorithmsprogramming help,Javaprogramming help,Ottawaassignment help,CSI 2110assignment help,Data Structures and Algorithmsassignment help,Javaassignment help,Ottawasolution,CSI 2110solution,Data Structures and Algorithmssolution,Javasolution,