1    Learning outcomes

In this assignment you will demonstrate your understanding of loops and if statements by writing a program that sequentially processes a ile of input data. You are also expected to make use of functions and arrays.

2    The story...

Traffic congestion detection and analysis aims to detect regions of a road network where traffic speed is slow and to analyse the congestion patterns, such as the source of a congestion.  It plays an important role in traffic optimisation.  For example, real-time traffic congestion detection can help navigation apps such as Google Maps to recommend faster routes, hence improving fuel efficiency and travel experience.  Meanwhile, traffic congestion pattern analysis can help authorities such as vicRoads make more efective traffic planning for major events such as AFL Grand Finals to reduce traffic congestions.

Figure 1 shows an example, where each coloured dot represents a traffic speed sensor in the freeway system of the metropolitan areas of california, USA1. The diferent colours of the dots represent diferent average traffic speed values recorded by the sensors for the last ive minutes.  A red colour suggests a low traffic speed, while a green colour suggests a high traffic speed.  If a navigation app can detect the low traffic speed at the red dots, it can suggest alternative routes to help users avoid these congested locations.

Figure 1：Traffic speed sensing (9：oo pm, 28 January 2o21, california, USA)

In this assignment, we are given a set of traffic speed sensor readings (in km/hour) that represent the average traffic speed at 5-minute intervals at diferent (sensor) locations.  The aim is to detect whether there are congestions at each location for the last 5 minutes, and if so, to identify the source of each congestion.  You do not need to be an e①peTt in tTa历c management oT sensoT technologies to complete this assignment.

1 Data 公。urce: https://pems.dot.ca.gov

Below is a sample set of input data.  The irst line contains a positive integer num-locations representing the number of sensor locations in the input data.  In the example below,  num-locations  =  10, meaning that there are 10 sensor locations.

starting from the second line, each line contains data of a sensor locations. Each line has up to 16 columns separated by spaces (‘ ,):

.  The irst column contains a unique 3-digit positive integer representing the ID of the sensor location.

.  The second column contains a positive integer representing the speed limit at the sensor location.

.  The third column contains a real number representing the latest aveTage tTaffic speed readings recorded by the sensor at the location at the last 5-minute interval.

.  The  next  1o  columns  each  contains  a real number representing the  average traffic speed readings recorded by the sensor at 5-minute intervals for the past 1o weeks on the current day of week and time of day. suppose the current time and day is 9:oo pm wednesday.  Then, column 4 is the average traffic speed reading between 8:55 pm and 9:oo pm on wednesday last week, column 5 is the average traffic speed reading between 8:55 pm and 9:oo pm on wednesday two weeks ago; . . .; and column 13 is the average traffic speed reading between 8:55 pm and 9:oo pm on wednesday 1o weeks ago.

Each average traffic speed value is a positive real number with 2 digits after the decimal point.  The average traffic speed values do not exceed the speed limit.

.  The last three columns contains IDs of the sensor locations at the “downstream” of the current sensor location, that is, the traffic lows from the current location to these locations. If a column contains a value of -1, it means there are no more downstream sensor locations.

The last line contains two real numbers representing traffic speed thresholds to indicate a congestion, which will be described and used in stage 3.

10

104  80  34.31  73.29  77.35  66.66  44.12  49.65  60.72  78.76  29.45  15.16  35.70  106  121  114

106  90  49.36  49.33  47.02  40.86  46.57  49.04  49.77  40.75  49.54  42.33  43.42  124  -1 114  90  80.85  81.50  66.26  84.71  50.63  17.01  70.02  54.95  82.38  28.54  69.71  132  -1 121  60  33.65  10.47  51.25  57.63  13.60  44.24  17.20  33.32  24.15  29.60  24.25  201  -1

124  40  31.13  36.52  24.10  29.71  28.05  16.02  32.55  15.17  36.31  30.95  20.39  221  351  -1 132  60  29.42  15.55  30.03  29.92  22.67  21.25  11.80  23.48  25.30  23.52  22.90  121  797  -1 201  80  43.27  06.62  10.43  12.28  21.59  32.42  22.72  22.11  27.61  21.36  27.77  -1

221  50  24.16  48.13  44.73  43.19  49.57  47.68  39.90  49.93  45.13  45.58  41.50  -1

351  90  77.83  86.72  82.94  85.29  85.66  85.58  81.95  84.71  88.00  89.49  84.69  104  797  -1 797  40  22.11  20.26  26.67  24.44  27.17  27.29  22.07  24.14  20.30  10.67  24.16  -1

0.6  0.8

The second line of the sample above represents sensor location #104.  Its speed limit and latest average traffic speed reading are 8o and 34.31, respectively.   Its past  average traffic speed readings are:  73.29, 77.35, 66.66, 44.12, 49.65, 60.72, 78.76, 29.45, 15.16, and 35.70.

