COMP2521 Data Structures and Algorithms

Wikipetia's network consists of computers and connections between pairs of computers. Each computer has a security level between 1 and 10,and takes a certain amount of time to poodle.The security level of a computer determines what other computers it is allowed to communicate with:a computer with security level X can only send to computers with security  level  X+1  or  smaller.Each  connection is bidirectional and has a transmission time associated with it,which is the amount of time it would take to send something (such as your pug)from the computer at one end of the  connection,to the computer at the other end.

Here is an example network:

In the above network,for example,computer 4 has a security level of two (as it has two rings around it),and would take 80 seconds to poodle.After it has been poodled,it could send the pug to computer O (which would take 1 second)and computer 1 (which would take 2 seconds),but not computer 5,as it has a security level of 4.

Change  into  the  directory  you  created  for  the  assignment  and  run  the  following command:

$unzip /web/cs2521/24T2/ass/ass2/downloads/files.zip

If you're working at home,download files.zip by clicking on the above link and then unzip the downloaded file.

You should now have the following files:

Makefile This controls compilation of the program.You only need to modify this if you create additional files for your implementation.

poodle.h This contains struct definitions and function prototypes for the functions you willcomplete in the tasks below. You must not modify this file.

poodle.c This is a stub file for you to complete the tasks below.

testPoodle.c This is a main program for testing your code.You should not modify this file unless you know what you're doing.

data/ This is a directory containing network data files.The format of these files are described below.

task[1234]/  These are directories containing test data files and expected outputs.The files ending with .in are test data files,while the corresponding .exp files contain expected outputs.

First,compile the original version of the files using the make command.This willproduce one  executable:testPoodle.

Note that in this assignment,you are permitted to create as many supporting files as you like.This allows you to compartmentalise your solution into different files.For example, you could implement a Graph ADT in Graph.c and Graph.h.To ensure that these files are actually included in the compilation,you will need to edit the Makefile;the  provided Makefile contains instructions on how to do this.

Network Data Files

Network data files contain the details of the network.Each file is formatted as follows:

·The first line contains two integers representing the number of computers n and the number of connections m.

·Then,for each computer there is a line containing two integers:the security level of the computer  and  the  time  taken  to  poodle  it.The  i-th  of  these  lines  (0≤i≤n-1) corresponds to computer i.

·Then,for each connection there is a line containing three integers:the two computers that it connects and the time taken to transmit anything across it.

230

340

370

350

280

440

190

012

233

452

563

041

412

151

523

262

633

The first line indicates that there are 7 computers and 10 connections.Each of the following seven lines describes a computer.For example,computer O has a security leve of 2 and takes 30 seconds to poodle.Each  of the ten  remaining  lines describes  a connection.For example,there is a connection between computers 0 and 1 that takes 2 seconds to transmit across.

The provided program in testPoodle.c will read the data file,so you won't need to do any file reading yourself,but you should understand the format of the file so that you can create your own networks for testing.

Test  Data  Files

Test data files contain the inputs for tests.The format of a test data file depends on the task,but each one always begins with two lines which indicate the task being tested (1-4), and the name of the network data file used in that test.More details are available under the Testing section of each task.

Inputs

In each of the tasks below,you will be given network data as input.This data will be given as an array of computers and an array of connections.Computers and connections are represented   by   the   following   structs:

struct   computer {

int      securityLevel; int   poodleTime;

};

struct connection {

};

In the computer struct,securityLevel is the security level of the computer,and will always  be  an  integer  between   1  and   10(inclusive).poodleTime  is  the  amount  of  time  it takes to poodle the computer,and will always be a positive integer.

In the connection struct,computerA and computerB are the  numbers  (IDs)of the computers at the endpoints of the connection,and will always be between O and n-1 (where n is the number of computers),and transmissionTime willalways be a positive integer.In each connection struct,computerA and computerB will always be different.

The computers will be given in an array of size n where index i contains the details of computer i.The connections willbe given in an array of size m(where m is the number of connections).The array of connections will not contain duplicate connections.Since connections    are    bidirectional,this    means    the     connections    (v,w)and    (w,v)cannot    both appear  in the array.

Before you poodle any computers,you would like to first probe the network by sending a harmless pug along different paths of computers to scan their contents.Your pug will move from computer to computer,scanning the contents of each computer before moving  on  to  the  next.You  would  like  to  measure  how  long  this  takes.

