Algorithms on Directed

Assignment 2 – Algorithms on Directed

Graphs (35%)

Overview

You task is to code a small collection of graph algorithms, based on your

directed_graph class for assignment 1 (all vertices and edges have positive

weights):

  • Shortest paths.
  • Strongly connected components.
  • Topological sort.

Besides the above, the class should offer an operation to solve the following

open question:

  • Consider each vertex as a city, vertex weight as the city’s population, and

the weight of each directed edge as the cost of delivering any amount of

goods from one city to another. Given a city that plans to deliver goods to

all other cities, can you find a way to deliver the goods to every other city

with the minimum average-delivery-cost per person? Your function should

return this minimum cost-per-person.

For example, in the above graph, A and C have the population of 800 and 400,

respectively, and it takes the cost of 900 to deliver any amount of goods from A to

C while there is no way to deliver the good directly from C to A.Suppose A -> B, A -> C, A -> C -> D, A -> B -> E are the paths you use to

deliver goods from A to other cities, your function should return ( cost(A->B) +

cost (A->C) + cost(C->D) + cost(B->E) ) / (the total population of

B,C,D,E) = (600+900+4000+3000)/(300+400+710+221) = 5. Your tasks is to

figure out the minimal return possible by determining the optimal paths for the

delivery. Note that, you can deliver any amout of goods at a fixed cost between

two adjacent cities; therefore, you only need to countcost(A-C) and cost(A->B)

once in this example.

The Code

You are provided with the following:

  • directed_graph_algorithms.cpp. The four methods present in the

skeleton are the entry point for the tests. As with the first assignment, you

should be able to complete the assignment within the

directed_graph_algorithms.cpp file. You main task is to implement the

four functions, which are not part of the class.

  • directed_graph.hpp. Please copy your submission for assignment 1 to

this file. The fully working implementation of a directed graph class in this

file will be reused by directed_graph_algorithms.cpp.

  • main.cpp. This is where you can do any testing you like.

The “run” button will compile and execute main.cpp, the “mark” button will run

directed_graph_algorithms.cpp against the tests.

You may modify any of these files as you see fit, e.g., adding extra functions and

extra classes, as long as the tests still execute.

Marking

As with assignment 1, this assignment will be marked against three components:

functionality, design and style.

Functionality will be marked exclusively by the tests, and constitutes 17% of the

subject’s total mark.

Design will be marked by your tutor and constitutes 12% of the subject’s total

mark. It does not depend on the functionality of your code. You may be asked

questions by your tutor to help them test your understanding of your code. It will

be marked qualitatively against the following rubric:• Pass The code shows basic understanding of how to employ data

structures to achieve a goal. The design should avoid unnecessary

data structures and should make reasonable use of iteration and recursion

when appropriate.

  • Credit The design shows a solid understanding of data structures and

demonstrate effective use of control structures to achieve the

program’s goals.

  • Distinction The design shows a high degree of understanding of how to

use data structures to achieve a goal efficiently, and demonstrate some

evidence that the design does not use unnecessary resources. The design

should be clean and efficient.

  • High Distinction The design demonstrates a high degree of understanding

of data structures and how to efficiently employ them to build algorithms

that not only meet technical goals, but support maintenance and future

development.

Style will also be marked by your tutor and constitutes 6% of the subject’s total

mark. It will be marked qualitatively against the following rubric:

  • Pass The code mostly uses some formatting standard and is somewhat

readable.

  • Credit The code adheres well to a formatting standard and variables are

well named.

  • Distinction At least as well formatted as for Credit standards, along with

sufficient inline commenting to explain the code.

  • High Distinction Excellent formatting and variable naming. Excellent,

judiciously employed comments that explain the code without just

repeating the code.

Extra explanations are available at

https://edstem.org/courses/3890/discussion/208882.

Marking Schedule

All being well, assuming you submit before the deadline and attend your Week 12

tutorial (in the class you are actually enrolled in – exceptions will only be made for

cases where attendance at your enrolled tutorial is impossible), we aim to return

the marks for the assignment within a week of the tutorial. The “mark” button will

become available two weeks before the due date, which is Friday 29 May 2020,

to give you some peacetime to focus on your assignment.

SubmissionYou will submit your work with the “mark” button on Ed. No other submissions will

be accepted. You are welcome to develop your code elsewhere, if that suits your

workflow, but remember it must compile and run on Ed. We are using the g++

compiler set to C++17 standard for this assessment. However code that compiles

with clang++ should also work with g++ (unless you’re doing something weird – so

check first!).

You may submit as many times as you like (in fact, repeated submission is an

expected part of the development process).

Due Date

Due date: The code submission of this assignment is due by 23:59 pm Sunday

14/06/2020.

Due date for late submission: A penalty (10% of the assignment’s full mark,

i.e., 3.5 marks) will be applied to code submissions after the due date yet before

23:59 pm Sunday 21/06/2020.

No code submission will be accepted after the due date for late submission.

Plagiarism Checking

All code will be checked for student misconduct and plagiarism using specialised

code similarity detection software.