initial commit

1 files changed, 872 insertions, 0 deletions

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"));
+}