path: root/comp6771/3/src/gdwg_graph.test.cpp

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