initial commit

7 files changed, 1643 insertions, 0 deletions

diff --git a/comp6771/3/.clang-format b/comp6771/3/.clang-format
new file mode 100644
index 0000000..d1555d3
--- /dev/null
+++ b/comp6771/3/.clang-format
@@ -0,0 +1,103 @@
+Language: Cpp
+Standard: Cpp11
+AccessModifierOffset: -3
+AlignAfterOpenBracket: Align
+AlignConsecutiveAssignments: false
+AlignConsecutiveDeclarations: false
+AlignConsecutiveMacros: false
+AlignEscapedNewlines: Right
+AlignOperands: true
+AlignTrailingComments: false
+AllowAllArgumentsOnNextLine: false
+AllowAllConstructorInitializersOnNextLine: false
+AllowAllParametersOfDeclarationOnNextLine: false
+AllowShortBlocksOnASingleLine: false
+AllowShortCaseLabelsOnASingleLine: true
+AllowShortFunctionsOnASingleLine: Empty
+AllowShortIfStatementsOnASingleLine: false
+AllowShortLambdasOnASingleLine: All
+AllowShortLoopsOnASingleLine: false
+AlwaysBreakAfterReturnType: None
+AlwaysBreakBeforeMultilineStrings: false
+AlwaysBreakTemplateDeclarations: Yes
+BinPackArguments: false
+BinPackParameters: false
+BreakBeforeBinaryOperators: NonAssignment
+BreakBeforeBraces: Custom
+BraceWrapping:
+  AfterCaseLabel: false
+  AfterClass: false
+  AfterControlStatement: MultiLine
+  AfterEnum: false
+  AfterFunction: false
+  AfterNamespace: false
+  AfterStruct: false
+  AfterUnion: false
+  AfterExternBlock: false
+  BeforeCatch: false
+  BeforeElse: true
+  BeforeLambdaBody: false
+  IndentBraces: false
+  SplitEmptyFunction: false
+  SplitEmptyRecord: false
+  SplitEmptyNamespace: false
+BreakBeforeTernaryOperators: true
+BreakConstructorInitializers: BeforeComma
+BreakInheritanceList: BeforeComma
+BreakStringLiterals: true
+ColumnLimit: 120
+CompactNamespaces: true
+ConstructorInitializerAllOnOneLineOrOnePerLine: false
+ConstructorInitializerIndentWidth: 0
+ContinuationIndentWidth: 4
+Cpp11BracedListStyle: true
+FixNamespaceComments: true
+IncludeBlocks: Preserve
+IncludeCategories:
+  - Regex: "^<[[:alnum:].]+>"
+    Priority: 2
+  - Regex: '^"[[:alnum:].]"'
+    Priority: 1
+IndentCaseBlocks: false
+IndentCaseLabels: false
+IndentGotoLabels: false
+IndentPPDirectives: AfterHash
+IndentWidth: 4
+IndentWrappedFunctionNames: false
+KeepEmptyLinesAtTheStartOfBlocks: false
+MaxEmptyLinesToKeep: 1
+NamespaceIndentation: All
+PenaltyBreakAssignment: 10
+PenaltyBreakBeforeFirstCallParameter: 10
+PenaltyBreakComment: 10
+PenaltyBreakFirstLessLess: 10
+PenaltyBreakString: 10
+PenaltyBreakTemplateDeclaration: 10
+PenaltyExcessCharacter: 10
+PenaltyReturnTypeOnItsOwnLine: 10
+PointerAlignment: Left
+ReflowComments: true
+SortIncludes: true
+SortUsingDeclarations: true
+SpaceAfterCStyleCast: false
+SpaceAfterLogicalNot: false
+SpaceAfterTemplateKeyword: false
+SpaceBeforeAssignmentOperators: true
+SpaceBeforeCpp11BracedList: false
+SpaceBeforeCtorInitializerColon: true
+SpaceBeforeInheritanceColon: true
+SpaceBeforeParens: ControlStatements
+SpaceBeforeRangeBasedForLoopColon: true
+SpaceBeforeSquareBrackets: false
+SpaceInEmptyBlock: false
+SpaceInEmptyParentheses: false
+SpacesBeforeTrailingComments: 1
+SpacesInAngles: false
+SpacesInCStyleCastParentheses: false
+SpacesInConditionalStatement: false
+SpacesInContainerLiterals: false
+SpacesInParentheses: false
+SpacesInSquareBrackets: false
+TabWidth: 4
+UseCRLF: false
+UseTab: ForIndentation
\ No newline at end of file
diff --git a/comp6771/3/.gitignore b/comp6771/3/.gitignore
new file mode 100644
index 0000000..36d0cdf
--- /dev/null
+++ b/comp6771/3/.gitignore
@@ -0,0 +1,17 @@
+build/
+build_release/
+Testing/
+.cache/
+.clangd/
+.vs/
+.DS_Store
+CMakeFiles
+CMakeCache.txt
+CTestTestfile.cmake
+Makefile
+client
+cmake_install.cmake
+compile_commands.json
+gdwg_graph_test_exe
+libcatch2_main.a
+libgdwg_graph.a
diff --git a/comp6771/3/CMakeLists.txt b/comp6771/3/CMakeLists.txt
new file mode 100644
index 0000000..ed94073
--- /dev/null
+++ b/comp6771/3/CMakeLists.txt
@@ -0,0 +1,72 @@
+# ------------------------------------------------------------ #
+# -------------- DO NOT TOUCH BELOW THIS LINE ---------------- #
+# ------------------------------------------------------------ #
+
+# Make sure checks are configured
+execute_process(COMMAND bash util/setup.sh)
+
+# this must be the first line of a CMake script.
+# sets the lowerbound on what CMake version can be used.
+cmake_minimum_required(VERSION 3.0...3.5)
+
+# the name of this CMake project and what language it uses
+# we could list more languages if we were using more.
+project(COMP6771_LAB_001 LANGUAGES CXX)
+
+# we use C++20
+set(CMAKE_CXX_STANDARD 20)
+set(CMAKE_CXX_STANDARD_REQUIRED YES)
+set(CMAKE_CXX_EXTENSIONS NO)
+
+# this is helpful for editors like VS Code
+set(CMAKE_EXPORT_COMPILE_COMMANDS ON)
+
+# helpful compiler flags for gcc/clang
+# the descriptions for these flags can be found on the GNU Compiler Collection's webpage.
+add_compile_options(
+  -Wall
+  -Wextra
+  -Werror
+  -pedantic-errors
+  -Wconversion
+  -Wsign-conversion
+  -Wdouble-promotion
+  -Wcast-align
+  -Wformat=2
+  -Wuninitialized
+  -Wnull-dereference
+  -Wnon-virtual-dtor
+  -Woverloaded-virtual
+  -Wdeprecated-copy-dtor
+  -Wold-style-cast
+  -Wzero-as-null-pointer-constant
+  -Wsuggest-override
+  -fstack-protector-strong
+)
+
+# debug builds should be compiled with sanitizers
+# sanitizers are small libraries that check things like buffer overrun with minimal runtime overhead.
+set(CMAKE_CXX_FLAGS_DEBUG_INIT "-fsanitize=address,undefined")
+set(CMAKE_CXX_FLAGS_RELWITHDEBINFO_INIT "-fsanitize=address,undefined")
+set(CMAKE_CXX_EXE_LINKER_FLAGS_DEBUG_INIT "-fsanitize=address,undefined")
+set(CMAKE_CXX_EXE_LINKER_FLAGS_RELWITHDEBINFO_INIT "-fsanitize=address,undefined")
+
+
+# add the testing library Catch2
+enable_testing()
+add_library(catch2_main lib/catch2_main.cpp)
+target_include_directories(catch2_main PUBLIC lib)
+# link the library so that other programs can get it
+link_libraries(catch2_main)
+
+# ------------------------------------------------------------ #
+# -------------- DO NOT MODIFY ABOVE THIS LINE --------------- #
+# ------------------------------------------------------------ #
+
+add_library(gdwg_graph src/gdwg_graph.h src/gdwg_graph.cpp)
+link_libraries(gdwg_graph)
+
+add_executable(client src/client.cpp)
+add_executable(gdwg_graph_test_exe src/gdwg_graph.test.cpp)
+add_test(gdwg_graph_test gdwg_graph_test_exe)
+
diff --git a/comp6771/3/src/client.cpp b/comp6771/3/src/client.cpp
new file mode 100644
index 0000000..ca3c30e
--- /dev/null
+++ b/comp6771/3/src/client.cpp
@@ -0,0 +1,75 @@
+#include "gdwg_graph.h"
+
+#include <iostream>
+#include <string>
+
+auto main() -> int {
+	/*
+	auto g = gdwg::graph<std::string, int>{};
+	g.insert_node("hello");
+	g.insert_node("how");
+	g.insert_node("are");
+	g.insert_node("you?");
+
+	g.insert_edge("hello", "how", 5);
+	g.insert_edge("hello", "are", 8);
+	g.insert_edge("hello", "are", 2);
+
+	g.insert_edge("how", "you?", 1);
+	g.insert_edge("how", "hello", 4);
+
+	g.insert_edge("are", "you?", 3);
+
+	std::cout << g << "\n";
+
+	auto g2 = gdwg::graph<std::string, int>(g);
+
+	std::cout << g2 << "\n";
+
+	// This is a structured binding.
+	// https://en.cppreference.com/w/cpp/language/structured_binding
+	// It allows you to unpack your tuple.
+	for (const auto& [from, to, weight] : g) {
+	    std::cout << from << " -> " << to << " ";
+	    if (weight.has_value()) {
+	        std::cout << "(weight " << *weight << ")\n";
+	    }
+	    else {
+	        std::cout << "(no weight)\n";
+	    }
+	}
+	*/
+
+	using graph = gdwg::graph<int, int>;
+	auto const v = std::vector<std::tuple<int, int, std::optional<int>>>{
+	    {4, 1, -4},
+	    {3, 2, 2},
+	    {2, 4, std::nullopt},
+	    {2, 4, 2},
+	    {2, 1, 1},
+	    {4, 1, std::nullopt},
+	    {6, 2, 5},
+	    {6, 3, 10},
+	    {1, 5, -1},
+	    {3, 6, -8},
+	    {4, 5, 3},
+	    {5, 2, std::nullopt},
+	};
+
+	auto g = graph{};
+	for (const auto& [from, to, weight] : v) {
+		g.insert_node(from);
+		g.insert_node(to);
+		if (weight.has_value()) {
+			g.insert_edge(from, to, weight.value());
+		}
+		else {
+			g.insert_edge(from, to);
+		}
+	}
+	g.insert_node(64);
+
+	auto out = std::ostringstream{};
+	out << g;
+	std::cout << g << '\n';
+}
diff --git a/comp6771/3/src/gdwg_graph.cpp b/comp6771/3/src/gdwg_graph.cpp
new file mode 100644
index 0000000..9326b3c
--- /dev/null
+++ b/comp6771/3/src/gdwg_graph.cpp
@@ -0,0 +1,5 @@
+#include "gdwg_graph.h"
+
+namespace gdwg {
+
+} // namespace gdwg
diff --git a/comp6771/3/src/gdwg_graph.h b/comp6771/3/src/gdwg_graph.h
new file mode 100644
index 0000000..7443f46
--- /dev/null
+++ b/comp6771/3/src/gdwg_graph.h
@@ -0,0 +1,499 @@
+#ifndef GDWG_GRAPH_H
+#define GDWG_GRAPH_H
+
+#include <initializer_list>
+#include <algorithm>
+#include <exception>
+#include <iterator>
+#include <memory>
+#include <numeric>
+#include <optional>
+#include <set>
+#include <sstream>
+#include <string>
+#include <vector>
+
+namespace gdwg {
+	template<typename N, typename E>
+	class edge {
+	 protected:
+		N src;
+		N dst;
+
+	 public:
+		edge(const N& s, const N& d)
+		: src(s)
+		, dst(d) {}
+		virtual ~edge() = default;
+
+		virtual auto print_edge() const -> std::string = 0;
+		virtual auto is_weighted() const noexcept -> bool = 0;
+		virtual auto get_weight() const -> std::optional<E> = 0;
+
+		auto get_nodes() const -> std::pair<N, N> {
+			return std::pair<N, N>{this->src, this->dst};
+		}
+
+		auto operator==(const edge& other) const noexcept -> bool {
+			if (this->src != other.src) {
+				return false;
+			}
+			return this->dst == other.dst;
+		};
+	};
+
+	template<typename N, typename E>
+	class weighted_edge : virtual public edge<N, E> {
+	 protected:
+		E weight;
+
+	 public:
+		weighted_edge(const N& s, const N& d, const E& w)
+		: edge<N, E>(s, d)
+		, weight(w) {}
+		virtual ~weighted_edge() = default;
+
+		virtual auto print_edge() const -> std::string override {
+			std::stringstream ss{};
+			ss << this->src << " -> " << this->dst << " | W | " << this->weight;
+			return ss.str();
+		}
+		virtual auto is_weighted() const noexcept -> bool override {
+			return true;
+		}
+		virtual auto get_weight() const -> std::optional<E> override {
+			return this->weight;
+		}
+		auto operator==(const weighted_edge<N, E>& other) const noexcept -> bool {
+			if (edge<N, E>::operator!=(*this, other)) {
+				return false;
+			}
+			return this->weight == other.weight;
+		};
+	};
+
+	template<typename N, typename E>
+	class unweighted_edge : virtual public edge<N, E> {
+	 private:
+	 public:
+		unweighted_edge(const N& s, const N& d)
+		: edge<N, E>(s, d) {}
+		virtual ~unweighted_edge() = default;
+
+		virtual auto print_edge() const -> std::string override {
+			std::stringstream ss{};
+			ss << this->src << " -> " << this->dst << " | U";
+			return ss.str();
+		}
+		virtual auto is_weighted() const noexcept -> bool override {
+			return false;
+		}
+		virtual auto get_weight() const -> std::optional<E> override {
+			return std::nullopt;
+		}
+	};
+
+	template<typename N, typename E>
+	class graph {
+	 private:
+		// We are not allowed to store redundant copies of nodes, so we use
+		// an unordered_set of N to avoid unnecessary copies. As the edge class
+		// copies the strings internally we cannot use them for our internal
+		// edge representation.
+		// We define two custom hashing functions here to force our shared_ptrs
+		// to use their internally stored strings for comparison
+		// such that we can avoid creating a map which inevitably stores a
+		// redundant copy of the string as the key.
+		struct shared_edge {
+			std::shared_ptr<N> from;
+			std::shared_ptr<N> to;
+			std::optional<E> weight;
+
+			// Required for multiset comparison.
+			auto operator==(const shared_edge& other) const noexcept -> bool {
+				if (*this->from != *other.from) {
+					return false;
+				}
+				if (*this->to != *other.to) {
+					return false;
+				}
+				return this->weight == other.weight;
+			}
+		};
+
+		using nodes_comp =
+		    decltype([](const std::shared_ptr<N>& a, const std::shared_ptr<N>& b) noexcept -> bool { return *a < *b; });
+		using edges_comp = decltype([](const shared_edge& a, const shared_edge& b) -> bool {
+			if (*a.from != *b.from) {
+				return *a.from < *b.from;
+			}
+			if (a.to == nullptr) { // necessary for our std::lower_bound
+				return true;
+			}
+			if (b.to == nullptr) {
+				return false;
+			}
+			if (*a.to != *b.to) {
+				return *a.to < *b.to;
+			}
+			return a.weight < b.weight;
+		});
+
+	 public:
+		using nodes_t = std::set<std::shared_ptr<N>, nodes_comp>;
+		using edges_t = std::set<shared_edge, edges_comp>;
+
+	 private:
+		nodes_t node_ptrs{};
+		edges_t shared_edges{};
+
+	 private:
+		// Efficiently find iterators for some N.
+		auto get_edges_from_n(const N& n) const noexcept -> auto {
+			const auto lower = this->shared_edges.lower_bound(
+			    shared_edge{.from = std::make_shared<N>(n), .to = nullptr, .weight = std::nullopt});
+
+			auto upper = lower;
+			for (; upper != std::end(this->shared_edges); ++upper) {
+				if (*upper->from != n) {
+					break;
+				}
+			}
+			return std::make_pair(lower, upper);
+		}
+		// Transforms a shared_edge to a unique_ptr of the appropriate edge.
+		static auto make_edge(const shared_edge& e) -> std::unique_ptr<edge<N, E>> {
+			if (not e.weight.has_value()) {
+				return std::make_unique<unweighted_edge<N, E>>(*e.from, *e.to);
+			}
+			return std::make_unique<weighted_edge<N, E>>(*e.from, *e.to, *e.weight);
+		};
+
+	 public:
+		class iterator {
+			friend graph;
+
+		 public:
+			using value_type = struct {
+				N from;
+				N to;
+				std::optional<E> weight;
+			};
+			using reference = value_type;
+			using pointer = void;
+			using difference_type = std::ptrdiff_t;
+			using iterator_category = std::bidirectional_iterator_tag;
+
+		 private:
+			edges_t::iterator iter;
+			value_type contents;
+
+		 private:
+			static auto iter_to_value(const edges_t::iterator i) -> value_type {
+				return value_type{
+				    .from = *i->from,
+				    .to = *i->to,
+				    .weight = i->weight,
+				};
+			}
+
+		 public:
+			// Iterator constructor
+			iterator() noexcept = default;
+			explicit iterator(edges_t::iterator it) noexcept
+			: iter(it) {}
+
+			// Iterator source
+			auto operator*() -> reference {
+				this->contents = iter_to_value(this->iter);
+				return contents;
+			}
+
+			// Iterator traversal
+			auto operator++() -> iterator& {
+				++this->iter;
+				return *this;
+			}
+			auto operator++(int) -> iterator {
+				iterator ret = *this;
+				++(*this);
+				return ret;
+			}
+			auto operator--() -> iterator& {
+				--this->iter;
+				return *this;
+			}
+			auto operator--(int) -> iterator {
+				iterator ret = *this;
+				--(*this);
+				return ret;
+			}
+
+			// Iterator comparison
+			friend auto operator==(const iterator& a, const iterator& b) noexcept -> bool {
+				return a.iter == b.iter;
+			}
+		};
+		[[nodiscard]] auto begin() const -> iterator {
+			return iterator{std::begin(this->shared_edges)};
+		}
+		[[nodiscard]] auto end() const -> iterator {
+			return iterator{std::end(this->shared_edges)};
+		}
+
+	 public:
+		graph() noexcept {}
+		graph(std::initializer_list<N> il) noexcept
+		: graph(std::begin(il), std::end(il)) {}
+		template<typename InputIt>
+		graph(InputIt first, InputIt last) {
+			std::transform(first, last, std::inserter(this->node_ptrs, std::end(this->node_ptrs)), [](const auto& n) {
+				return std::make_shared<N>(n);
+			});
+		}
+		graph(graph&& other) noexcept
+		: node_ptrs(std::move(other.node_ptrs))
+		, shared_edges(std::move(other.shared_edges)) {
+			other.clear();
+		}
+		graph(const graph& other)
+		: node_ptrs(other.node_ptrs)
+		, shared_edges(other.shared_edges) {}
+
+		auto operator=(graph&& other) noexcept {
+			if (&other != this) {
+				this->node_ptrs = std::move(other.node_ptrs);
+				this->shared_edges = std::move(other.shared_edges);
+				other.clear();
+			}
+			return *this;
+		}
+		auto operator=(const graph& other) -> graph& {
+			if (&other != this) {
+				this->node_ptrs = other.node_ptrs;
+				this->shared_edges = other.shared_edges;
+			}
+			return *this;
+		}
+		friend auto operator==(const graph& a, const graph& b) noexcept -> bool {
+			if (not std::equal(std::begin(a.node_ptrs),
+			                   std::end(a.node_ptrs),
+			                   std::begin(b.node_ptrs),
+			                   std::end(b.node_ptrs),
+			                   [](const auto& a_v, const auto& b_v) { return *a_v == *b_v; }))
+			{
+				return false;
+			}
+			return a.shared_edges == b.shared_edges;
+		}
+		friend auto operator<<(std::ostream& os, const graph& g) -> std::ostream& {
+			os << '\n';
+			for (const auto& n : g.node_ptrs) {
+				os << *n << " (\n";
+
+				const auto& [lower, upper] = g.get_edges_from_n(*n);
+				std::for_each(lower, upper, [&](const auto& e) {
+					const auto print = make_edge(e);
+					os << "  " << print->print_edge() << '\n';
+				});
+
+				os << ")\n";
+			}
+			return os;
+		}
+
+		auto insert_node(const N& value) -> bool {
+			return this->node_ptrs.insert(std::make_shared<N>(value)).second;
+		}
+		auto insert_edge(const N& s, const N& d, std::optional<E> w = std::nullopt) -> bool {
+			const auto s_it = this->node_ptrs.find(std::make_shared<N>(s));
+			const auto d_it = this->node_ptrs.find(std::make_shared<N>(d));
+			if (s_it == std::end(this->node_ptrs) || d_it == std::end(this->node_ptrs)) {
+				throw std::runtime_error("Cannot call gdwg::graph<N, E>::insert_edge when either src or dst node "
+				                         "does "
+				                         "not exist");
+			}
+
+			const auto insert = shared_edge{.from = *s_it, .to = *d_it, .weight = w};
+			if (this->shared_edges.contains(insert)) {
+				return false;
+			}
+
+			this->shared_edges.insert(std::move(insert));
+			return true;
+		}
+		auto replace_node(const N& old_node, const N& new_node) -> bool {
+			const auto old_it = this->node_ptrs.find(std::make_shared<N>(old_node));
+			if (old_it == std::end(this->node_ptrs)) {
+				throw std::runtime_error("Cannot call gdwg::graph<N, E>::replace_node on a node that doesn't exist");
+			}
+
+			const auto insert = std::make_shared<N>(new_node);
+			if (this->node_ptrs.contains(insert)) {
+				return false;
+			}
+
+			this->node_ptrs.erase(old_it);
+			this->node_ptrs.insert(insert);
+			return true;
+		}
+		auto merge_replace_node(const N& old_node, const N& new_node) -> void {
+			const auto old_it = this->node_ptrs.find(std::make_shared<N>(old_node));
+			const auto new_it = this->node_ptrs.find(std::make_shared<N>(new_node));
+			if (old_it == std::end(this->node_ptrs) or new_it == std::end(this->node_ptrs)) {
+				throw std::runtime_error("Cannot call gdwg::graph<N, E>::merge_replace_node on old or new data if they "
+				                         "don't exist in the graph");
+			}
+
+			// This operation completely transforms all nodes and replaces all
+			// existences of old_node with new_node (using the existing shared_ptr).
+			auto result = edges_t{};
+			std::transform(std::begin(this->shared_edges),
+			               std::end(this->shared_edges),
+			               std::inserter(result, std::end(result)),
+			               [&](const auto& e) {
+				               return shared_edge{.from = (e.from == *old_it ? *new_it : e.from),
+				                                  .to = (e.to == *old_it ? *new_it : e.to),
+				                                  .weight = e.weight};
+			               });
+
+			this->shared_edges = std::move(result);
+			this->node_ptrs.erase(old_it);
+		}
+		auto erase_node(const N& n) -> bool {
+			const auto node_it = this->node_ptrs.find(std::make_shared<N>(n));
+			if (node_it == std::end(this->node_ptrs)) {
+				return false;
+			}
+
+			std::erase_if(this->shared_edges, [&](const auto& e) {
+				if (*e.from == **node_it) {
+					return true;
+				}
+				if (*e.to == **node_it) {
+					return true;
+				}
+				return false;
+			});
+			this->node_ptrs.erase(node_it);
+			return true;
+		}
+		auto erase_edge(const N& s, const N& d, std::optional<E> w = std::nullopt) -> bool {
+			const auto s_it = this->node_ptrs.find(std::make_shared<N>(s));
+			const auto d_it = this->node_ptrs.find(std::make_shared<N>(d));
+			if (s_it == std::end(this->node_ptrs) || d_it == std::end(this->node_ptrs)) {
+				throw std::runtime_error("Cannot call gdwg::graph<N, E>::erase_edge on src or dst if they don't exist "
+				                         "in the graph");
+			}
+
+			const auto& [lower, upper] = this->get_edges_from_n(s);
+			if (const auto it = std::find_if(lower,
+			                                 upper,
+			                                 [&](const auto& e) {
+				                                 if (*e.from != s) {
+					                                 return false;
+				                                 }
+				                                 if (*e.to != d) {
+					                                 return false;
+				                                 }
+				                                 return e.weight == w;
+			                                 });
+			    it != upper)
+			{
+				this->shared_edges.erase(it);
+				return true;
+			}
+
+			return false;
+		}
+		auto erase_edge(const iterator& i) -> iterator {
+			return iterator{this->shared_edges.erase(i.iter)};
+		}
+		auto erase_edge(const iterator& i, const iterator& s) -> iterator {
+			return iterator{this->shared_edges.erase(i.iter, s.iter)};
+		}
+
+		auto clear() noexcept -> void {
+			this->node_ptrs.clear();
+			this->shared_edges.clear();
+		}
+
+		[[nodiscard]] auto is_node(const N& value) const noexcept -> bool {
+			return this->node_ptrs.contains(std::make_shared<N>(value));
+		}
+		[[nodiscard]] auto empty() const noexcept -> bool {
+			return this->node_ptrs.empty();
+		}
+		[[nodiscard]] auto nodes() const -> std::vector<N> {
+			auto result = std::vector<N>{};
+			std::transform(std::begin(this->node_ptrs),
+			               std::end(this->node_ptrs),
+			               std::back_inserter(result),
+			               [](const auto& n) { return *n; });
+			return result;
+		}
+		[[nodiscard]] auto is_connected(const N& s, const N& d) const -> bool {
+			if (not this->is_node(s) or not this->is_node(d)) {
+				throw std::runtime_error("Cannot call gdwg::graph<N, E>::is_connected if src or dst node don't exist "
+				                         "in the graph");
+			}
+
+			const auto& [lower, upper] = this->get_edges_from_n(s);
+			return std::any_of(lower, upper, [&](const auto& e) { return *e.to == d; });
+		}
+
+		[[nodiscard]] auto edges(const N& s, const N& d) const -> std::vector<std::unique_ptr<edge<N, E>>> {
+			if (not this->is_node(s) or not this->is_node(d)) {
+				throw std::runtime_error("Cannot call gdwg::graph<N, E>::edges if src or dst node don't exist in the "
+				                         "graph");
+			}
+
+			const auto& [lower, upper] = this->get_edges_from_n(s);
+
+			auto result = std::vector<std::unique_ptr<edge<N, E>>>{};
+			std::for_each(lower, upper, [&](const auto& e) {
+				if (*e.to != d) {
+					return;
+				}
+				result.push_back(make_edge(e));
+			});
+			return result;
+		}
+		[[nodiscard]] auto find(const N& s, const N& d, std::optional<E> w = std::nullopt) const -> iterator {
+			const auto& [lower, upper] = this->get_edges_from_n(s);
+
+			if (const auto it = std::find_if(lower,
+			                                 upper,
+			                                 [&](const auto& e) {
+				                                 if (*e.to != d) {
+					                                 return false;
+				                                 }
+				                                 return e.weight == w;
+			                                 });
+			    it != upper)
+			{
+				return iterator{it};
+			}
+			return std::end(*this);
+		}
+		[[nodiscard]] auto connections(const N& s) const -> std::vector<N> {
+			if (not this->is_node(s)) {
+				throw std::runtime_error("Cannot call gdwg::graph<N, E>::connections if src doesn't exist in the "
+				                         "graph");
+			}
+
+			const auto& [lower, upper] = this->get_edges_from_n(s);
+
+			auto result = std::set<N>{};
+			std::transform(lower, upper, std::inserter(result, std::end(result)), [](const auto& e) {
+				const auto n = *e.to;
+				return n;
+			});
+
+			return std::vector<N>{std::begin(result), std::end(result)};
+		}
+	};
+
+} // namespace gdwg
+
+#endif // GDWG_GRAPH_H
diff --git a/comp6771/3/src/gdwg_graph.test.cpp b/comp6771/3/src/gdwg_graph.test.cpp
new file mode 100644
index 0000000..778fc9e
--- /dev/null
+++ b/comp6771/3/src/gdwg_graph.test.cpp
@@ -0,0 +1,872 @@
+#include "gdwg_graph.h"
+
+#include <catch2/catch.hpp>
+
+// Specification: 2.2 graph()
+// Purpose:  Ensure the default graph constructor functions as expected.
+// Expected: The default graph constructor does not throw and is_empty returns
+// 		  	 true.
+// Notes:    We cannot test inner data members due to added brittleness.
+TEST_CASE("graph constructor value initialises all members") {
+	const auto g = gdwg::graph<int, std::string>{};
+	CHECK(g.empty());
+}
+
+// Specification 2.2 graph(std::initializer_list<N> il)
+// Purpose:  Ensure the initializer list graph constructor functions correctly.
+// Expected: The initializer list graph constructor functions and correctly
+//			 initialises its data members as equal to the provided nodes.
+TEST_CASE("graph initializer list constructor constructs nodes") {
+	const auto list = std::initializer_list<int>{1, 2, 3};
+	const auto g = gdwg::graph<int, std::string>{list};
+	CHECK(not g.empty());
+	CHECK(g.nodes() == std::vector<int>{list});
+}
+
+// Specification 2.2 graph(InputIt first, InputIt last)
+// Purpose:  Ensure the range iterator constructor functions correctly.
+// Expected: The range iterator graph constructor functions and correctly
+//			 initialises its data members as equal to the provided nodes.
+TEST_CASE("graph iterator constructor constructs nodes") {
+	const auto list = std::initializer_list<int>{1, 2, 3};
+	const auto g = gdwg::graph<int, std::string>{std::begin(list), std::end(list)};
+	CHECK(not g.empty());
+	CHECK(g.nodes() == std::vector<int>{list});
+}
+
+// Specification 2.2 graph(graph&& other)
+// Purpose:  Ensure the graph move constructor functions as expected.
+// Expected: The graph move constructor should default construct the
+// 			 moved-from class after the move operation and prior iterators
+//			 from the moved-from class should remain valid.
+TEST_CASE("graph move constructor conforms to iterator validity") {
+	auto g = gdwg::graph<int, std::string>{{1, 2}};
+	g.insert_edge(1, 2);
+	CHECK(not g.empty());
+
+	const auto it = std::begin(g);
+	CHECK(it != std::end(g));
+
+	const auto moved = gdwg::graph{std::move(g)};
+	CHECK(g.empty());
+	CHECK(not moved.empty());
+	CHECK(it == std::begin(moved));
+	CHECK(it != std::begin(g));
+}
+
+// Specification 2.2 auto operator=(graph&& other)
+// Purpose:  Ensure the graph move assignment operator functions as expected.
+// Expected: The graph move assignment should default construct the moved from
+//			 object. *this should be equal to *other before the move operation.
+//           Iterators pointing to the original moved-from object should be valid,
+//			 instead pointing to the moved into object.
+TEST_CASE("graph move assignment conforms to iterator validity") {
+	auto g = gdwg::graph<int, std::string>{{1, 2}};
+	g.insert_edge(1, 2);
+	CHECK(not g.empty());
+
+	const auto copy = g;
+
+	const auto it = std::begin(g);
+	CHECK(it != std::end(g));
+
+	auto moved = gdwg::graph<int, std::string>{};
+	moved = std::move(g);
+	CHECK(g.empty());
+	CHECK(not moved.empty());
+	CHECK(it == std::begin(moved));
+	CHECK(it != std::begin(g));
+}
+
+// Specification 2.2 graph(const graph& other)
+// Purpose:  Ensure the graph copy constructor functions as expected.
+// Expected: The graph copy constructor should compare equal to the copied-from
+// 			 graph.
+TEST_CASE("graph copy constructor compares equal to original graph") {
+	auto g = gdwg::graph<int, std::string>{{1, 2}};
+	g.insert_edge(1, 2);
+
+	const auto copy = gdwg::graph{g};
+	CHECK(g == copy);
+}
+
+// Specification 2.2 operator=(const graph& other) -> graph&
+// Purpose:  Ensure the copy assignment operator functions as expected.
+// Expected: The graph copy assignment operator should compare equal to the
+//			 copied-from class.
+TEST_CASE("graph copy assignment compares equal to original graph") {
+	auto g = gdwg::graph<int, std::string>{{1, 2}};
+	g.insert_edge(1, 2);
+
+	auto copy = gdwg::graph<int, std::string>{};
+	copy = g;
+	CHECK(g == copy);
+}
+
+// Specification 2.3.2 weighted_edge(const N& src, const N& dst, const E& w);
+// Purpose:  Ensure the weighted_edge constructor functions as expected.
+// Expected: The weighted_edge should construct as a derived class from the
+//			 edge class.
+TEST_CASE("weighted edge constructor is derived from the edge class") {
+	auto edge = std::make_unique<gdwg::weighted_edge<int, int>>(1, 2, 3);
+	const auto downcast = std::unique_ptr<gdwg::edge<int, int>>(std::move(edge));
+}
+
+// Specification 2.3.2 weighted_edge implementation
+// Purpose:  Ensure the weighted_edge implements edge functions.
+// Expected: The weighted_edge should implement all edge functions such that
+//           they are callable from the base class.
+TEST_CASE("weighted edge correctly implements edge") {
+	auto we = std::make_unique<gdwg::weighted_edge<int, int>>(1, 2, 3);
+	const auto e = std::unique_ptr<gdwg::edge<int, int>>(std::move(we));
+
+	CHECK(e->print_edge() == "1 -> 2 | W | 3");
+	CHECK(e->is_weighted());
+	CHECK(*e->get_weight() == 3);
+	CHECK(e->get_nodes() == std::pair<int, int>{1, 2});
+	CHECK(*e == *std::make_unique<gdwg::weighted_edge<int, int>>(1, 2, 3));
+}
+
+// Specification 2.3.3 unweighted_edge(const N& src, const N& dst);
+// Purpose:  Ensure the unweighted_edge constructor functions as expected.
+// Expected: The unweighted_edge should construct as a derived class from the
+//			 edge class.
+TEST_CASE("unweighted edge constructor is derived from the edge class") {
+	auto edge = std::make_unique<gdwg::unweighted_edge<int, int>>(1, 2);
+	const auto downcast = std::unique_ptr<gdwg::edge<int, int>>(std::move(edge));
+}
+
+// Specification 2.3.3 unweighted_edge(const N& src, const N& dst);
+// Purpose:  Ensure the unweighted_edge constructor functions as expected.
+// Expected: The unweighted_edge should implement all edge functions such that
+//           they are callable from the base class.
+TEST_CASE("unweighted edge correctly implements edge") {
+	auto ue = std::make_unique<gdwg::unweighted_edge<int, int>>(1, 2);
+	const auto e = std::unique_ptr<gdwg::edge<int, int>>(std::move(ue));
+
+	CHECK(e->print_edge() == "1 -> 2 | U");
+	CHECK(not e->is_weighted());
+	CHECK(e->get_weight() == std::nullopt);
+	CHECK(e->get_nodes() == std::pair<int, int>{1, 2});
+	CHECK(*e == *std::make_unique<gdwg::unweighted_edge<int, int>>(1, 2));
+}
+
+// Specification 2.4 insert_node
+// Purpose:  Ensure the insert_node method functions as expected.
+// Expected: The insert node method should return true on first insertion, and
+//			 false afterwards.
+TEST_CASE("insert_node returns true on first, false on second of same node") {
+	auto g = gdwg::graph<int, std::string>{};
+	CHECK(g.insert_node(1));
+	CHECK(not g.insert_node(1));
+}
+
+// Specification 2.4 insert_edge
+// Purpose:  Ensure the insert_edge method functions as expected.
+// Expected: The insert edge method should return true if a new edge is added
+//			 to the graph, and false if the edge already existed.
+TEST_CASE("insert_edge returns true on unique edge insertion, false otherwise") {
+	auto g = gdwg::graph<int, std::string>{};
+	CHECK(g.insert_node(1));
+	CHECK(g.insert_node(2));
+	CHECK(g.insert_edge(1, 2));
+	CHECK(not g.insert_edge(1, 2));
+	CHECK(g.insert_edge(1, 2, "different_weight"));
+}
+
+// Specification 2.4 insert_edge
+// Purpose:  Ensure the insert_edge method functions as expected.
+// Expected: The insert edge method throws if either src or dest do not exist.
+TEST_CASE("insert_edge throws if either src or dest do not exist") {
+	auto g = gdwg::graph<int, std::string>{};
+	CHECK(g.insert_node(1));
+	REQUIRE_THROWS_AS(g.insert_edge(1, 2), std::runtime_error);
+	REQUIRE_THROWS_WITH(g.insert_edge(1, 2),
+	                    "Cannot call gdwg::graph<N, E>::insert_edge when either src or dst node does not exist");
+	REQUIRE_THROWS_AS(g.insert_edge(2, 1), std::runtime_error);
+	REQUIRE_THROWS_WITH(g.insert_edge(2, 1),
+	                    "Cannot call gdwg::graph<N, E>::insert_edge when either src or dst node does not exist");
+}
+
+// Specification 2.4 replace_node
+// Purpose:  Ensure the replace_node method functions as expected.
+// Expected: The replace_node method should remove the existing node and replace
+//			 it with a new node that doesn't yet exist in the graph, returning
+//			 true or false to determine if the replacement could take place.
+TEST_CASE("replace_node returns based on the modification made") {
+	auto g = gdwg::graph<int, std::string>{};
+	g.insert_node(1);
+	CHECK(g.replace_node(1, 2));
+	g.insert_node(1);
+	CHECK(not g.replace_node(1, 2));
+}
+
+// Specification 2.4 replace_node
+// Purpose:  Ensure the replace_node method functions as expected.
+// Expected: The replace_node method should throw if the first argument does
+//			 not exist in the graph.
+TEST_CASE("replace_node throws when first argument does not exist in graph") {
+	auto g = gdwg::graph<int, std::string>{};
+	REQUIRE_THROWS_AS(g.replace_node(1, 2), std::runtime_error);
+	REQUIRE_THROWS_WITH(g.replace_node(1, 2), "Cannot call gdwg::graph<N, E>::replace_node on a node that doesn't exist");
+}
+
+// Specification 2.4 merge_replace_node
+// Purpose:  Ensure the merge_replace_node method functions as expected.
+// Expected: The merge_replace_node method should follow the provided basic
+//			 example in the specification.
+TEST_CASE("merge_replace_node correctly redirects edges") {
+	auto g = gdwg::graph<std::string, int>{"A", "B", "C", "D"};
+	g.insert_edge("A", "B", 1);
+	g.insert_edge("A", "C", 2);
+	g.insert_edge("A", "D", 3);
+
+	g.merge_replace_node("A", "B");
+
+	auto expected = gdwg::graph<std::string, int>{"B", "C", "D"};
+	expected.insert_edge("B", "B", 1);
+	expected.insert_edge("B", "C", 2);
+	expected.insert_edge("B", "D", 3);
+
+	CHECK(g == expected);
+}
+
+// Specification 2.4 merge_replace_node
+// Purpose:  Ensure the merge_replace_node method functions as expected.
+// Expected: The merge_replace_node method should follow the second basic
+//			 example in the specification, removing duplicate edges.
+TEST_CASE("merge_replace_node removes duplicate edges") {
+	auto g = gdwg::graph<std::string, int>{"A", "B", "C", "D"};
+	g.insert_edge("A", "B", 1);
+	g.insert_edge("A", "C", 2);
+	g.insert_edge("A", "D", 3);
+	g.insert_edge("B", "B", 1);
+
+	g.merge_replace_node("A", "B");
+
+	auto expected = gdwg::graph<std::string, int>{"B", "C", "D"};
+	expected.insert_edge("B", "B", 1);
+	expected.insert_edge("B", "C", 2);
+	expected.insert_edge("B", "D", 3);
+
+	CHECK(g == expected);
+}
+
+// Specification 2.4 merge_replace_node
+// Purpose:  Ensure the merge_replace_node method functions as expected.
+// Expected: The merge_replace_node method should throw if the first or second
+//			 arguements do not exist in the graph.
+TEST_CASE("merge_replace_node throws when either nodes do not exist") {
+	auto g = gdwg::graph<std::string, int>{};
+	g.insert_node("A");
+	REQUIRE_THROWS_AS(g.merge_replace_node("A", "B"), std::runtime_error);
+	REQUIRE_THROWS_WITH(g.merge_replace_node("A", "B"),
+	                    "Cannot call gdwg::graph<N, E>::merge_replace_node on old or new data if they don't exist in "
+	                    "the graph");
+	REQUIRE_THROWS_AS(g.merge_replace_node("B", "A"), std::runtime_error);
+	REQUIRE_THROWS_WITH(g.merge_replace_node("B", "A"),
+	                    "Cannot call gdwg::graph<N, E>::merge_replace_node on old or new data if they don't exist in "
+	                    "the graph");
+}
+
+// Specification 2.4 erase_node
+// Purpose:  Ensure the erase_node method functions as expected
+// Expected: Erase node should remove all incoming and outgoing edges, returning
+//			 true if it was removed and false if the node didn't exist.
+TEST_CASE("erase_node removes all outgoing and incoming edges") {
+	auto g = gdwg::graph<std::string, int>{"A", "B"};
+	g.insert_edge("A", "B", 1);
+	g.insert_edge("B", "A", 1);
+	CHECK(g.erase_node("A"));
+
+	auto expected = gdwg::graph<std::string, int>{"B"};
+	CHECK(g == expected);
+	CHECK(not g.erase_node("A"));
+}
+
+// Specification 2.4 erase_edge
+// Purpose:  Ensure the erase_edge method functions as expected
+// Expected: Ensure erase_edge removes the specific edge including the specified
+//			 weight.
+TEST_CASE("erase_edge only removes edges exactly from arguments") {
+	auto g = gdwg::graph<std::string, int>{"A", "B"};
+	g.insert_edge("A", "B", 1);
+	g.insert_edge("B", "A", 1);
+	CHECK(not g.erase_edge("A", "B", std::nullopt));
+	CHECK(g.erase_edge("A", "B", 1));
+
+	auto expected = gdwg::graph<std::string, int>{"A", "B"};
+	expected.insert_edge("B", "A", 1);
+	CHECK(g == expected);
+}
+
+// Specification 2.4 erase_edge
+// Purpose:  Ensure the erase_edge method functions as expected.
+// Expected: The erase_edge method should throw if the first or second
+//			 arguements do not exist in the graph.
+TEST_CASE("erase_edge throws when either nodes do not exist") {
+	auto g = gdwg::graph<std::string, int>{};
+	g.insert_node("A");
+	REQUIRE_THROWS_AS(g.erase_edge("A", "B"), std::runtime_error);
+	REQUIRE_THROWS_WITH(g.erase_edge("A", "B"),
+	                    "Cannot call gdwg::graph<N, E>::erase_edge on src or dst if they don't exist in the graph");
+	REQUIRE_THROWS_AS(g.erase_edge("B", "A"), std::runtime_error);
+	REQUIRE_THROWS_WITH(g.erase_edge("B", "A"),
+	                    "Cannot call gdwg::graph<N, E>::erase_edge on src or dst if they don't exist in the graph");
+}
+
+// Specification 2.4 erase_edge(iterator)
+// Purpose:  Ensure the erase_edge method functions as expected
+// Expected: Ensure erase_edge removes the specified edge from an iterator
+// 			 argument.
+TEST_CASE("erase_edge removes edges from specified iterator") {
+	auto g = gdwg::graph<std::string, int>{"A", "B"};
+	g.insert_edge("A", "B", 1);
+	g.insert_edge("B", "A", 1);
+	CHECK(g.erase_edge(std::begin(g)) != std::end(g));
+	CHECK(std::distance(std::begin(g), std::end(g)) == 1);
+	CHECK(g.erase_edge(std::begin(g)) == std::end(g));
+	CHECK(std::distance(std::begin(g), std::end(g)) == 0);
+}
+
+// Specification 2.4 erase_edge(iterator, iterator)
+// Purpose:  Ensure the erase_edge method functions as expected
+// Expected: Ensure erase_edge removes all edges when provided with begin and
+//			 end iterators, returning end.
+TEST_CASE("erase_edge removes all edges from entire range of iterators") {
+	auto g = gdwg::graph<std::string, int>{"A", "B", "C"};
+	g.insert_edge("A", "B", 1);
+	g.insert_edge("B", "A", 1);
+	g.insert_edge("B", "C", 1);
+	CHECK(g.erase_edge(std::begin(g), std::end(g)) == std::end(g));
+	CHECK(std::distance(std::begin(g), std::end(g)) == 0);
+}
+
+// Specification 2.4 erase_edge(iterator, iterator)
+// Purpose:  Ensure the erase_edge method functions as expected
+// Expected: Ensure erase_edge removes the specified range of iterators, without
+//			 returning end as some edges remain.
+TEST_CASE("erase_edge removes edges from range of iterators") {
+	auto g = gdwg::graph<std::string, int>{"A", "B", "C"};
+	g.insert_edge("A", "B", 1);
+	g.insert_edge("B", "A", 1);
+	g.insert_edge("B", "C", 1);
+	CHECK(g.erase_edge(std::begin(g), std::next(std::begin(g), 2)) != std::end(g));
+	CHECK(std::distance(std::begin(g), std::end(g)) == 1);
+}
+
+// Specification: 2.5 Accessors
+// Purpose:  Ensure is_node() fails on values not inside the graph.
+// Expected: The is_node method returns false only on values that are not
+//           inserted into the graph.
+TEST_CASE("is_node should return false on values not present in the graph") {
+	auto g = gdwg::graph<int, std::string>{};
+	CHECK(not g.is_node(0));
+	g.insert_node(1);
+	CHECK(not g.is_node(0));
+	g.insert_node(2);
+	CHECK(not g.is_node(0));
+}
+
+// Specification: 2.5 Accessors
+// Purpose:  Ensure empty() returns true on empty graphs.
+// Expected: The empty method returns true only with empty graphs of different
+// 			 types.
+TEST_CASE("empty should return true only if there are no nodes in the graph") {
+	CHECK(gdwg::graph<int, std::string>{}.empty());
+	CHECK(gdwg::graph<char, std::vector<int>>{}.empty());
+	CHECK(gdwg::graph<bool, std::set<float>>{}.empty());
+}
+
+// Specification: 2.5 Accessors
+// Purpose:  Ensure empty() returns false on graphs containing nodes.
+// Expected: The empty method returns false with on each graphs containing nodes
+// 			 regardless of underlying type.
+TEST_CASE("empty should return false on graphs containing nodes") {
+	CHECK(not gdwg::graph<int, std::string>{1, 5}.empty());
+	CHECK(not gdwg::graph<char, std::vector<int>>{'v'}.empty());
+	CHECK(not gdwg::graph<bool, std::set<float>>{true}.empty());
+}
+
+// Specification: 2.5 Accessors
+// Purpose:  Ensure is_connected returns true only if an edge from src -> dst
+// 			 is connected.
+// Expected: The is_connected method returns true on connected nodes only.
+TEST_CASE("is_connected only returns true on connected nodes") {
+	auto g = gdwg::graph<int, std::string>{};
+	g.insert_node(1);
+	g.insert_node(2);
+	g.insert_node(3);
+	g.insert_edge(1, 2);
+	CHECK(g.is_connected(1, 2));
+	CHECK(not g.is_connected(1, 3));
+	CHECK(not g.is_connected(2, 3));
+}
+
+// Specification: 2.5 Accessors
+// Purpose:  Ensure is_connected reports weighted edges as connected
+// Expected: The is_connected method returns true even if an edge has been
+// inserted with a weight.
+TEST_CASE("is_connected reports weighted edges as connected") {
+	auto g = gdwg::graph<int, float>{};
+
+	g.insert_node(1);
+	g.insert_node(2);
+	g.insert_edge(1, 2, 0.5f);
+	CHECK(g.is_connected(1, 2));
+	CHECK(not g.is_connected(2, 1));
+}
+
+// Specification: 2.5 Accessors
+// Purpose:  Ensure is_connected distinguishes omnidirectional edges from
+// 			 bidirectional edges.
+// Expected: The is_connected method only returns true if an edge from a -> b has
+// 			 been explicitly added while also respecting previously inserted
+//		 	 edges.
+TEST_CASE("is_connected distinguishes omnidirectional and bidirectional connections") {
+	auto g = gdwg::graph<int, std::string>{};
+
+	g.insert_node(1);
+	g.insert_node(2);
+	CHECK(not g.is_connected(1, 2));
+	CHECK(not g.is_connected(2, 1));
+
+	g.insert_edge(1, 2);
+	CHECK(g.is_connected(1, 2));
+	CHECK(not g.is_connected(2, 1));
+
+	g.insert_edge(2, 1);
+	CHECK(g.is_connected(1, 2));
+	CHECK(g.is_connected(2, 1));
+}
+
+// Specification: 2.5 Accessors
+// Purpose:  Ensure is_connected throws as expected.
+// Expected: The is_connected method should throw when wither the first or second
+// 			 argument nodes do not exist in the graph.
+TEST_CASE("is_connected throws when src or dst do not exist") {
+	auto g = gdwg::graph<int, std::string>{};
+	g.insert_node(1);
+
+	REQUIRE_THROWS_AS(g.is_connected(1, 2), std::runtime_error);
+	REQUIRE_THROWS_WITH(g.is_connected(1, 2),
+	                    "Cannot call gdwg::graph<N, E>::is_connected if src or dst node don't exist in the graph");
+	REQUIRE_THROWS_AS(g.is_connected(2, 1), std::runtime_error);
+	REQUIRE_THROWS_WITH(g.is_connected(2, 1),
+	                    "Cannot call gdwg::graph<N, E>::is_connected if src or dst node don't exist in the graph");
+}
+
+// Specification: 2.5 Accessors
+// Purpose:  Ensure the nodes method functions as expected.
+// Expected: The nodes() method should return copies of the nodes in ascending
+//			 order, regardless of their insertion.
+TEST_CASE("nodes should return copy in ascending order") {
+	auto g = gdwg::graph<int, std::string>{};
+	g.insert_node(1);
+	g.insert_node(3);
+	g.insert_node(2);
+
+	REQUIRE(g.nodes() == std::vector<int>{1, 2, 3});
+}
+
+// Specification: 2.5 Accessors
+// Purpose:  Ensure the nodes method functions as expected.
+// Expected: The nodes() method should return an empty vector when no nodes are
+//			 present.
+TEST_CASE("nodes should return nothing when empty") {
+	auto g = gdwg::graph<int, std::string>{};
+	REQUIRE(g.nodes() == std::vector<int>{});
+}
+
+// Specification: 2.5 Accessors
+// Purpose:  The find method functions as expected.
+// Expected: The find method should return the end iterator when nothing is
+//			 present.
+TEST_CASE("find should return end iterator when empty") {
+	auto g = gdwg::graph<int, std::string>{};
+	REQUIRE(g.find(1, 2) == std::end(g));
+}
+
+// Specification: 2.5 Accessors
+// Purpose:  The find method functions as expected.
+// Expected: The find method should return an iterator to the object matching
+//			 the arguments to find.
+TEST_CASE("find should return iterator when arguments match existing edge") {
+	auto g = gdwg::graph<int, std::string>{};
+	g.insert_node(1);
+	g.insert_node(2);
+	g.insert_edge(1, 2);
+	REQUIRE(g.find(1, 2) != std::end(g));
+}
+
+// Specification: 2.5 Accessors
+// Purpose:  The find method functions as expected.
+// Expected: The find method should differentiate between weighted and
+//			 nonweighted edges.
+TEST_CASE("find should differentiate between weighted and nonweighted edges") {
+	auto g = gdwg::graph<int, std::string>{};
+	g.insert_node(1);
+	g.insert_node(2);
+	g.insert_edge(1, 2, "weight");
+	REQUIRE(g.find(1, 2) == std::end(g));
+	REQUIRE(g.find(1, 2, "weight") != std::end(g));
+}
+
+// Specification: 2.5 Accessors
+// Purpose:  Ensure edges throws if one of the node parameters do not exist.
+// Expected: The edges method should throw with a specific error message using
+//           std::runtime_error on failure.
+TEST_CASE("edges should throw when called on edges that do not exist") {
+	auto g = gdwg::graph<int, float>{};
+
+	REQUIRE_THROWS_AS(g.edges(1, 2), std::runtime_error);
+	REQUIRE_THROWS_WITH(g.edges(1, 2),
+	                    "Cannot call gdwg::graph<N, E>::edges"
+	                    " if src or dst node don't exist in the graph");
+}
+
+// Specification: 2.5 Accessors
+// Purpose:  Ensure edges does not throw if both nodes exist in the graph,
+// 			 even when there are no edges.
+// Expected: The edges method should return an empty std::vector.
+TEST_CASE("edges should return an empty list of edges during a call to a graph with two nodes and no edges") {
+	auto g = gdwg::graph<int, float>{1, 2};
+	REQUIRE(g.edges(1, 2).empty());
+}
+
+// Specification: 2.5 Accessors
+// Purpose:  Ensure edges does not throw if both nodes exist in the graph.
+// Expected: The edges method should return a vector of unique ptrs when called with
+// 			 valid node parameters.
+TEST_CASE("edges should return the list of edges when called on nodes that do exist") {
+	auto g = gdwg::graph<int, float>{1, 2};
+	g.insert_edge(1, 2);
+	REQUIRE(!g.edges(1, 2).empty());
+}
+
+// Specification: 2.5 Accessors
+// Purpose:  Ensure edges does not confuse reverse direction edges.
+// Expected: The edges method should return an empty vector even if edges are
+// 			 inserted in the other direction.
+TEST_CASE("edges should return an empty vector if edges are inserted in the other direction between two nodes") {
+	auto g = gdwg::graph<int, float>{1, 2};
+	g.insert_edge(1, 2);
+	g.insert_edge(1, 2);
+	REQUIRE(g.edges(2, 1).empty());
+}
+
+// Specification: 2.5 Accessors
+// Purpose:  Ensure edges returns a sorted vector of edges when called on two
+// 			 nodes with multiple edges.
+// Expected: The edges method should return a vector sorted in order according to
+// 			 the edge weights, with no weight considered lower priority than all
+//			 edges with weights.
+TEST_CASE("edges should sort inserted edges when called on nodes with multiple edges") {
+	auto g = gdwg::graph<int, float>{1, 2};
+	g.insert_edge(1, 2);
+	g.insert_edge(1, 2, 0.1f);
+	g.insert_edge(1, 2, 0.3f);
+	g.insert_edge(1, 2, 0.2f);
+	const auto result = g.edges(1, 2);
+	REQUIRE(result.size() == 4);
+	REQUIRE(result[0]->get_weight() == std::nullopt);
+	REQUIRE(result[1]->get_weight().value() == 0.1f);
+	REQUIRE(result[2]->get_weight().value() == 0.2f);
+	REQUIRE(result[3]->get_weight().value() == 0.3f);
+}
+
+// Specification: 2.5 Accessors
+// Purpose:	 The connections method functions as expected.
+// Expected: Connections should return nothing when no edges are present.
+TEST_CASE("connections should return nothing when no edges are present") {
+	auto g = gdwg::graph<int, std::string>{};
+	g.insert_node(1);
+	g.insert_node(2);
+	REQUIRE(g.connections(1).empty());
+}
+
+// Specification: 2.5 Accessors
+// Purpose:	 The connections method functions as expected.
+// Expected: Connections should return all outgoing edges from a node in
+// 			 ascending order.
+TEST_CASE("connections should return outgoing edges in ascending order") {
+	auto g = gdwg::graph<int, std::string>{};
+	g.insert_node(1);
+	g.insert_node(2);
+	g.insert_node(3);
+	g.insert_node(4);
+	g.insert_edge(1, 2);
+	g.insert_edge(1, 4);
+	g.insert_edge(1, 3);
+	REQUIRE(g.connections(1) == std::vector<int>{2, 3, 4});
+}
+
+// Specification: 2.5 Accessors
+// Purpose:	 The connections method functions as expected.
+// Expected: Connections should return all outgoing edges without duplicates.
+TEST_CASE("connections should return outgoing edges without duplicates") {
+	auto g = gdwg::graph<int, std::string>{};
+	g.insert_node(1);
+	g.insert_node(2);
+	g.insert_edge(1, 2);
+	g.insert_edge(1, 2, "weight");
+	REQUIRE(g.connections(1) == std::vector<int>{2});
+}
+
+// Specification: 2.5 Accessors
+// Purpose:  The connections method functions as expected.
+// Purpose:  The connections method should throw when the node doesn't exist.
+TEST_CASE("connected throws on non-existent node") {
+	auto g = gdwg::graph<int, std::string>{};
+	REQUIRE_THROWS_AS(g.connections(1), std::runtime_error);
+	REQUIRE_THROWS_WITH(g.connections(1), "Cannot call gdwg::graph<N, E>::connections if src doesn't exist in the graph");
+}
+
+// Specification: 2.6 Iterator Access
+// Purpose:  Ensure the begin() and end() iterators are equal in empty graphs
+// Expected: begin() should equal end() in a default-contructed graph.
+TEST_CASE("begin() and end() iterators should be equal in an empty graph") {
+	auto g = gdwg::graph<int, float>{};
+	REQUIRE(std::begin(g) == std::end(g));
+}
+
+// Specification: 2.6 Iterator Access
+// Purpose:  Ensure the distance between two iterators equals the expected
+// 			 edge count of the graph.
+// Expected: std::distance(begin(), end()) should equal the graph size.
+TEST_CASE("the distance of begin() and end() should equal the graph size") {
+	auto g = gdwg::graph<int, float>{0, 1};
+	REQUIRE(std::distance(std::begin(g), std::end(g)) == 0);
+	g.insert_edge(0, 1);
+	REQUIRE(std::distance(std::begin(g), std::end(g)) == 1);
+	g.insert_edge(1, 0);
+	REQUIRE(std::distance(std::begin(g), std::end(g)) == 2);
+}
+
+// Specification: 2.6 Iterator Access
+// Purpose:  Ensure that iterators also visit edges with weights.
+// Expected: The distance between begin and end iterators should be one
+// 			 after an edge with a weight is inserted.
+TEST_CASE("begin() and end() iterators visit edges with weights") {
+	auto g = gdwg::graph<int, float>{0, 1};
+	g.insert_edge(0, 1, 0.5f);
+	REQUIRE(std::distance(std::begin(g), std::end(g)) == 1);
+}
+
+// Specification: 2.7 Comparisons
+// Purpose:  Ensure that graphs that are empty compare as equal.
+// Expected: When compared with operator==, two empty graphs should be equal.
+TEST_CASE("empty graphs should compare equal using operator==") {
+	auto first = gdwg::graph<int, float>{};
+	auto second = gdwg::graph<int, float>{};
+	REQUIRE(first == second);
+}
+
+// Specification: 2.7 Comparisons
+// Purpose:  Ensure operator==  does not depend on insertion order for nodes
+// Expected: Two graphs which contain the same nodes inserted in a different
+// 			 order should compare equal regardless.
+TEST_CASE("two graphs containing the same nodes inserted in a different order should compare equal") {
+	auto first = gdwg::graph<int, float>{};
+	first.insert_node(1);
+	first.insert_node(2);
+	auto second = gdwg::graph<int, float>{};
+	second.insert_node(2);
+	second.insert_node(1);
+	REQUIRE(first == second);
+}
+
+// Specification: 2.7 Comparisons
+// Purpose:  Ensure operator== does not depend on insertion order for edges
+// Expected: Two graphs which contain the same nodes, with edges inserted in a different
+// 			 order should compare equal regardless.
+TEST_CASE("two graphs containing the same edges inserted in a different order should compare equal") {
+	auto first = gdwg::graph<int, float>{};
+	first.insert_node(1);
+	first.insert_node(2);
+	first.insert_edge(1, 2, 0.5f);
+	first.insert_edge(1, 2, 0.9f);
+	first.insert_edge(2, 1);
+	auto second = gdwg::graph<int, float>{};
+	second.insert_node(1);
+	second.insert_node(2);
+	second.insert_edge(1, 2, 0.9f);
+	second.insert_edge(2, 1);
+	second.insert_edge(1, 2, 0.5f);
+	REQUIRE(first == second);
+}
+
+// Specification: 2.8 Extractor
+// Purpose:  Ensure the extractor functions on the empty graph edge case.
+// Expected: An empty graph is extracted as just a newline.
+TEST_CASE("extractor formats an empty graph correctly") {
+	auto out = std::ostringstream{};
+	out << gdwg::graph<int, int>{};
+	CHECK(out.str() == "\n");
+}
+
+// Specification: 2.8 Extractor
+// Purpose:  Ensure the extractor functions as expected for a sufficiently complex graph.
+// Expected: After a large graph is extracted into a stringstream, the output should equal
+// 			 the expected output with the correct ordering.
+TEST_CASE("extractor formats output according to specification") {
+	const auto v = std::vector<std::tuple<int, int, std::optional<int>>>{
+	    {4, 1, -4},
+	    {3, 2, 2},
+	    {2, 4, std::nullopt},
+	    {2, 4, 2},
+	    {2, 1, 1},
+	    {4, 1, std::nullopt},
+	    {6, 2, 5},
+	    {6, 3, 10},
+	    {1, 5, -1},
+	    {3, 6, -8},
+	    {4, 5, 3},
+	    {5, 2, std::nullopt},
+	};
+	auto g = gdwg::graph<int, int>{64};
+	for (const auto& [from, to, weight] : v) {
+		g.insert_node(from);
+		g.insert_node(to);
+		if (weight.has_value()) {
+			g.insert_edge(from, to, *weight);
+		}
+		else {
+			g.insert_edge(from, to);
+		}
+	}
+	auto out = std::ostringstream{};
+	out << g;
+	const auto expected_output = std::string_view(R"(
+1 (
+  1 -> 5 | W | -1
+)
+2 (
+  2 -> 1 | W | 1
+  2 -> 4 | U
+  2 -> 4 | W | 2
+)
+3 (
+  3 -> 2 | W | 2
+  3 -> 6 | W | -8
+)
+4 (
+  4 -> 1 | U
+  4 -> 1 | W | -4
+  4 -> 5 | W | 3
+)
+5 (
+  5 -> 2 | U
+)
+6 (
+  6 -> 2 | W | 5
+  6 -> 3 | W | 10
+)
+64 (
+)
+)");
+	CHECK(out.str() == expected_output);
+}
+
+// Specification: 2.9.1 Iterator Constructor
+// Purpose:  The iterator should conform to the specification.
+// Expected: A default constructed iterator should compare equal to another.
+TEST_CASE("default constructed iterators compare equal") {
+	CHECK(gdwg::graph<int, int>::iterator{} == gdwg::graph<int, int>::iterator{});
+}
+
+// Specification: 2.9.2 Iterator Source
+// Purpose:  The iterator should conform to the specification.
+// Expected: The dereference operator should result in the from, to and weight
+//			 of the current iterator position.
+TEST_CASE("iterators return from, to and weight") {
+	auto g = gdwg::graph<int, int>{1, 2};
+	g.insert_edge(1, 2, 3);
+	CHECK(std::begin(g) != std::end(g));
+	const auto& [from, to, weight] = *std::begin(g);
+	CHECK(from == 1);
+	CHECK(to == 2);
+	CHECK(weight == 3);
+}
+
+// Specification: 2.9.3 Iterator Traversal
+// Purpose:  The iterator should support traversal (as a bidirectional iterator).
+// Expected: Incrementing and decrementing the iterator should maintain the
+//			 expected bidirectional iterator behaviour by the standard.
+TEST_CASE("iterators support bidirectional iteration") {
+	auto g = gdwg::graph<int, int>{1, 2, 4, 5};
+	g.insert_edge(1, 2, 3);
+	g.insert_edge(4, 5, 6);
+	CHECK(std::begin(g) != std::end(g));
+	CHECK(std::distance(std::begin(g), std::end(g)) == 2);
+
+	const auto first = std::begin(g);
+	const auto second = std::next(std::begin(g), 1);
+
+	auto it = std::begin(g);
+	CHECK(it == first);
+	++it;
+	CHECK(it == second);
+	--it;
+	CHECK(it == first);
+	CHECK(it++ == first);
+	CHECK(it-- == second);
+}
+
+// Specification: 2.9.4 Iterator Comparison
+// Purpose:  The iterator should support comparison between other iterators.
+// Expected: The iterators should return true of they point to the same elements,
+//			 false otherwise.
+TEST_CASE("iterators support equality comparison") {
+	auto g = gdwg::graph<int, int>{1, 2, 4, 5};
+	g.insert_edge(1, 2, 3);
+	CHECK(std::begin(g) != std::end(g));
+
+	const auto first = std::begin(g);
+	const auto second = std::next(std::end(g), -1);
+	CHECK(first == second);
+	CHECK(not(first == std::end(g)));
+}
+
+// Specification: 2.9.3 Iterator Traversal
+// Purpose:  The iterator should traverse the graph as expected.
+// Expected: The iterator should traverse the graph in an ascending order,
+//			 sorting via form, to and weight respectively. Empty nodes should
+//			 be ignored.
+TEST_CASE("iterator traverses in ascending order") {
+	auto g = gdwg::graph<int, int>{1, 5, 6, 9, 3, 49, 667};
+	g.insert_edge(5, 1); // insert edges manually out of order
+	g.insert_edge(1, 5);
+	g.insert_edge(9, 1);
+	g.insert_edge(3, 1);
+	g.insert_edge(1, 1);
+
+	const auto expected = std::vector<std::pair<int, int>>{
+	    {1, 1},
+	    {1, 5},
+	    {3, 1},
+	    {5, 1},
+	    {9, 1},
+	};
+	auto i = 0ul;
+	for (const auto& [f, d] : expected) {
+		CHECK(f == expected[i].first);
+		CHECK(d == expected[i].second);
+		++i;
+	}
+}
+
+// Specification: 2.10 Compulsory internal representation
+// Purpose:  Ensure the internal representation meets the specification.
+// Expected: The graph should own resources that are passed in via insert
+// 			 function - leaving scope should be valid.
+// Note: Obviously we can't test for redundant copies here, but we do avoid them
+//		 using a std::set of shared_ptr<N>'s in our implementation.
+TEST_CASE("internal respresentation makes copies, avoiding redundant copies") {
+	auto g = gdwg::graph<std::string, int>{};
+	{
+		auto s1 = std::string{"Hello"};
+		g.insert_node(s1);
+	}
+	CHECK(g.is_node("Hello"));
+}