You mag assume that the input is alwags coTTectlg foTmatted, and 0  <  num-locations  <   101.  The input is sorted by the sensor location ID in ascending order.

3    your Task

your task is to write a program that reads the input data and detects if there are congestions at any of the sensor locations, and if so, outputs the source of the congestions.  The assignment consists of four stages.

3.1    stage 1 - process the First sensor Location (6 Marks)

write a program that reads the irst two lines of the input data and prints out: num-locations, the ID of the irst sensor location, the speed limit, the latest average tra伍c speed, the histoTical aveTage (HA) tra伍c speed for the past 1o weeks of the irst sensor location, and the IDs of any downstream sensor locations (-1 should not be outputted).

Given a sensor location L with m (m = 1o in our case) past average tra伍c speed readings s0 , s1 , . . . , sm- 1 (excluding the latest average tra伍c speed), its historical average tra伍c speed is calculated as:

HA(L) =  si                                                                                                   (1)

The output of this stage given the above sample input should be (where“mac:”is the command prompt):

mac:  ./program  < test0.txt

stage  1

==========

num-locations:  10

ⅠD  of the  first  sensor  location: #104

speed  limit:  80

Latest  average traffic  speed:  34.31

Historical  average traffic  speed:  53.09

Downstream  sensor  locations:  #106  #121  #114

Here, 53.09 is the historical average tra伍c speed of the irst sensor location as calculated by Equation 1.

You should wTite functions to process this and the following stages where appropriate.

Hint:  To ensure the result accuracy, use double,s for storing the tra伍c speed readings and calculating the historical average. use X05.2f for the average speed output formatting. You may also read all input data before printing out for stage 1.

As this example illustrates, the best way to get data into your program is to save it in a text ile (with a “ .txt”extension, any text editor can do this), and then execute your program from the command line,  feeding the data in via input TediTection (using <).

In gouT pTogTam,  gou will still use  the standaTd input functions such  as  scanf（） to  Tead  the  data.  Input TediTection will diTect these functions  to  Tead the  data fTom  the fle,  instead  of asking gou to  tgpe  it in  bg hand.   This will be moTe  conuenient than tgping  out the test cases manuallg eueTg time gou test gouT pTo- gTam.  our auto-testing system will feed input data into your submissions in this way as well.  To simplify the marking, your program should not print anything except for the data requested to be output (as shown in the output example).

we will provide a sample test ile“test0.txt”on LMs. You may download this ile directly and use it to test your code before submission.  This ile is created under Mac os. under windows systems, the entire ile may be displayed in one line if opened in the Notepad app. You do not need to edit this ile to add line breaks. The‘\n, characters are already contained in the ile. They are just not displayed properly but the scanf（） function in C can still recognise them correctly.

3.2    stage 2 - calculate the Historical Average (5 Marks)

Now modify your program so that the historical average tra伍c speed of each sensor location is computed and visualised. You may assume that the historical average tra伍c speed values are within the range of (o , 1oo) (use X05.2f for the historial average output formatting).  on the same sample input data, the additional output for this stage should be (you need to work out how the visualisation works based on this example):

stage  2

==========

#104, HA:  53.09  l--+--+

#106, HA: 45.86  l--+--

#114, HA:  60.57  l--+--+-

#121, HA:  30.57  l--+-

#124, HA:  26.98  l--+

#132, HA:  22.64  l--+

#201, HA:  20.49  l--+

#221, HA: 45.53  l--+--

#351, HA:  85.50  l--+--+--+

#797, HA:  22.72  l--+

3.3    stage 3 - Detect congestions (5 Marks)

Now read the last line of the input, which contains two threshold parameter values a and β (O < a, β < 1), to help detect two typical types of congestions.  consider a sensor location L with speed limit SL , latest average tra伍c speed CL , and historical average tra伍c speed HL .

1.  Recurring congestions (REC-CONGESTⅠON): we say that a recurring congestion has occurred at a sensor location L, if its latest average tra伍c speed CL  is substantially lower than its speed limit SL  but not substantially lower than its historical average, that is:

CL  < a . SL  and CL  > β . HL                                                                                (2)

2.  Non-recurring  congestions  (NON-REC-CONGESTⅠON): we  say that a non-recurring congestion has oc- curred at a sensor location L, if its latest average tra伍c speed CL  is substantially lower than both its speed limit SL  and its historical average, that is:

CL  < a . SL  and CL  < β . HL                                                                                (3)

In this stage, your task is to detect and output if either types of congestions have occurred at each of the sensor locations. on the same sample input data, the additional output for this stage should be:

Stage  3

==========

