辅导 COMP 261(2024)- Assignment 2 - Graph Algorithms讲解 Java编程

COMP 261 (2024) - Assignment 2 - Graph Algorithms

Zip file of code and data: containing four folders (Part1, Part2, Part3, Part4).

Zip file of 2024 Metlink data: may be useful for part 4.

Submission link

To submit:

Part1.zip : zip file of the Part1 folder (AStar search program)

Part2.zip : zip file of the Part2 folder (Connected Components program)

Part3.zip : zip file of the Part3 folder (Articulation Points program)

Part4.zip : zip file of the Part4 folder (extended pathfinder with fastest paths).

A brief Report.txt file stating which parts of the assignment you have completed and which parts do not yet work.

Overview:

This assignment is about implementing graph algorithms in programs using real data. It has four parts:

Part 1: Complete a program to find shortest routes in the Wellington Region Public Transport Network

(WRPTN). Most of the program, including all the user interface and reading data from files, is written for

you. You must extend the graph building code to include "walking edges" and implement the A* shortest

path algorithm.

Part 2: Create a program that identifies and displays the strongly connected components in the WRPTN.

Your program should build on the template program from Part 1, but must construct the graph in a

different way, and must implement the connected components algorithm.

Part 3: Create a program that identifies and displays the articulation points in the WRPTN. As in part 2,

your program should build on the template program from part 1 (or your new part 2), but must construct

the graph in a different way, and must implement the articulation points algorithm.

Part 4: Modify your part 1 answer to provide a facility for finding the fastest routes in the WRPTN.

You must submit your answer in four separate zip files, each zip file containing the folder for files for one part.

The Wellington Region Public Transport Network

The assignment involves writing three programs that use three dif ferent graph algorithms to query/analyse the Wellington Region Public Transport Network in three different ways, plus a fourth program that extends the first program in a more challenging way.

The Wellington Regional Public Transport Network is a complex network of bus lines (routes), train lines,

ferry services, and a cablecar that connect bus stops, train stations, and ferry/cablecar terminals. The data

forms a graph, with the stops/stations/terminals as the nodes of the graph, and the segments of

roads/tracks/ferry route between the stops/stations/terminals as the edges of the graph.

For this assignment, we will call the nodes of the graph "Stops".

Each direction on each bus route, train line, and ferry service is called a "Line", for example, the bus route 37

from Wrights Hill to Brandon St is treated as a different line from the reverse bus route 37 from Brandon St to

Wrights Hill.

Note that the bus stops are mostly on just one side of the road, and a bus stop on one side of the road is

unlikely to be directly connected to the bus stop on the other side of the road via any of the bus lines. To

actually use the network, a passenger may need to walk from one Stop to a nearby Stop, so the graph needs

to include walking edges as well, but there is a maximum walking distance that limits these edges.

The complete information about the network would include the schedule information about when each

bus/train/ferry/cablecar should arrive and leave each stop, but this schedule information is only relevant for

the very last part of the assignment. This information can be found in the metlink-data-2024 folder, or

online

The data for the programs you are to write is primarily in two files: stops.txt and lines.txt .

The stops.txt file contains one row for each stop in the network. The information on each row

includes the stop ID (eg 5915 or WELL), the name of the stop (eg "Wellington University - Stop B" or

"Wellington Station"), and the location (latitude and longitude), along with other attributes you won't need

to use.

