BBM 204 PROGRAMMING ASSIGNMENT 4 Finding Time-Dependent Shortest Path

Description

Subject: Directed graphs and shortest path
1 Introduction
The main objective of this assignment is to gain experience on handling directed graphs, or
digraphs, and on implementing the shortest path algorithm (i.e., Dijkstra) within a scenario
comprising a number of design constraints.
The following two subsections introduce the basic concepts of the directed graphs (Section 1.1) and Dijkstra’s shortest path algorithm, one of the well-known algorithm (see Section 1.2).
1.1 Directed graph
A directed graph is a set of vertices and a collection of directed edges that each connects an
ordered pair of vertices. We say that a directed edge points from the first vertex in the pair
and points to the second vertex in the pair. The vertices are also called nodes or points, while
directed edges are also referred to as links or lines. When working with real-world examples
of graphs, we sometimes refer to them as networks.
Adjacency-lists representation is one of the convenient ways for a graph representation. In
this representation, we often maintain a vertex-indexed array of lists of the vertices connected
by an edge to each vertex. Figure 1 demonstrates adjacency-list representation of a digraph
containing 5 vertices and a couple of edges connecting some of them.
Figure 1: An example of a digraph and a corresponding adjacency-list representation.
1.2 Dijkstra’s shortest path algorithm
An edge-weighted digraph is a digraph where we associate weights or costs with each edge.
The shortest path from vertex s to vertex t is a directed path from s to t with the property
Page 1 of 14
BBM 204: Software Laboratory II
that no other such path has a lower weight.
Dijkstra’s algorithm, conceived by a computer scientist Edsger W. Dijkstra in 1956, is an algorithm for finding the shortest paths between the vertices in a digraph, which may represent,
for example, road networks.
A step-by-step introduction of Dijkstra’s algorithm1
is given below.
1. Mark all nodes unvisited. Create a set of all the unvisited
nodes called the unvisited set.
2. Assign to every node a tentative distance value: set it to
zero for the starting node and to infinity for all other nodes.
3. For the current node, consider all of its unvisited neighbors
and calculate their tentative distances through the current
node. Compare the newly calculated tentative distance to the
currently assigned value and assign the smaller one.
4. When we are done considering all of the neighbors of the
current node, mark the current node as visited and remove it
from the unvisited set. A visited node will never be checked
again.
5. Move to the next unvisited node with the smallest tentative
distances and repeat the above steps which check neighbors and
mark visited.
6. If the destination node has been marked visited or if the
smallest tentative distance among the nodes in the unvisited
set is infinity then stop. The algorithm has finished.
7. Otherwise, select the unvisited node that is marked with the
smallest tentative distance, set it as the new “current node”,
and go back to step 3.
Section 2 defines the problem and the scenario designed within the context of this assignment.
Section 3 provides a set of instructions that you need to consider to accomplish this assignment. Section 4 gives a complete example. Finally, important remarks regarding submission
are outlined in Section 5.
2 Problem Definition
Railway network in an imaginary country, say Neverland, consists of a set of intersections
(I) and a set of rails (R) connecting some of them. There is a switch in every intersection
pointing to one of the rails going out of the intersection. Therefore, when a railway driver
enters one of the intersections, (s)he can leave only in a direction where the switch is pointing.
If the railway driver wants to go some other direction, (s)he needs to manually change the
switch, which leads to an increase in arrival time.
The problem that you are expected to address in this assignment is to help a railway driver
1A simulation that applies Dijkstra’s shortest path algorithm can be found here.
Page 2 of 14
BBM 204: Software Laboratory II
for finding his/her optimal route from source to the destination by implementing Dijkstra’s
algorithm over a dynamic digraph where the topology changes occasionally.
The idea behind using Dijkstra’s algorithm is to ensure time-dependent shortest path for the
railway driver. To elaborate it further, Figure 2 demonstrates an imaginary railway network.
In this network, there are 6 intersections (from A to F) and 9 rails (edges). The number next
to each rail is the distance (in km.) between the intersections that the rail connects. The
black rails indicate the rails where the switch in the source intersection is pointing.
A
B C
D
E
F
20
5
40
50
3
13
10
8
5
Figure 2: A example of a railway network
Considering this railway network, suppose a railway driver expects one route that gives least
arrival time from A to C. From the network, we can see that there exist three routes (A-BC, A-E-C, and A-D-E-C). It requires one switch change for the selection of the first route
(A-B-C) while it takes two switch changes if (s)he selects the second (A-E-C) or the third
route (A-D-E-C). As mentioned, every switch change leads to an additional time; and thus
negatively affects the total arrival time to the destination. So, there is a trade-off between
selecting longer rail or changing the switch’s direction at every intersection for the railway
driver.
The arrival time (TA) of a rail vehicle, such as tram, metro, and train, from source to destination is the sum of all the times taken for it to pass all the rails within the path P (i.e.,
TA =
PTri,j | ri,j ∈ P; P ⊆ R |i, j ∈ I | R, I 6= ∅). It is quite straightforward to calculate the
time to pass across a rail connecting X and Y (TrX,Y ) and it is equal to the distance (in km)
from X to Y (distX,Y ) divided by the rail vehicle’s velocity (vel):
TrX,Y
distX,Y /vel already points Y
C + (distX,Y /vel) otherwise (1)
where C is a time (in min) that takes railway driver to change switch’s direction, which should
be used in the case where the switch in X points any direction other than Y.
3 Assignment Task
This assignment expects you to implement Dijkstra’s shortest path algorithm and to apply it
on a digraph with dynamic topology.
Page 3 of 14
BBM 204: Software Laboratory II
The first thing you need to do is to construct a railway network. As it is the most case in
the real railway networks where there exist two rails pointing opposite directions between
any pair of intersections, you should also construct a directed graph to represent the railway
network instead of an undirected graph. Clearly saying, if there exists a rail from X to Y
then a rail in opposite direction (from Y to X) should also exist in the network.
You are provided three files and two of which are for the construction of railway network
(whereas the third file consists of various commands to ensure a dynamic digraph). Every
line in the first file begins with a label of an intersection followed by a set of intersections
as neighbors (each of which is separated by commas) and ends with a label of one of the
neighbors its switch is currently pointing.
A:B,C>C
B:A>A
C:A>A
From the file content above, it can be seen that intersection A has 2 neighbors, in other words,
there are 2 rails going from A, and the switch in A points to the intersection C. The second
file you are given contains the distances between every intersection in the railway network.
As the distance from X to Y is equal to that from Y to X, this file does not necessarily state
all the distances.
A-B 10
A-C 4
Every intersection in the railway network has i) a label, ii) a state variable indicating whether
it is under maintenance or not, and iii) a variable showing the total number of trains that
pass over itself. Every rail, however, has i) source and destination intersections, ii) a state
variable indicating whether the switch in the source intersection points it or not, iii) a state
variable that indicates whether it is broken or not, and iv) a variable storing the distance
between source and destination. Figure 3 gives an abstract representation of the corresponding
railway network that is constructed according to the topology which is stated in the files above.
Figure 4, however, gives an adjacency-list representation of this railway network.
After you are managed to construct the railway network, you can now move one step ahead
and it is time for you to make this network dynamic through a couple of commands that are
provided in the third file.
Page 4 of 14
BBM 204: Software Laboratory II
A B
name C
underMaintenance true
totalPasses 0
C
source A
destination C
isActive true
isbroken true
dist 4
name A
underMaintenance false
totalPasses 0
name B
underMaintenance false
totalPasses 0
source C
destination A
isActive true
isbroken false
dist 4
source B
destination A
isActive true
isbroken false
dist 10
source A
destination B
isActive false
isbroken false
dist 10
Figure 3: An abstract representation of a railway network
Commands
Rather than simply applying Dijkstra’s algorithm on a static graph, you are expected to
handle a dynamic graph where its topology changes occasionally as in the real-world. The
topology change occurs through a couple of commands provided in the third file as mentioned
earlier. Description of all the commands is provided below:
ˆ MAINTAIN {INTERSECTION}: It sets a specified intersection as under maintenance.
If one intersection is maintained, it should be treated as if it was removed from the
railway network. Therefore, one should ignore this intersection and thus all the rails
going to this intersection while finding optimal route until it is put into service again.
Input:
MAINTAIN A
Output:
COMMAND IN PROCESS >> MAINTAIN A
Command “MAINTAIN A” has been executed successfully!
ˆ SERVICE {INTERSECTION}: It puts specified intersection that is currently under
maintenance into service again.
Input:
SERVICE A
Output:
COMMAND IN PROCESS >> SERVICE A
Command “SERVICE A” has been executed successfully!
Page 5 of 14
BBM 204: Software Laboratory II
name C
underMaintenance true
totalPasses 0
source A
destination C
isActive true
isbroken true
dist 4
name A
underMaintenance false
totalPasses 0
name B
underMaintenance false
totalPasses 0
source C
destination A
isActive true
isbroken false
dist 4
source B
destination A
isActive true
isbroken false
dist 10
source A
destination B
isActive false
isbroken false
dist 10
Figure 4: A graph representation of a railway network
ˆ BREAK {SOURCE}>{DESTINATION}: It interrupts an existing connection/rail/link
between SOURCE and DESTINATION. When a rail is broken, one should ignore it during
the process of finding optimal route until it is repaired again.
Input:
BREAK A>B
Output:
COMMAND IN PROCESS >> BREAK A>B
Command “BREAK A>B” has been executed successfully!
ˆ REPAIR {SOURCE}>{DESTINATION}: It repairs an existing broken rail and puts it
into service.
Input:
REPAIR A>B
Output:
COMMAND IN PROCESS >> REPAIR A>B
Command “REPAIR A>B” has been executed successfully!
Page 6 of 14
Spring 2018
BBM 204: Software Laboratory II
ˆ ADD {INTERSECTION}: It creates a new intersection into the railway network.
Input:
ADD D
Output:
COMMAND IN PROCESS >> ADD D
Command “ADD D” has been executed successfully!
ˆ LINK {SOURCE}:{NEIGHBOR-DIST}+>{POINTING RAIL}: It connects newly added
SOURCE intersection with other existing ones. This command also adjusts the direction
of the switch in SOURCE intersection. Please note that you should also construct the
rails with opposite direction of what is provided as neighbors.
Input:
LINK D:A-12,B-7,C-4>C
Output:
COMMAND IN PROCESS >> LINK D:A-12,B-7,C-4>C
Command “LINK D:A-12,B-7,C-4>C” has been executed successfully!
ˆ ROUTE {SOURCE}>{DESTINATION} {vel}: It initiates a process that is finding optimal route between SOURCE and DESTINATION for a rail vehicle moving with a certain
velocity (vel) (km/h). Remember that you need to consider maintenance and repair
status of intersections and rails before you initiate, respectively. After the process is
completed, it may or may not have found a route. An appropriate message should be
displayed.
Input:
ROUTE A>D 3
Output:
COMMAND IN PROCESS >> ROUTE A>D 3
No route from A to D found currently!
Command “ROUTE A>D 3” has been executed successfully!
or
Output:
COMMAND IN PROCESS >> ROUTE A>D 3
Time (in min): 160,000
Total # of switch changes: 1
Route from A to D: A C D
Command “ROUTE A>D 3” has been executed successfully!
As explicitly stated above, you should print a warning message in the case of no route
found. Otherwise, you should print i) time (in min) taken for a rail vehicle to arrive
DESTINATION from SOURCE. Please refer to Section 2 for the calculation of total arrival
time, ii) total number of switch change that is necessary to ensure the least arrival time,
iii) labels of the intersections in the visiting order.
Page 7 of 14
Spring 2018
BBM 204: Software Laboratory II
The further commands are intended for testing your implementation, which reveals
every change that you are expected to perform in the railway network topology.
ˆ LISTROUTESFROM {INTERSECTION}: It lists all the rails (including those currently
being repaired) going from INTERSECTION in an alphabetical order.
Input:
LISTROUTESFROM C
Output:
COMMAND IN PROCESS >> LISTROUTESFROM C
Routes from C: A D
Command “LISTROUTESFROM C” has been executed successfully!
ˆ LISTMAINTAINS: It lists all the intersections that are currently under maintenance in
an alphabetical order.
Input:
LISTMAINTAINS
Output:
COMMAND IN PROCESS >> LISTMAINTAINS
Intersections under maintenance: A B
Command “LISTMAINTAINS” has been executed successfully!
ˆ LISTACTIVERAILS: It lists all the rails that are currently being pointed by all switches
in the intersections in an alphabetical order with respect to the source intersection.
Input:
LISTACTIVERAILS
Output:
COMMAND IN PROCESS >> LISTACTIVERAILS
Active Rails: A>C B>A C>A D>C
Command “LISTACTIVERAILS” has been executed successfully!
ˆ LISTBROKENRAILS: It lists all the rails that are currently broken with BREAK command in an alphabetical order.
Input:
LISTBROKENRAILS
Output:
COMMAND IN PROCESS >> LISTBROKENRAILS
Broken rails: A>B
Command “LISTBROKENRAILS” has been executed successfully!
Page 8 of 14
Spring 2018
BBM 204: Software Laboratory II
ˆ LISTCROSSTIMES: It lists every intersection with the total number of trains that pass
over that intersection thus far in alphabetical order. Note that, you should ignore an
intersection over which no rail vehicle passes.
Input:
LISTCROSSTIMES
Output:
COMMAND IN PROCESS >> LISTCROSSTIMES
# of cross times: A:1 C:1 D:1
Command “LISTCROSSTIMES” has been executed successfully!
ˆ TOTALNUMBEROFJUNCTIONS: It prints out total number of intersections (including
those that are currently under maintenance) in the railway network.
Input:
TOTALNUMBEROFJUNCTIONS
Output:
COMMAND IN PROCESS >> TOTALNUMBEROFJUNCTIONS
Total # of junctions: 4
Command “TOTALNUMBEROFJUNCTIONS” has been executed successfully!
ˆ TOTALNUMBEROFRAILS: It prints out total number of rails (including those that currently being repaired) in the railway network.
Input:
TOTALNUMBEROFRAILS
Output:
COMMAND IN PROCESS >> TOTALNUMBEROFRAILS
Total # of rails: 10
Command “TOTALNUMBEROFRAILS” has been executed successfully!
ˆ In the case of any command other than what are described above, the following message
should arise.
Input:
DUMMYCOMMAND
Output:
COMMAND IN PROCESS >> DUMMYCOMMAND
Unrecognized command “DUMMYCOMMAND”!
Page 9 of 14
Spring 2018
BBM 204: Software Laboratory II
4 A Complete Example
The implementation you are expected to design will take 4 parameters to be run. The order
of these parameters should be:
1. a complete path (including the file name and extension) of the file that describes railway
network topology
2. a complete path (including the file name and extension) of the file that states distances
of intersections
3. a complete path (including the file name and extension) of the command file
4. time for a switch change in an intersection (C in Eq. 1) in the network.
Suppose after your implementation is run with the following command as well as with the file
given thereafter, you get a network demonstrated in a figure given in the initial step.
java network.in distances.in commands.in 2
network.in distances.in commands.in
A:B,D>B
B:A,C>C
C:B,D>D
D:A,C,E>A
E:D>D
A-B 10
A-D 8
B-C 6
C-D 2
D-E 15
ROUTE A>E 3
BREAK A>D
ROUTE A>E 10
MAINTAIN C
ROUTE A>E 1
ADD G
LINK G:B-19,E-41>B
ROUTE A>E 6
LISTCROSSTIMES
Page 10 of 14
Spring 2018
BBM 204: Software Laboratory II
ˆ Initial step:
B
A C
D E
8
10 6
2
15
ˆ ROUTE A>E 3
COMMAND IN PROCESS >> ROUTE A>E 3
Time (in min): 464,000
Total # of switch changes: 2
Route from A to E: A D E
Command “ROUTE A>E 3” has been executed successfully!
B
A C
D E
8
10 6
2
15
ˆ BREAK A>D
COMMAND IN PROCESS >> BREAK A>D
Command “BREAK A>D” has been executed successfully!
B
A C
D E
8
10 6
2
15
Page 11 of 14
BBM 204: Software Laboratory II
ˆ ROUTE A>E 3
COMMAND IN PROCESS >> ROUTE A>E 10
Time (in min): 200,000
Total # of switch changes: 1
Route from A to E: A B C D E
Command “ROUTE A>E 10” has been executed successfully!
B
A C
D E
8
10 6
2
15
ˆ MAINTAIN C
COMMAND IN PROCESS >> MAINTAIN C
Command “MAINTAIN C” has been executed successfully!
B
A
D E
8
10 6
2
15
C
ˆ ROUTE A>E 1
COMMAND IN PROCESS >> ROUTE A>E 1
No route from A to E found currently!
Command “ROUTE A>E 1” has been executed successfully!
Page 12 of 14
BBM 204: Software Laboratory II
ˆ ADD G
COMMAND IN PROCESS >> ADD G
Command “ADD G” has been executed successfully!
B
A
D E
8
10 6
2
15
C
G
ˆ LINK G:B-19,E-41>B
COMMAND IN PROCESS >> LINK G:B-19,E-41>B
Command “LINK G:B-19,E-41>B” has been executed successfully!
B
A
D E
8
10 6
2
15
C
G
19
41
ˆ ROUTE A>E 6
COMMAND IN PROCESS >> ROUTE A>E 6
Time (in min): 704,000
Total # of switch changes: 2
Route from A to E: A B G E
Command “ROUTE A>E 6” has been executed successfully!
B
A
D E
8
10 6
2
15
C
G
19
41
Page 13 of 14
BBM 204: Software Laboratory II
ˆ LISTCROSSTIMES
COMMAND IN PROCESS >> LISTCROSSTIMES
# of cross times: A:3 B:2 C:1 D:2 E:3 G:1
Command “LISTCROSSTIMES” has been executed successfully!
5 Submission Notes
ˆ Do not miss the deadline.
ˆ Save all your work until the assignment is graded.
ˆ The assignment must be original, individual work. All the duplicate or Internet works
(even if a citation is provided) are both going to be considered as cheating.
ˆ You can ask your questions via Piazza and you are supposed to be aware of everything
discussed in there.
ˆ You will submit your work from https://submit.cs.hacettepe.edu.tr/index.php with the file hierarchy as below:
→
→ src.zip