Directed Graphs

Overview

Your task is to implement a directed graph class, offering a reasonably effective suite of operations, including computing spanning trees, depth and breadth first traversals, and implementing iterators.

The Code

You are provided with a
directed_graph.hpp
file, which includes all the basic definitions you will need (and it can be done with just those - I made sure). You made add extra methods, classes, structs etc., as long as they don't interfere with the operation of the tests. You may not include any further classes from the standard library in any of your marked code. You have also been provided with a
main.cpp
for ad-hoc testing purposes.
main.cpp
file does not form part of the assignment, and will not be marked. You can do anything you like with it. When the "run" button is pressed, it will compile and run
main.cpp. When the "mark" button is pressed, your code will be run against the tests. Note that as this is C++, if your code causes a program crash (e.g. a segfault), the testing code cannot recover, and will fail to mark your work - if you get this, make sure you fix that problem first!

You have also been given a copy of
test.h, which is the set of tests that the code will be run against. Note that this code has had certain elements removed (things that would just give part of the solution), so it's not runnable in its current state, but it may help you understand where you program is failing, and to design your own tests to be run with
main.cpp.

Remember to read over all the code before starting.

You have terminal access if you so desire it.

Directed Graphs

As the abstract data structure, and the possibilities for implementing it, have been covered in the lectures, I won't repeat them here. Please refer to the lecture material for the technical details in this regard. However, don't hesitate to ask questions etc. - you're welcome to inquire, I just don't want to clutter this space up!

The
directed_graph
Class

directed_graph
is probably the most complicated C++ class you will have had to implement, but it bears a great resemblance to many of the things we've already done, so just break it down into smaller, more manageable tasks. The code itself is commented to indicate the purpose of each method. Again, to avoid clutter, I won't repeat it all here, but do not hesitate to ask if anything is unclear (there's a forum specifically for the assignment).