The lines.txt file contains the sequence of stops along each line: each row contains a line id (eg

37_0 for the outbound bus route 37) and a stop ID (eg 5012). (The line also contains the number of

seconds from the start of the route to that stop, but this isn't needed until part 4). The sequence of stops

for each line specifies the order of stops along the line.

The data-full folder contains the stops.txt and lines.txt files that have the full 2022 data for

the network.

The data-small folder contains the stops.txt and lines.txt files for the 2022 data for just a part of the network, which may make testing your programs easier.

There are made-up test data files for Parts 1 and 2 that will also help you to test your programs.

The initial program you are given (in the Part1 folder) is a javaFX application that includes classes to read

all the data from the files, construct a graph of the network, and display the graph on the interface. It also

contains all the UI code to pan and zoom the display, reload the data (asking for a folder name), set the

maximum walking distance, and invoke the pathfinder by selecting the start and goal nodes (with the

mouse, or typing into text boxes).

The provided program includes the following classes. Many of them are complete and we do not expect you

as(to)si(m)g(o)m(if)en(y t)t(h)em. Other classes will need to be completed, modified, or added for each of the parts of the

Main.java: [Complete for Parts 1-3]

Starts the application.

NetworkViewer.java: [Complete for Part 1, modify in Parts 2-3]

Sets up the GUI, Loads data from files, and responds to the user interactions.

Graph.java: [Needs completing for Part 1, modify further in Parts 2-3]

Represents the information about the network graph.

Stop.java: [Complete for Part 1; Modify for Parts 2-3]

Represents information about a single Stop in the network, including its connections to other Stops.

Line.java: [Complete]

Represents information about a bus line, train line, etc, including the list of stops along each line and the

time to get to each.

Edge.java: [Complete]

A data structure to represent the directed connection from one stop to another. Used in building the

graph.

Zoning.java: [Complete]

Represent2s the geographical data describing the outline of the entire region and the fare zones.

java: [Complete]

Methods project the map to the display, used for pan and zoom.

GisPoint java: [Complete]

Representing a point using latitude and longitude and methods to calculate distances and new points.

Transport.java: [Complete]

Containing constants and methods to do with the different types of transport in the network (BUS,

TRAIN, FERRY, CABLECAR, and WALKING).

AStar.java: [Stub only; for Part 1]

Should contain the implementation of the A* algorithm.

SearchQueueItem.java: [Stub; Only for Part 1]

You may use it for items on the A* search queue.

Components.java: [Stub; Only for Part 2, in Part2 folder]

Should contain the implementation of the Strongly Connected Components algorithm.

ArticulationPoints.java: [Stub; Only for Part 3, in Part3 folder]

Should contain the implementation of the A* algorithm.

You can use any IDE you wish to write the programs for the assignment, but you may have to set up your

IDE to run JavaFX programs correctly. This may be complicated for some IDEs and especially on Apple

computers. BlueJ (v 5.2.1) is automatically set up to run JavaFX programs and we have provided a

package.bluej file with the program. To run the program from BlueJ, right-click on the Main class, and

select "Run JavaFX Application".

Part 1: Finding Shortest Paths in the Network. [40%]

The first program will allow a user to find a shortest route through the network from a starting Stop to a goal

Stop. The provided program is almost complete for Part 1, including all the UI code: you only have to write

the code to add the walking edges to the graph and implement the A* algorithm to find the shortest route

between two Stops.

Walking Edges and the Graph structure for Part 1.

Wellington Regional Public Transport Network is a directed, labeled, weighted multi-graph:

An Edge between two Stops is directed, according to the direction that the bus/train/ferry goes between

the Stops. If the reverse route also goes through the two stops (as is the case for most train lines and for

walking connections, but not most bus routes) then there will be a second, different Edge for the reverse

direction between the two stops.

The Stops are labeled with their ID, and have additional information such as their name, location, and a

list of the Lines that go through the stop.

The Edges are weighted with their distance, which is the distance between the locations of the two

Stops at each end of the edge. (The distance ought to be based on the length of the road beteen the

Stops, but this would be unnecessarily complicated for this assignment.) The Edges also have additional

information, including the Line that they are part of, and the kind of transport.

The graph is a multi-graph because there may be many edges between two Stops, one edge for each

Line that goes from the first Stop to the second Stop. For example, there are 12 routes that go from the

Wellington University - Stop B to Upland Road (18_1, 21_0, 22_0, 37_0, an after-midnight bus, and

seven school bus routes), and therefore there are 12 separate Edges from Stop 5915 to Stop 5916.

The provided program builds all the Stops and Edges for the graph from the data files (see the loadStops

and loadLines methods in NetworkViewer.java and the constructor in Graph.java ). It only creates

forward edges: if there is an Edge E from Stop X to Stop Y, then Stop X will contain E in its collection of

edges, but Stop Y will not contain E.

The program does not build the walking edges. Specifing the maximum walking distance in the UI (using the

slider or the text field) will call the removeWalkingEdges and recomputeWalkingEdges methods in

Graph.java . You must write these methods:

recomputeWalkingEdges should find all pairs of Stops that are no further apart than the maximum walking Distance, and construct two Edges between the stops - one in each direction.

removeWalkingEdges should remove all walking Edges from the Graph. Hint: make sure you set the transportation type of the walking edges to Transport.WALKING !

When 2 written these methods correctly, the display of the network should show all the walking

edges different colour. You may need to zoom in to see them.

Finding a shortest route for Part 1.

When the user enters a start and goal (by typing the names of the Stops in the text fields or by clicking on

the displayed network), the NetworkViewer class will call AStar.findShortestPath(...) to find the

shortest route from the start to the goal. AStar.findShortestPath(...) should return the shortest path

from start to goal as an ordered list of Edges on the path, from the start to the goal. If there is no path, it

should return null.

The AStar.java file is provided, but is essentially empty. You need to complete it, implementing the A*

algorithm described in lectures.. You will also need to define a class for the items that are put on the priority queue in A*.

A* uses a heuristic estimate of the remaining pathlength from each node it considers; you may find the

distanceTo(...) methods in Stop.java helpful.

Notes:

The Stop class does not allow you to mark Stops with "visited" or with the previous node from which

they were visited. You will need to use a HashSet of visited Stops to record which Stops have been

visited, and an appropriate structure to record the Edge from which the search got to each node that it

visited.

The shortest path finding in Part 1 does not have to take the bus route/train line information into account,

so that the path it finds may have a sequence of edges from completely different bus routes. Actually

taking the proposed paths might require changing buses (and waiting for a later bus) at every Stop! You

will see this in the report of the path shown at the bottom of the interface. Part 4 of the assignment will

address this problem.

Screenshot for Part1, with the data-small map loaded,

Zoomed in on Kelburn,

Walking distance set to 70m. (You can see the walking edges between some stops on opposite sides of

the road.

Shows the shortest path from the University to Marsden village.

Screenshots for Part1 with the data-testAstar map data loaded.

Stops are on a grid, with two Stops slightly displaced.

There is just one bus route, zigzagging from the top left Stop to the bottom right Stop.

Walking distance of 300 adds horiziontal edges;

Walking distance of 480 adds vertical edges; (500 adds one further diagonal walking edge).

Walking Distance = 0 - One way links.	Walking Distance = 0 - Shortest path from top left to -bottom right.	Walking Distance = 300 - Horizontal walking edges added.

Walking Distance = 300 - Shortest path from top left to bottom right.	Walking Distance = 300 - Shortest path from bottom right to top left.	Walking Distance = 480 -- Short(Vertic)e(a)s(l)tep(d)a(g)th(e)sft(e)p left to bottom right.

Part 2: Finding Strongly Connected Components [20%]

The second program does a different kind of analysis on the network to find parts of the graph that are not

strongly connected to other parts. Inside a strongly connected component, it is possible to get from any node

to any other node, but it is not possible to get both to and from a node inside the component to any node

outside the component. A network with many such connected components is undesirable for a public

transport network.

Your program should enable a user to see how well the network is connected.

Using Kosaraju's algorithm, as described in the lecture, your program should find all the strongly connected

components 2the directed graph and return a Map that links each Stop with the ID of its component. Your

program then display the components by colour-coding each Stop with a colour according to its

component

Kosaraju's algorithm requires an ordinary directed graph, rather than a multi-graph - there should be at most

one Edge between two Stops. It also requires backward links - each Stop should not only have a collection

of the Edges out of the Stop, but should also have a collection of the Edges in to the Stop.

( Note: this does not mean two versions of the same Edge - the same Edge object should be in the "out

edges" of its "from" Stop and in the "in edges" of its "to" Stop.)

Construct a new program in the Part2 directory by copying your Part 1 program (including data-full and

data-small) to the Part2 folder, then modifying it to identify the Strongly Connected Components.

1. Modify the UI by removing the label and text fields for start and goal, and the methods for setting the

start and goal.

2. Make clicking the Mouse print out the description of the closest Stop in the displayText area.

3. Modify the drawMap() method in NetworkViewer.java to remove the path drawing and reporting 4. Remove the AStar class and any other classes used only for the path finding.

5. Modify the Stop class so that each Stop has

a collection of Edges out of the Stop

a collection of Edges in to the Stop

6. Modify the way that the Graph class creates edges (both Edges from the linedata and walking Edges) so that

There is at most one Edge from any one node to a second node.

Each Edge is recorded on the "out edges" of its "from" Stop, and the "in edges" of its "to" Stop.

Note that identifying strongly connected components does not care about the bus route/train line

information in the edges.

7. Add a new button to the UI for computing the strongly connected components, and make it invoke

Components.findComponents(...)

8. Implement Kosaraju's algorithm in a findComponents method in a Components class. Test it by loading data-testComponents , and your algorithm should find 5 components.

9. Modify the drawMap() method in NetworkViewer.java to draw the Stops using different colours to

show the different components, and report all the strongly connected components in the text area, listing

the number of components and the Stops in each component.

Hint: if there are n components, create a list or array of n different colours to use when drawing the Stops:

Color[] subGraphColors = new Color[numComponents];

for (int i=0; i i++){

subGraphColors[i]= Color.hsb((180.0 + (i*360.0/numComponents)) % 36

0, 1, 1);

}

The following is a screenshot of what your Part2 should look like:

The data-small map is loaded,

Walking distance is set to 10m,