Description
1. Overview
Write a “Graph” Class Library in C++, with its interface given in graph.h and its implementation in graph.tpp .
1.1. Aims
Smart Pointers
Exception Handling
Lambda Functions
Custom Iterators
Function and Class templates
Operator Overloading
Friends
Namespaces
1.2. Description
In this assignment, you will write a Generic Directed Weighted graph (GDWG) with value-like semantics in C++. Both the data
stored at a node and the weight stored at an edge will be of generic types. Both generic types may be different. For example,
here is a graph with nodes storing std::string and edges weighted by int:
gdwg::Graph<std::string,int> g;
Formally, this directed weighted graph G=(N,E) will consist of a set of nodes N and a set of weighted edges E. Give a node, an
edge directed into it is called an incoming edge and an edge directed out of it is called an outgoing edge. The in-degree of a
node is the number of its incoming edges. Similarly, the out-degree of a node is the number of its outgoing edges. Given a
directed edge from src to dst, src → dst, src is the source node and dst is known as the destination node. G is a multi-edged
graph, as there may be two edges from the same source node to the same destination node with two different weights.
However, all nodes are distinct, as they contain different data values.
All nodes in the graph are unique.
Between any two nodes (or a node and itself), all edges must be unique
2. Your task
2.1 Constructors & Destructors
2019/10/2 COMP6771 – Advanced C++ Programming – 19T2
https://cgi.cse.unsw.edu.au/~cs6771/19T2/assignments/dg/index.html 2/12
Name Constructor
Description
and Hints
Examples
Default
Constructor
gdwg::Graph<N, E>
The default
constructor for
a graph.
gdwg::Graph<N, E> a;
Constructor
gdwg::Graph<N, E>(
std::vector::const_iterator,
std::vector::const_iterator
)
Takes the start
and end of a
const_iterator
to a
std:vector
and adds
those nodes to
the graph.
std::vector v{“Hello”, “how”, “are”
gdwg::Graph<std::string, double> b{v.begin(),v.e
Constructor
gdwg::Graph<N, E>(
std::vector<std::tuple<N, N, E>>::const_iterator,
std::vector<std::tuple<N, N, E>>::const_iterator
)
Iterators over
tuples of
(source node,
destination
node, edge
weight) and
adds them to
the graph. You
are
responsible for
creating nodes
if they don’t
exist as you
iterate
through.
std::string s1{“Hello”};
std::string s2{“how”};
std::string s3{“are”};
auto e1 = std::make_tuple(s1, s2, 5.4);
auto e2 = std::make_tuple(s2, s3, 7.6);
auto e = std::vector<std::tuple<std::string, std::
gdwg::Graph<std::string, double> b{e.begin(), e.en
Constructor gdwg::Graph<N, E>(std::initializer_list)
A constructor
that takes an
initialiser list
of Nodes to
populate the
graph.
gdwg::Graph<char, std::string> b{‘a’, ‘b’, ‘x’, ‘y
Copy
Constructor
gdwg::Graph<N, E>(const gdwg::Graph<N, E>&)
gdwg::Graph<std::string, int>
gdwg::Graph<std::string, int> aCopy{a};
Move
Constructor
gdwg::Graph<N, E>(gdwg::Graph<N, E>&&)
gdwg::Graph<std::string, int> a;
gdwg::Graph<std::string, int> aMove{std::move(a)};
Destructor ~gdwg::Graph<N, E>() N/A
2.2. Operations
Name Operator Description Examples
Exception:
Why
thrown &
what
message
Copy
Assignment
gdwg::Graph<N, E>& operator=(const gdwg::Graph<N, E>&)
A copy
assignment
operator
overload
a = b; N/A
Move
Assignment
gdwg::Graph<N, E>& operator=(gdwg::Graph<N, E>&&)
A move
assignment
operator
a = std::move(b); N/A
2.3. Methods
Prototype Description Usage
Exception: Why
& what message
2019/10/2 COMP6771 – Advanced C++ Programming – 19T2
https://cgi.cse.unsw.edu.au/~cs6771/19T2/assignments/dg/index.html 3/12
bool InsertNode(const N& val)
Adds a new node with
value val to the graph.
This function returns
true if the node is
added to the graph
and false if there is
already a node
containing val in the
graph (with the graph
unchanged).
std::string s{“a”};
g.InsertNode(s); N/A
bool InsertEdge(const N& src, const N& dst, const E& w)
Adds a new edge src
→ dst with weight w.
This function returns
true if the edge is
added and false if the
edge src → dst with
weight w already
exists in the graph.
Note: Nodes are
allowed to be
connected to
themselves.
std::string u{“c”};
g.InsertEdge(“a”,u,1);
Condition:
src or dst no
be found in
Throw:
std::runtime
With string
“Cannot call
Graph::Inse
when either
node does n
bool DeleteNode(const N&)
Deletes a given node
and all its associated
incoming and
outgoing edges. This
function does nothing
if the node that is to
be deleted does not
exist in the graph.
Hint: if you are using
weak ptrs for edges
you may be able to do
this quite simply. This
function returns an
boolean as to whether
the item has been
removed or not (true
if removed).
g.DeleteNode(“b”) N/A
bool Replace(const N& oldData, const N& newData)
Replaces the original
data, oldData, stored
at this particular node
by the replacement
data, newData. If an
exception is not
thrown, this function
returns false if a node
that contains value
newData already
exists in the graph
(with the graph
unchanged) and true
otherwise.
g.Replace(“a”, “e”)
Condition:
node that co
value oldDat
found
Throw:
std::runtime
With string
“Cannot call
Graph::Repl
node that do
exist”
void MergeReplace(const N& oldData, const N& newData)
All instances of node
oldData in the graph
are replaced with
instances of newData.
After completing,
every incoming and
outgoing edge of
oldData becomes an
incoming/ougoing
edge of newData,
except that duplicate
edges must be
removed. Examples at
the bottom of the
table.
g.MergeReplace(“c”, “e”)
Condition:
node cannot
in the graph
Throw:
std::runtime
With string
“Cannot call
Graph::Merg
on old or ne
they don’t e
graph”
2019/10/2 COMP6771 – Advanced C++ Programming – 19T2
https://cgi.cse.unsw.edu.au/~cs6771/19T2/assignments/dg/index.html 4/12
void Clear()
Remove all nodes and
edges from the graph.
New nodes or edges
can be added to the
graph afterwards.
g.Clear() N/A
bool IsNode(const N& val);
Returns true if a node
with value val exists
in the graph and false
otherwise.
g.IsNode(“a”) N/A
bool IsConnected(const N& src, const N& dst);
Returns true if the
edge src → dst exists
in the graph and false
otherwise.
g.IsConnected(“e”,”b”)
Condition:
src or dst is
the graph
Throw:
std::runtime
With string
“Cannot call
Graph::IsCo
if src or dst
don’t exist in
graph”
std::vector GetNodes()
Returns a vector of all
nodes in the graph.
Sorted by increasing
order of node.
g.GetNodes() N/A
std::vector GetConnected(const N& src)
Returns a vector of
the nodes (found from
any immediate
outgoing edge)
connected to the src
node passed in.
Sorted by increasing
order of node (of
those nodes that are
connected).
g.GetConnected(“e”)
Condition:
not in the gr
Throw:
std::out_of_
With string
“Cannot call
Graph::GetC
if src doesn’
the graph”
std::vector GetWeights(const N& src, const N& dst)
Returns a vector of
the weights of edges
between two nodes.
Sorted by increasing
order of edge. These
edges are all outgoing
edges of src toward
dst.
g.GetWeights(“e”,”b”)
Condition:
src or dst is
the graph
Throw:
std::out_of_
With string
“Cannot call
Graph::GetW
src or dst no
exist in the
const_iterator find(const N&, const N&, const E&);
Returns an iterator to
the found edge in the
graph. If the edge is
not found the
equivalent value of
gdwg::Graph<N, E>::cend() is
returned.
gwdg::Graph<std::string, int> g;
std::string a1{“e”};
std::string a2{“i”};
int e = 8;
auto it = g.find(a1, a2, e)
N/A
bool erase(const N& src, const N& dst, const E& w)
Deletes an edge from
src to dst with weight
w, only if the edge
exists in the graph.
This function returns
an boolean as to
whether the item has
been removed or not
(true if removed). If
the edge is not in the
graph it returns false.
g.erase(“b”, “c”, 1) N/A
2019/10/2 COMP6771 – Advanced C++ Programming – 19T2
https://cgi.cse.unsw.edu.au/~cs6771/19T2/assignments/dg/index.html 5/12
const_iterator erase(const_iterator it);
This function removes
the position at the
location the iterator
points to. This
function returns an
iterator to the
element AFTER the
one that has been
removed. If no erase
can be made, the
equivalent of
gdwg::Graph<N, E>::end() is returned.
gwdg::Graph<std::string, int> g;
auto it = g.find(“e”, “i”, 8);
if (it != g.end()) {
g.erase(it);
}
N/A
const_iterator cbegin();
Returns a
const_iterator pointing
to the first in the
container. A
const_iterator is an
iterator that points to
const content. This
iterator can be
increased and
decreased (unless it is
itself also const), but
it cannot be used to
modify the contents it
points to, even if the
content it points to is
not itself const.
auto it = g.cbegin() N/A
const_iterator cend();
Returns a
const_iterator pointing
to the past-the-end
element in the
container. A
const_iterator is an
iterator that points to
const content. This
iterator can be
increased and
decreased (unless it is
itself also const), but
it cannot be used to
modify the contents it
points to, even if the
content it points to is
not itself const. If the
container is empty,
this function returns
the same as
vector::cbegin. The
value returned shall
not be dereferenced.
auto it = g.cend() N/A
const_reverse_iterator crbegin();
Returns a
const_reverse_iterator
pointing to the last
element in the
container. A
const_reverse_iterator
is a reverse iterator
that points to const
content. This iterator
can be increased and
decreased (unless it is
itself also const), but
it cannot be used to
modify the contents it
points to, even if the
content it points to is
not itself const.
auto it = g.crbegin() N/A
2019/10/2 COMP6771 – Advanced C++ Programming – 19T2
https://cgi.cse.unsw.edu.au/~cs6771/19T2/assignments/dg/index.html 6/12
const_reverse_iterator crend();
Returns a
const_reverse_iterator
pointing to the beforethe-first element in
the container. A
const_reverse_iterator
is a reverse iterator
that points to const
content. This iterator
can be increased and
decreased (unless it is
itself also const), but
it cannot be used to
modify the contents it
points to, even if the
content it points to is
not itself const. If the
container is empty,
this function returns
the same as
vector::crbegin. The
value returned shall
not be dereferenced.
auto it = g.crend() N/A
const_iterator begin(); Exactly the same as
cbegin()
auto it = g.begin() N/A
const_iterator end(); Exactly the same as
cend()
auto it = g.end() N/A
const_reverse_iterator rbegin(); Exactly the same as
crbegin()
auto it = g.rbegin() N/A
const_reverse_iterator rend(); Exactly the same as
crend()
auto it = g.rend() N/A
MergeReplace examples
Format is (N_src, N_dst, E)
Example 1 – basic
Operation: MergeReplace(A, B)
Graph before: (A, B, 1), (A, C, 2), (A, D, 3)
Graph after : (B, B, 1), (B, C, 2), (B, D, 3)
Example 2 – duplicate edge removed
Operation: MergeReplace(A, B)
Graph before: (A, B, 1), (A, C, 2), (A, D, 3), (B, B, 1)
Graph after : (B, B, 1), (B, C, 2), (B, D, 3)
Example 3 – Diagramatic
2.4. Friends
2019/10/2 COMP6771 – Advanced C++ Programming – 19T2
https://cgi.cse.unsw.edu.au/~cs6771/19T2/assignments/dg/index.html 7/12
In addition to the operations indicated earlier, the following operations should be supported as friend functions. Note that these
friend operations don’t modify any of the given operands.
Name Operator Description
Equal bool operator==(const gdwg::Graph<N, E>&, const gdwg::Graph<N, E>&) True if the two graphs contain the same nodes and edges.
Not
Equal
bool operator!=(const gdwg::Graph<N, E>&, const gdwg::Graph<N, E>&) True if the two graphs do not contain the same nodes or ed
Output
Stream
std::ostream& operator<<(std::ostream&, const gdwg::Graph<N, E>&)
Prints out the graph in the following format:
[node1][1 space](
[2 spaces][node1_connected_node1][1 space][pipe][1 sp
[2 spaces][node1_connected_node2][1 space][pipe][1 sp
[etc etc]
)
[node2][1 space](
[2 spaces][node2_connected_node1][1 space][pipe][1 sp
[2 spaces][node2_connected_node2][1 space][pipe][1 sp
[etc etc]
)
[node3][1 space](
[2 spaces][node3_connected_node1][1 space][pipe][1 sp
[2 spaces][node3_connected_node2][1 space][pipe][1 sp
[etc etc]
)
[etc etc]
For example, for gdwg::Graph<int, int>, an output may be
1 (
5 | -1
)
2 (
1 | 1
4 | 2
)
3 (
2 | 2
6 | -8
)
4 (
1 | -4
5 | 3
)
5 (
2 | 7
)
6 (
2 | 5
3 | 10
)
Note that output is sorted by 1) Src node (increasing order
node (increasing order); then 3) Edge weight (increasing o
Note that there is a newline after the last ‘)’
Note that if a node has no outgoing edges then you should
such as:
Node 7 has no outgoing edges:
7 (
)
2019/10/2 COMP6771 – Advanced C++ Programming – 19T2
https://cgi.cse.unsw.edu.au/~cs6771/19T2/assignments/dg/index.html 8/12
3.5. Your “Edge” Custom Iterator
You are required to define an iterator class gdwg::Graph<N, E>::const_iterator.
The iterators will come in a const form. The iterator should respond to the *, ++, –, == and != operators
When iterating through your graph the order of iteration should be based on the operator< for the underlying node type N
Your iterators should be appropriately declared as bi-directional. You should implement and test the complete bi-directional
iterator functionality. This includes pre/post incre- ment and decrement. The post-increment/decrement operations should
return a copy of the value pointed to before the increment/decrement is performed.
We will assume that all iterators are invalidated after any modification of the graph
3.5.1. Iterator Operators & Behaviour
Iterator operators should have the same structure/schema as discussed in week 7 lectures
The value_type within your iterator should be
std::tuple<N, N, E>
The reference type within your iterator should be
std::tuple
. Note that this means that when returning references, you cannot return a reference to your value type. Instead, you should
write
return {node1, node2, edge};
, where node1, node2, and edge are references to the nodes and the edge. Additionally, do not use std::make_tuple, as that
will always copy values instead of returning references.
In this way, your iterator will iterator through a graph like the one below producing the following tuple values when deferenced
each time:
gdwg::Graph<int, int>
3.5.2. Iterator order
Note that output is sorted by 1) Src node (increasing order); then 2) Dst node (increasing order); then 3) Edge weight
(increasing order)
(1, 5, -1)
(2, 1, 1)
(2, 4, 2)
(3, 2, 2)
(3, 6, -8)
(4, 1, -4)
(4, 5, 3)
(5, 2, 7)
(6, 2, 5)
(6, 3, 10)
3.6. Internal Representation
Your Graph is required to own the resources (nodes and edges) that are passed in through the insert functions. This means
creating memory on the heap and doing a proper copy of the values from the caller. This is because resources in your graph
should outlive the caller’s resouce that was passed in in case it goes out of scope. For example, we want the following code to
be valid.
2019/10/2 COMP6771 – Advanced C++ Programming – 19T2
https://cgi.cse.unsw.edu.au/~cs6771/19T2/assignments/dg/index.html 9/12
int main() {
gdwg::Graph<std::string, int< g;
{
std::string s1{“Hello”};
g.InsertNode(s1);
}
// Even though s1 has gone out of scope, g has its own
// copied resource that it has stored, so the node
// will still be in here.
std::cout << g.IsNode(“Hello”) << “\n”; // prints ‘true’;
}
Your Graph is required to use smart pointers (however you please) to solve this problem.
For each edge, you are only allowed to have one underlying resource (heap) stored in your graph for it.
For each node, you are only allowed to have one underlying resource (heap) stored in your graph for it.
Hint: In your own implementation you’re likely to use some STL containers to store things, and somewhere in those containers
you’ll use instances of either:
std::unique_ptr
std::shared_ptr
depending on your implementation choice.
But why smart pointers
You could feasibly implement the assignment without any smart pointers, through lots of redundant copying. For example,
having a massive data structure like:
std::map<N, std::vector<std::pair<N, E>>>
You can see that in this structure you would have duplicates of nodes when trying to represent this complex structure. This
takes up a lot of space. We want you to build a space efficient graph. This means only storing one instance of each node and
edge.
3.7. Throwing Exceptions
You are required to throw exceptions in certain cases. These are specified in the tables above.
3.8. Other notes
You must:
Include a header guard in graph.h
Use C++17 style and methods
Leave a moved-from object in a state with 0 nodes
Mark all appropriate functions noexcept
You must not:
Write to any files that aren’t provided in the repo (e.g. storing your graph data in an auxilliary file)
3.9. Const Correctness
You must ensure that each method (2.3) and friend (2.4) appropriately either has:
A const member function; or
A non-const member function; or
Both a const and non-const member function
Please think carefully about this. The function prototypes intentionally do not specify their constness. This has an explicit const
and non-const prototype to help you out.
In most cases you will only need a single function, but in a couple of cases you will need both a const and non-const version.
4. Getting Started
If you haven’t done so already, clone the repository:
$ git clone https://github.com/cs6771/comp6771 comp6771
Then navigate to the assignments/dg directory
All of the files you need are in this directory. Here is a list of files that and a description of their purpose:
File Description
client.
(cpp|out)
A simple use case of a client using your graph
Note: Do NOT modify this file. We will potentially update it. If you want to modify it, make a local
copy first.
graph.(tpp|h) Your GDWG interface and implementation.
2019/10/2 COMP6771 – Advanced C++ Programming – 19T2
https://cgi.cse.unsw.edu.au/~cs6771/19T2/assignments/dg/index.html 10/12
graph_test.cpp Your tests for your GDWG file
BUILD Build file containing build, test, dependency instructions
4.2. Reference Solution & Time Limits
Due to the simple nature of this data type, there will be performance based measurements
Each test will still have a time limit to run (1 second max), but unless you do something completely insane this will be more
than enough time for all of your operations to complete.
4.3. Running your assignment
4.3.1. Running a basic use case
You can run your code against a basic (non-testing) use case to get a better sense of the behaviour
From your project directory:
$ bazel build //assignments/dg:client
$ ./bazel-bin/assignments/dg/client | diff ./assignments/dg/client.sampleout –
4.3.2. Running your tests
$ bazel build //assignments/dg:graph_test
$ bazel run //assignments/dg:graph_test
4.4. Autotests
You can run some basic tests on your code on any CSE machine. In a folder that contains your files, simply run the following
command:
6771 dgtest
Note: graph.tpp and graph.h must be in that directory.
Note: This test will not be available until the at the earliest the final 7 days before submission
4.5. Assessment
This assignment will contribute 20% to your final mark.
The assessment for the assignment recognizes the difficulty of the task, the importance of style, and the importance of
appropriate use of programming methods (e.g. using while loops instead of a dozen if statements).
60% Correctness
The correctness of your program will be determined automatically by tests that we will run against your program. We
will create a series of test files that contain their own main function and are compiled with your GDWG file(s).
20% Your tests
You are required to write your own tests to ensure your program works. You will write tests in graph_test.cpp . At
the top of this file you will also include a block comment to explain the rational and approach you took to writing
tests. Please read the Catch2 tutorial (https://github.com/catchorg/Catch2/blob/master/docs/tutorial.md) or review
lecture/tutorial content to see how to write tests. Tests will be marked on several factors. These include, but are not
limited to
Correctness – an incorrect test is worse than useless.
Coverage – your tests might be great, but if they don’t cover the part that ends up failing, they weren’t much
good to you.
Brittleness – If you change your implementation, will the tests need to be changed (this generally means
avoiding calling functions specific to your implementation where possible – ones that would be private if you
were doing OOP).
Clarity – If your test case failed, it should be immediately obvious what went wrong (this means splitting it up
into appropriately sized sub-tests, amongst other things).
15% C++ style
Your adherence to good C++ style. This is not saying that if you conform to the style guide you will receive full
marks for this section. This 20% is also based on how well you use modern C++ methodologies taught in this course
as opposed to using backwards-compatible C methods. Examples include: Not using primitive arrays and not using
pointers.
2019/10/2 COMP6771 – Advanced C++ Programming – 19T2
https://cgi.cse.unsw.edu.au/~cs6771/19T2/assignments/dg/index.html 11/12
5% cpplint and clang-format
In your project folder, run the following commands on all C++ files you submit:
$ clang-format -i /path/to/file && python cpplint.py /path/to/file
If the program outputs the following, you will receive full marks for this section (5%). Otherwise you will receive no marks.
Done processing assignments/dg/graph.h
Total errors found: 0
The following actions will result in a 0/100 mark for gdwg::Graph<N, E>, and in some cases a 0 for COMP6771:
Knowingly providing your work to anyone and it is subsequently submitted (by anyone).
Submitting any other person’s work. This includes joint work.
Submitting another person’s work without their consent.
The lecturer may vary the assessment scheme after inspecting the assignment submissions but it will remain broadly similar to
the description above.
4.6. Originality of Work
The work you submit must be your own work. Submission of work partially or completely derived from any other person (other
than your partner) or jointly written with any other person is not permitted. The penalties for such an offence may include
negative marks, automatic failure of the course and possibly other academic discipline. Assignment submissions will be
examined both automatically and manually for such submissions.
Relevant scholarship authorities will be informed if students holding scholarships are involved in an incident of plagiarism or
other misconduct.
Do not provide or show your assignment work to any other person — apart from the teaching staff of COMP6771. If you
knowingly provide or show your assignment work to another person for any reason, and work derived from it is submitted, you
may be penalized, even if the work was submitted without your knowledge or consent. This may apply even if your work is
submitted by a third party unknown to you.
Note you will not be penalized if your work has the potential to be taken without your consent or knowledge.
4.7. Group Work
For this assignment, you can choose to work in a group (of 2) or work by yourself. We STRONGLY recommend you work in a
group of 2. Working by yourself is not grounds for special consideration, or compensation of marks. Working in a team will
provide you someone you can share and discuss code with and develop your teamwork skills with.
If working in a group (RECOMMENDED)
You are required to use a private git repository (e.g. github) to store your assignment code. This repository must be kept
after the assignment is due and will be used to resolve any disputes regarding relative contributions between team members.
If you are pair programming (i.e. working off one computer), just write “Pair programming” in the commit message. However,
if you pair program and commit with a single username, we will have trouble resolving any disputes.
Groups will be finalised on Friday 19th July at 11:59pm
You must register your group here (https://docs.google.com/forms/d/e/1FAIpQLSe554 NdOWlXghFDNCw0YVqPF2g/viewform) before that deadline
You must register your group here (https://docs.google.com/forms/d/e/1FAIpQLSe554 NdOWlXghFDNCw0YVqPF2g/viewform) before that deadline
You must register your group here (https://docs.google.com/forms/d/e/1FAIpQLSe554 NdOWlXghFDNCw0YVqPF2g/viewform) before that deadline
If working individually (NOT RECOMMENDED)
You are strongly recommended, but not required to use a repository to store your code. If you do use a repository to store
your code, it must be a private repository
4.8. Submission
This assignment is due Tuesday 6th of August, 23:59:59. Submit the assignment using this give command:
give cs6771 graph graph.h graph.tpp graph_test.cpp
2019/10/2 COMP6771 – Advanced C++ Programming – 19T2
https://cgi.cse.unsw.edu.au/~cs6771/19T2/assignments/dg/index.html 12/12
4.9. Late Submission Policy
If your assignment is submitted after this date, each hour it is late reduces the maximum mark it can achieve by 1%. For
example if an assignment worth 76% was submitted 5 hours late, the late submission would have no effect (as maximum
mark would be 95%). If the same assignment was submitted 30 hours late it would be awarded 70%, the maximum mark it
can achieve at that time.
