Contents

Homework Assignment 1: Graph Traversal Iterators

Prepared files: pv264_hw1.zip
Deadline: 8th November 2020 23:59

Updates

2020-10-25: You must keep graph::value_type as is.

Introduction

Iterators of a data structure provide us with a way to go through elements of said structure, often in a well-defined order, allowing us to read or even modify them. Iterators of standard containers are quite simple, as most of the containers have a linear structure to traverse.

Graphs are not the case; several interesting ways to traverse them emerge. Recall two basic graph traversal algorithms: depth-first search (DFS) and breadth-first search (BFS).

Your task is to implement a directed graph and a set of iterators over it. The order in which the graph’s vertices are iterated over corresponds to the well-known algorithms BFS and DFS. For DFS, implement both pre-order and post-order variants.

Graph Type

The graph structure is parametrised by type of values assigned to each vertex. Do not assume anything about the type parameter except that it is movable.

template< typename V >
struct graph {
    using value_type = V;
    using node_handle = /** up to you **/;
    ...
};

The internal graph representation is entirely up to you, but keep the value_type declaration unchanged. Our tests will build graphs using a very simple interface:

node_handle add_node( V );
void add_edge( node_handle from, node_handle to );

Devise a suitable graph::node_handle type. Its values must be cheap to copy and must remain valid after the graph has been moved. Please note that the assignment does not enforce that the vertex values be unique, nor that there is at most one edge between vertices.

Iterators

There are three distinct kinds of iterators, which differ in the order in which they iterate through vertices:

BFS order: the order in which the vertices are processed (popped from the queue) during BFS.
DFS preorder: the order in which the vertices are discovered during DFS.
DFS postorder: the order in which the vertices are closed (backtracked from) during DFS.

Moreover, all three iterators come in two flavours:

sourced search, which starts in a specified vertex and iterates through all the vertices reachable from that vertex
global search, which traverses the entire graph by starting the search in every theretofore undiscovered vertex.

Of course, there is a constant and a mutable variant of each of these six iterators. Implementing these 12 iterators without code duplication is a large part of this assignment. There are 18 couples of begin/end functions (because constant iterators can be implicit or explicit); their prototypes are already declared in the skeleton.

The iterators must compute the graph traversal on-the-fly – pre-computing the right order is not a viable solution. Take extra care to implement the searches efficiently (in terms of both time and space complexity) and correctly (so that your DFS is indeed a DFS).

Edges from each vertex shall be explored in the order in which they were defined using a call to add_edge. Similarly, the global iterators shall start the search in all the vertices in the order of their respective add_node calls. Note that during the global search no vertex is visited twice (i.e., the set of visited vertices is shared across the searches). Call of add_edge or add_node invalidates all associated iterators.

When designing the iterators, refer to the “legacy iterator requirements” on https://en.cppreference.com/w/cpp/iterator. The iterators must satisfy InputIterator (the ones returned by the non-const member functions also OutputIterator) with the following restrictions (taken from ForwardIterator):

incrementing an iterator doesn’t affect its copies nor what gets read from (or modified through) them.
assignment through a mutable iterator doesn’t invalidate it or its copies.
a == b implies ++a == ++b. (Not really interesting.)

In contrast to ForwardIterator, the == relation doesn’t have to distinguish between all the pointed-to vertices. It only has to detect the end of the traversal and be an equality relation. However, feel free to implement a full-blown ForwardIterator; it should emerge naturally.

Don’t forget to make sure that std::iterator_traits of your iterators contain the correct types.

When implementing the iterators, do not duplicate code (i.e. there should be only one implementation of BFS and DFS (try to share code even between the pre-order and post-order variants) and only one implementation of the sourced and the global strategy). The constant and mutable variants should share basically all the code. Try to make everything about the iterator flavours compile-time: virtual functions are forbidden altogether and you should avoid using various (run-time) flags as well.

Notes

Templates are your friends. A few facts that some of the approaches use:

A class may inherit from its own template parameter. Calling the parent’s member functions then requires an explicit this->.
When you call a member function of a templated object, the existence of the member function is checked during instantiation – no need to know the exact interface beforehand.
You may call static member functions of template parameters as T::foo().
Not only a type, but also an integral constant (such as a number or an enum member) may be a template parameter.
You can template a using declaration to partially specialise a template under a new name.
You can use using Base::Base; inside a class derived from Base to re-export all constructors of the parent class as the derived one’s own.

For comparison, both reference solutions have under 250 lines.