COMP6771

General Directed Weighted Graph

2 The Task

In this assignment, you will write a generic directed weighted graph (GDWG) with value-semantics in C++. Both the data stored at a node and the weight stored at an edge will be parameterised types. The types may be different. For example, here is a graph with nodes storing std::string and edges weighted by int :

using graph = gdwg::graph;

Formally, this directed weighted graph G = (N, E) will consist of a set of nodes N and a set of unweighted/weighted edges E.

Explicit assumption for N and E: copyable, comparable (i.e. you can do ==, < etc.), streamable (i.e. you can use operator<< ) and hashable.

All nodes are unique, that is to say, no two nodes will have the same value and shall not compare equal using perator== .

Given 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.

A graph can include both weighted and unweighted edges. This applies to this assignment as well, therefore, you need to differentiate between weighted and unweighted edges in your implementation.

You need to make use of dynamic polymorphism to implement a base edge class, from which unweighted_edge and weighted_edge classes will inherit. The edge class will represent a directed edge from a source node src to a destination node dst . The derived classes will specialise the behaviour of the edge based on whether it is weighted or unweighted.

To summarise, you will need to implement the following classes along with gdwg::graph :

edge: An abstract base class representing an edge in the graph, which can be either weighted or unweighted. It declares pure virtual functions that must be implemented by its derived classes.

weighted_edge: A derived class of edge that represents an edge with an associated weight.

unweighted_edge: A derived class of edge that represents an edge without an associated weight.

Note that edges can be reflexive, meaning the source and destination nodes of an edge could be the same.

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, two edges from the same source node to the same destination node cannot have the same weight.

Some words have special meaning in this document. This section precisely defines those words.

Preconditions: the conditions that the function assumes to hold whenever it is called; violation of any preconditions results in undefined behaviours.

Effects: the actions performed by the function.

Postconditions: the conditions (sometimes termed observable results) established by the function.

Returns: a description of the value(s) returned by the function.

Throws: any exceptions thrown by the function, and the conditions that would cause the exception.

Complexity: the time and/or space complexity of the function.

Remarks: additional semantic constraints on the function.

Unspecified: the implementation is allowed to make its own decisions regarding what is unspecified, provided that it still follows the explicitly specified wording.

An Effects element may specify semantics for a function F in code using the term Equivalent to. The semantics for F are interpreted as follows:

All of the above terminology applies to the provided code, whether or not it is explicitly specified.

[Example: If F has a Preconditions element, but the code block doesnʼt explicitly check them, then it is implied that the preconditions have been checked. —end example]

If there is not a Returns element, and F has a non- void return type, all the return statements are in the code block.

Throws, Postconditions, and Complexity elements always have priority over the code block.

Specified complexity requirements are upper bounds, and implementations that provide better complexity guarantees meet the requirements.

The class synopsis is the minimum text your header requires to compile most tests (this doesnʼt mean that it will necessarily link or run as expected).

Blue text in code will link to C++ Reference or to another part of this document.

This section makes use of [stable.names]. A stable name is a short name for a (sub)section, and isnʼt supposed to change. We will use these to reference specific sections of the document.

[Example:

Student: Do we need to define gdwg::graph::operator!= ?

Tutor: [other.notes] mentions that you donʼt need to so you can get used to C++20ʼs generated operators.

—end example]

2.2 Constructors

Itʼs very important your constructors work. If we canʼt validly construct your objects, we canʼt test any of your other functions.

graph();

1. Effects: Value initialises all members.

2. Throws: Nothing.

graph(std::initializer_list il);

3. Effects: Equivalent to: graph(il.begin(), il.end());

template

graph(InputIt first, InputIt last);

4. Preconditions: Type InputIt models Cpp17 Input Iterator and is indirectly readable as type N .

5. Effects: Initialises the graphʼs node collection with the range [first, last) .

graph(graph&& other) noexcept;

6. Postconditions: *this is equal to the value other had before this constructorʼs invocation. other.empty() is true . All iterators pointing to elements owned by *this prior to this constructorʼs invocation are invalidated. All iterators pointing to elements owned by other prior to this constructorʼs invocation remain valid, but now point to the elements owned by *this .

auto perator=(graph&& other) noexcept -> graph&;

7. Effects: All existing nodes and edges are either move-assigned to, or are destroyed.

8. Postconditions:

*this is equal to the value other had before this operatorʼs invocation.

other.empty() is true .

All iterators pointing to elements owned by *this prior to this operatorʼs invocation are invalidated.

All iterators pointing to elements owned by other prior to this operatorʼs invocation remain valid, but now point to the elements owned by *this .

9. Returns: *this .

graph(graph const& other);

10. Postconditions: *this == other is true .

auto perator=(graph const& other) -> graph&;

11. Postconditions:

*this == other is true .

All iterators pointing to elements owned by *this prior to this operatorʼs invocation are invalidated.

Returns: *this .

2.3 Edge Class Hierachy

The edge class is an abstract BASE class that declares PURE virtual functions which must be implemented by its derived classes.

You will note that ONLY the member functions listed below can be specified as public , you are free to create other private virtual functions to help with the implementation of the derived classes and the features required for gdwg::graph .

NOTE: We didn't specify the keywords for functions such as const , virtual , override , or noexcept , this is intentional. You should use them where appropriate.

auto print_edge() -> std::string;

1. Effects: Returns a string representation of the edge.

2. Returns: A string representation of the edge.

3. Remarks: The format of the string representation is src -> dst | W | weight if the edge is weighted, and src -> dst | U if the edge is unweighted.

Note: print_edge will be used in the operator<< overload for the graph class.

auto is_weighted() -> bool;

4. Effects: identify whether the edge is weighted.

5. Returns: true if the edge is weighted, and false otherwise.

auto get_weight() -> std::optional;

7. Effects: Returns the weight of the edge, std::nullopt if the edge is unweighted.

8. Returns: The weight of the edge.

auto get_nodes() -> std::pair;

9. Effects: Returns the source and destination nodes of the edge.

10. Returns: A pair of the source and destination nodes of the edge.

As a polymorphic base class, edge should also have a public virtual destructor.

2.3.2 weighted_edge

The weighted_edge class inherits from edge and represents a weighted edge in the graph.

It MUST implement the edge classʼs pure virtual functions to provide appropriate funtionality for weighted edges.

Additionally, the weighted_edge class should have a constructor that takes the src , dst node, and weight as parameters and initialises the corresponding private member variables.

2.3.3 unweighted_edge

The unweighted_edge class inherits from edge and represents an unweighted edge in the graph.

It MUST implement the edge classʼs pure virtual functions to provide appropriate functionality for unweighted edges.

Similar to the weighted_edge class, the unweighted_edge class should have a constructor that takes the src node and dst node as parameters and initialises the corresponding private member variables.