#104:  NON-REC-CONGESTⅠON

#106:  REC-CONGESTⅠON

#114:  NO-CONGESTⅠON

#121:  REC-CONGESTⅠON

#124:  NO-CONGESTⅠON

#132:  REC-CONGESTⅠON

#201:  REC-CONGESTⅠON

#221:  NON-REC-CONGESTⅠON

#351:  NO-CONGESTⅠON

#797:  REC-CONGESTⅠON

Here, location #104 has a speed limit SL  = 8O.  Its latest average tra伍c speed CL  = 34.31 is smaller than a. SL  = O.6X8O = 48.O, while CL is greater than β . HL  = O.8X53.O9 = 42.47.  Thus, there is a non-recurring congestion at location #104.

Hint: You should store the HA values calculated in stage 2 and reuse them for this stage.

3.4    stage 4 - Detect sources of the congestions  (4 Marks)

In this stage, we trace back the sources (that is, source locations) of the congestions.  when a congestion has been detected at a location L, we examine if any of its downstream locations also has a congestion.  If there is a congestion at some downstream location Ld , we further examine the downstream locations of Ld. The process is performed recursively, until there are no more downstream sensor locations with congestions. The sensor locations that have congestions while their downstream sensor locations do not have congestions are the sources of the congestions, and your program should output these sensor locations.

on the same sample input data, the additional output for this stage should be:

Stage 4

==========

#104:  source（s）  -  #106 #201

#106:  source（s）  - #106

#114:  NO-CONGESTⅠON

#121:  source（s）  - #201

#124:  NO-CONGESTⅠON

#132:  source（s）  -  #797 #201

#201:  source（s）  - #201

#221:  source（s）  - #221

#351:  NO-CONGESTⅠON

#797:  source（s）  - #797

In the example above, for sensor location #104, there are three downstream locations #106, #121, and $114. Both #106 and #121 are congested (see output from stage 3).

.  Location #106 has only one downstream location, which is #124 and is not congested.  Thus, #106 is one of the sources of the congestion at #104.

.  Location #121 also has only one downstream location, #201, which is congested and does not have any further downstream locations. Thus, #201 is another source of the congestion at #104.

Hint:  You can use loops instead of recursive functions for this stage, with the help of an array Q to store the sensor locations to be considered.  The algorithm to trace the source of a congestion at location L works as follows:

1. At start, Q is an empty array without any elements.

2.  sensor location L (that is, its ID) is added to Q as its irst element.

3.  Now we loop through locations in Q starting from the irst location.

4. when the loop reaches a location L、in Q, we examine if any of its downstream locations are also congested. If so, we add those congested downstream locations to be after the last existing location in Q (if those congested downstream locations are not in Q already). If not, we have found a congestion source location, which is outputted.

5.  The loop ends when we reach the last location in Q and there are no more congested locations to be added to Q.

You may assume that there are no “congestion cycles”, that is, there will not be sensor locations such as L1  一 L2  一 L3  一 . . . 一 L1   (“Li  一 Lj”denotes that Lj  is a downstream location of Li ) where all locations are congested.

4    submission and Assessment

This assignment is worth 2o% of the inal mark. A detailed marking scheme will be provided on LMs.

submitting your code. To submit your code, you will need to: (1) Log in to LMs subject site, (2) Nav- igate to “Assignment 1”in the “Assignments” page, (3) click on “Load Assignment 1 in a new window”, and (4) follow the instructions on the Gradescope “Assignment 1”page and click on the “submit” link to make a submission.  You can submit as many times as you want to.  onlg the last submission made before the deadline will be marked. submissions made after the deadline will be marked with late penalties as detailed at the end of this document.  Do  not submit after the deadline unless a late submission is intended.  Two hidden tests will be run for marking purposes. Results of these tests will be released after the marking is done.

You can (and should) submit both early and often - to check that your program compiles correctly on our test system, which may have some diferent characteristics to your own machines.

Testing on your own computer. You will be given a sample test ile te网t0.txt and the sample output te网t0一output.txt. You can test your code on your own machine with the following command and compare the output with te网t0一output.txt:

mac:  ./program  < te网t0.txt       /*  Here ‘<,  feed网  the  data  from  te网t0.txt  into  program  */

Note that we are using the following command to compile your code on the submission testing system (we name the source code ile program.c).

gcc  一wall  一网td=c17  一o  program program.c  一lm

The lag“一网td=c17”enables the compiler to use a modern standard of the C language - C17.  To ensure that your submission works properly on the submission system, you should use this command to compile your code on your local machine as well.  If you are using Grok to prepare your assignment, you may use the following command to compile it in Grok Terminal, which only supports C11 but should be close enough.

gcc  一wall  一网td=c11  一o  program program.c  一lm