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

Engage in a Conversation
OttawaCSI 2110Data Structures and AlgorithmsJava

Paris Metro: Exploring the Paris Subway Network CourseNana.COM

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). CourseNana.COM

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: CourseNana.COM

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

    in the graph. CourseNana.COM

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

    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: CourseNana.COM

  • The symbol $ denotes the end of the vertex list. CourseNana.COM

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

    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 Hôtel de Ville, taking 98 secs, 62 secs and 65 secs, respectively:
    CourseNana.COM

    ! 119 16 98 ! 16 331 62 ! 331 135 65 CourseNana.COM

    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): CourseNana.COM

Your tasks CourseNana.COM

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

2. Usingthisgraph,yourprogramneedstoallowtoautomatically: CourseNana.COM

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

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

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

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

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

    information will be printed as in ii). CourseNana.COM

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

    and described separately in the last page of this handout. CourseNana.COM

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

Your program: CourseNana.COM

You should create the following classes: CourseNana.COM

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

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. CourseNana.COM

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

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

     java ParisMetro N1 N2 N3

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

  • IfonlyN1isspecifiedtheprogrammustanswer question2-i)whereN1isthegivenstation CourseNana.COM

    identifying the line to be printed. CourseNana.COM

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

    departure station and N2 is the arrival station. CourseNana.COM

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

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

    not functioning). CourseNana.COM

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

Get in Touch with Our Experts

QQ QQ
Wechat WeChat
Whatsapp 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,