Forexample,consider the following network:

Suppose  the   path  is  0-4-1-5-6.The  total  amount of time taken to probe  this   path   is  30+

1+80+2+40+1+40+3+90=287                    seconds.

As you don't  have all the details about the network yet,some paths that you try may be invalid.A path can be invalid in two different ways:(1)a computer does not have a connection to the next computer on the path,or (2)a computer does not have  permission

However,you can still measure the time taken betore the probe tails,which is 40+2+80+ 1+30+2+40=195     seconds.

A path may contain the same computer more than once.However,since each computer is only scanned the first time it is visited,subsequent visits to a computer take no time (0 seconds).For example,the path 1-4-0-1would take 40+2+80+1+30+2+0=155 seconds.

If a computer appears multiple times in a row in a path,it should be treated as if it only appeared once.For example,the path   0-0-1-1-0-0 should be treated as 0-1-0.

Your task is to implement the following function:

The function takes information about the network via an array of computers and an array of connections,and the path as an array of computer IDs,and returns the result of the probe in a struct  probePathResult.

The  struct  contains  two  fields:status,which  indicates  whether  the  probe  ran  to completion or the reason if it didn't,and elapsedTime,which indicates the total amount of time taken before the probe completed or failed.The status field should be set to:

·SUCCESS if the probe ran to completion

·NO_CONNECTION  if  the  probe  failed  because  a  computer  did  not  have  a  connection  to the next computer on the path

·NO_PERMISSION   if  the   probe   failed   because   a   computer   had   a   connection   but   did   not have permission to communicate with the next computer on the path

Note that it is not possible for a probe to fail for two different reasons,because a probe stops as soon as one of the above problems occur.

Constraints

To earn most of the marks for this task,you may assume the following:

·The number of computers will be at most 100.   ● The number of connections will be at most 100. ·The length of the path will be at most 250,000.

To earn all of the marks for this task,you must assume the following more challenging constraints:

·The number of computers will be at most 250,000.

As it is not necessarily easy to solve the problem with the more challenging constraints, you may want to solve the problem with the easier constraints first,and then come back to solve the challenge later.

Testing

All tasks can be tested using the testPoodle program.The program takes one command- line argument:the name of a test data file.

Test  data  files  contain  the  parameters  for  a  test  case.The  format  of  a  test  data  file depends on the task,but it always begins with one integer,which is the number of the task being tested.

You can test Task 1 by running ./testPoodle with one of the test data files in the task1 directory.The format of the test data file is as follows:

·The first line contains the integer 1.

·The  next  line  contains  the  name  of  a   network  data  file  (not   including  the  data/ directory prefix).

·The next line contains an integer representing the length of the path,P.

·The final line contains P integers representing the IDs of the computers along the path. Note that this path may contain multiple of the same computer ID.

For example,here is a test data file for Task 1:

1

network-1a.txt

5

04156

This  means  this test  is  for task  1,it  uses  the  network  given  in  data/network-1a.txt,the probe path has length 5,and the probe path is O-4-1-5-6.

The expected output for this test is:

$./testPoodle task1/1.in

Probe        path:0->4        ->1        ->5->6

Result:Success

Time    taken:287    seconds

You can run all provided tests using the command:

$./autotest 1

Now that you have gathered information about the network,you would like to choose a computer to start at that willallow you to poodle as many computers as possible.Note that computers are able to send to multiple computers at once.

For example,consider the following network (times are intentionally not shown):

The  optimal  source  computer  is  computer  8,as  you  will  be  able  to  poodle  eight computers:O,1,2,4,5,6,7  and  8.Starting  at  any  other  computer  will result  in  you poodling fewer computers.For example,starting at computer 3 will only allow you to poodle three computers:1,3 and 6.Note that the time taken is not relevant here.

Your task is to implement the following function:

The struct contains three fields:sourceComputer,which  indicates the  optimal  source computer,numComputers,which indicates the number of computers that can be poodled, and computers,which is a dynamically allocated array containing those computers.The array must be sorted  in ascending order.

If there are multiple optimal source computers and/or multiple sets of poodled computers as a result,you may return any of them.

Constraints

Testing

You can test task 2 by running ./testPoodle with one of the test data files in the task2 directory.The format of the test data file is as follows:

·The first   line   contains  the   integer   2.

·The next line contains the name of a network data file (not including the data/ directory prefix).

