From 98cef5e9a772602d42acfcf233838c760424db9a Mon Sep 17 00:00:00 2001 From: Nicolas James Date: Thu, 13 Feb 2025 18:00:17 +1100 Subject: initial commit --- comp6771/3/src/gdwg_graph.test.cpp | 872 +++++++++++++++++++++++++++++++++++++ 1 file changed, 872 insertions(+) create mode 100644 comp6771/3/src/gdwg_graph.test.cpp (limited to 'comp6771/3/src/gdwg_graph.test.cpp') 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 + +// 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{}; + CHECK(g.empty()); +} + +// Specification 2.2 graph(std::initializer_list 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{1, 2, 3}; + const auto g = gdwg::graph{list}; + CHECK(not g.empty()); + CHECK(g.nodes() == std::vector{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{1, 2, 3}; + const auto g = gdwg::graph{std::begin(list), std::end(list)}; + CHECK(not g.empty()); + CHECK(g.nodes() == std::vector{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{{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{{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{}; + 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{{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{{1, 2}}; + g.insert_edge(1, 2); + + auto copy = gdwg::graph{}; + 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>(1, 2, 3); + const auto downcast = std::unique_ptr>(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>(1, 2, 3); + const auto e = std::unique_ptr>(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{1, 2}); + CHECK(*e == *std::make_unique>(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>(1, 2); + const auto downcast = std::unique_ptr>(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>(1, 2); + const auto e = std::unique_ptr>(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{1, 2}); + CHECK(*e == *std::make_unique>(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{}; + 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{}; + 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{}; + 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::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::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{}; + 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{}; + REQUIRE_THROWS_AS(g.replace_node(1, 2), std::runtime_error); + REQUIRE_THROWS_WITH(g.replace_node(1, 2), "Cannot call gdwg::graph::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{"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{"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{"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{"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{}; + 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::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::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{"A", "B"}; + g.insert_edge("A", "B", 1); + g.insert_edge("B", "A", 1); + CHECK(g.erase_node("A")); + + auto expected = gdwg::graph{"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{"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{"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{}; + 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::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::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{"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{"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{"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{}; + 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{}.empty()); + CHECK(gdwg::graph>{}.empty()); + CHECK(gdwg::graph>{}.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{1, 5}.empty()); + CHECK(not gdwg::graph>{'v'}.empty()); + CHECK(not gdwg::graph>{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{}; + 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{}; + + 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{}; + + 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{}; + 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::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::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{}; + g.insert_node(1); + g.insert_node(3); + g.insert_node(2); + + REQUIRE(g.nodes() == std::vector{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{}; + REQUIRE(g.nodes() == std::vector{}); +} + +// 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{}; + 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{}; + 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{}; + 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{}; + + REQUIRE_THROWS_AS(g.edges(1, 2), std::runtime_error); + REQUIRE_THROWS_WITH(g.edges(1, 2), + "Cannot call gdwg::graph::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{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{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{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{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{}; + 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{}; + 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{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{}; + 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{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{}; + REQUIRE_THROWS_AS(g.connections(1), std::runtime_error); + REQUIRE_THROWS_WITH(g.connections(1), "Cannot call gdwg::graph::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{}; + 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{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{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{}; + auto second = gdwg::graph{}; + 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{}; + first.insert_node(1); + first.insert_node(2); + auto second = gdwg::graph{}; + 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{}; + 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{}; + 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{}; + 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>>{ + {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{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::iterator{} == gdwg::graph::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{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{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{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{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>{ + {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's in our implementation. +TEST_CASE("internal respresentation makes copies, avoiding redundant copies") { + auto g = gdwg::graph{}; + { + auto s1 = std::string{"Hello"}; + g.insert_node(s1); + } + CHECK(g.is_node("Hello")); +} -- cgit v1.2.3