For  example,here  is  a  test  data  file  for  task  2:

2

network-2a.txt

This means this test is for task 2 and it uses the network given in data/network-2.txt. The  expected  output  for  this  test   is:

$./testPoodle task2/1.in

Source  computer:computer  8

Number  of  reachable  computers:8 Reachable computers:

-computer   0 -Computer   1 -Computer  2 -Computer  4 -Computer  5 -computer   6 -computer   7 -Computer  8

You can run all provided tests using the command:

$./autotest 2

Now   it   is   time   to   take   over   the   world   (ahem,network)with   your   mischief!Given   a   source computer,your aim is to poodle as many computers as possible,as quickly as possible.

For   example,consider   the   following    network:

Suppose your source computer is computer 2.To poodle all the computers as quickly as possible,it should be sent along these paths (highlighted in dotted red):

The  following  table  summarises  when  each  computer  will   be   poodled,and  which computers each computer will send your pug to after it has been poodled.

The function takes information about the network and a source computer,and returns a plan to poodle computers as quickly as possible that details,for each computer (that can be poodled),the quickest time that it can be poodled,and the computers that it will need to send the pug to after it has been poodled,in a struct poodleResult.

The poodleResult struct will contain the same kind of information as in the table shown above.The struct contains two fields:numSteps,which is the number of steps in the plan, which is equal to the number of computers that can be poodled,and steps,which is a dynamically  allocated  array  of  struct  steps.Each  struct  step  contains  three  fields: computer,which is the ID of a computer that will be poodled,time,which is the time that it willbe poodled,and recipients,which is a linked list of computers that it will send the pug to after it has been poodled.

The array must be sorted in ascending order by time,and each list of recipients must be sorted in ascending order by computer ID.If multiple computers will be poodled at the same time,they may be placed in any order.If there are multiple valid plans (that would result in computers being poodled as quickly as possible),then you may return any of them.

Assumptions

For simplicity,assume that a computer is able to send to multiple computers at the same time.

Constraints

·The number of computers will be at most 100.

● The number of connections will be at most 100.

Testing

You can test task 3 by running ./testPoodle with one of the test data files in the task3 directory.The format of the test data file is as follows:

·The first line contains the integer 3.

·The  next  line  contains  the  name  of  a  network  data  file  (not  including  the  data/ directory prefix).

·The next line contains the ID of the source computer. For example,here is a test data file for task 3:

This  means  this  test  is  for  task  3,it  uses  the  network  given  in  data/network-3a.txt,and the source computer is 2.

The  expected  output  for  this  test  is:

$./testPoodle task3/1.in

Plan:

-computer 2 poodled at 1 seconds -pug     sent    to:3,5

-computer 3 poodled at 5 seconds -pug   sent   to:0

-computer 0 poodled at 7 seconds -pug   sent   to:4

-computer 5 poodled at 8 seconds -pug   sent   to:6

-computer 4 poodled at 9 seconds -pug    sent    to:1

-computer 6 poodled at 11 seconds -computer 1 poodled at 16 seconds

You  can  run  all  provided  tests  using  the  command:

$./autotest 3

You have upgraded your pug!Now,whenever a computer B is poodled as a result of a computer A sending the pug to B,the security level of  B will be increased to the same level as A (if it was lower).A computer can be poodled multiple times if needed to increase  its  security  level.This  will  allow  you  to  poodle  more  computers  than  before!

Forexample,consider  the  following    network:

If  you  start  at  computer  1,then  you  will   be  able  to  poodle  computer   1  after  20  seconds, and  poodle  computer  2  after  52  seconds.With  your  upgraded  pug,computer  2  can  send be poodled atter 13 more seconds,which is a total ot 8/seconds Your task is to implement the following function:

The function takes information about the network and a source computer,and returns,for each computer (that can be poodled),the quickest time that it can be poodled (for the first   time)in  a  struct  poodleResult.This   is   similar   to   task   3,but   in   task  4,the recipients field should be ignored.

The array  must  be  sorted  in  ascending  order  by  time.If multiple computers will  be poodled at the same time,they may be placed in any order.

You must also describe your solution in detail in a comment above the advancedPoodle function.If you do not do this,your mark for this task will be capped at 12/15.

Assumptions

For simplicity,assume that a computer is able to send to multiple computers at the same time.

Constraints

·The number of computers will be at most 100.

● The number of connections will be at most 100.