testGraph.cpp
//
// Created by max on 04.08.22.
//
#include <boost/test/unit_test.hpp>
#include <range/v3/all.hpp>
#include <set>
#include "setgraph/graph.hpp"
BOOST_AUTO_TEST_CASE(test_creation) {
using namespace setgraph;
SetGraph<int> graph;
auto a = graph.addVertex(1);
auto b = graph.addVertex(2);
auto c = graph.addVertex(3);
auto d = graph.addVertex(4);
auto ab = *graph.addEdge(a, b);
auto ba = *graph.addEdge(b, a);
auto bc = *graph.addEdge(b, c);
auto cd = *graph.addEdge(c, d);
auto da = *graph.addEdge(d, a);
BOOST_TEST(graph.source(ab) == a);
BOOST_TEST(graph.target(ab) == b);
BOOST_TEST(graph.source(ba) == b);
BOOST_TEST(graph.target(ba) == a);
BOOST_TEST(graph.source(bc) == b);
BOOST_TEST(graph.target(bc) == c);
BOOST_TEST(graph.source(cd) == c);
BOOST_TEST(graph.target(cd) == d);
BOOST_TEST(graph.source(da) == d);
BOOST_TEST(graph.target(da) == a);
BOOST_TEST(graph[a] == 1);
BOOST_TEST(graph[b] == 2);
BOOST_TEST(graph[c] == 3);
BOOST_TEST(graph[d] == 4);
BOOST_TEST(graph.edge(a, b).has_value());
BOOST_TEST(graph.edge(b, a).has_value());
BOOST_TEST(!graph.edge(a, c).has_value());
BOOST_TEST(!graph.edge(a, d).has_value());
BOOST_TEST(graph.edge(d, a).has_value());
}
BOOST_AUTO_TEST_CASE(test_deletion) {
using namespace setgraph;
SetGraph<int> graph;
auto a = graph.addVertex(1);
auto b = graph.addVertex(2);
auto c = graph.addVertex(3);
auto d = graph.addVertex(4);
BOOST_TEST(graph.numVertices() == 4);
auto ab = *graph.addEdge(a, b);
auto ba = *graph.addEdge(b, a);
auto bc = *graph.addEdge(b, c);
auto cd = *graph.addEdge(c, d);
auto da = *graph.addEdge(d, a);
BOOST_TEST(graph.numEdges() == 5);
BOOST_TEST(graph[a] == 1);
BOOST_TEST(graph[b] == 2);
BOOST_TEST(graph[c] == 3);
BOOST_TEST(graph[d] == 4);
BOOST_TEST(graph.edge(a, b).has_value());
BOOST_TEST(graph.edge(b, a).has_value());
BOOST_TEST(!graph.edge(a, c).has_value());
BOOST_TEST(!graph.edge(a, d).has_value());
BOOST_TEST(graph.edge(d, a).has_value());
// removing non-out_edges should not do anything
graph.removeEdge(a, c);
graph.removeEdge(a, d);
graph.removeEdge(c, b);
BOOST_TEST(graph.numEdges() == 5);
BOOST_TEST(graph.edge(a, b).has_value());
BOOST_TEST(graph.edge(b, a).has_value());
BOOST_TEST(!graph.edge(a, c).has_value());
BOOST_TEST(!graph.edge(a, d).has_value());
BOOST_TEST(graph.edge(d, a).has_value());
graph.removeEdge(d, a);
BOOST_TEST(graph.numEdges() == 4);
BOOST_TEST(!graph.edge(d, a).has_value());
BOOST_TEST(graph.edge(a, b).has_value());
BOOST_TEST(graph.edge(b, a).has_value());
BOOST_TEST(!graph.edge(a, c).has_value());
BOOST_TEST(!graph.edge(a, d).has_value());
graph.removeEdge(ab);
BOOST_TEST(!graph.edge(d, a).has_value());
BOOST_TEST(!graph.edge(a, b).has_value());
BOOST_TEST(graph.edge(b, a).has_value());
BOOST_TEST(!graph.edge(a, c).has_value());
BOOST_TEST(!graph.edge(a, d).has_value());
graph.removeVertex(c);
BOOST_TEST(graph.numVertices() == 3);
for (auto e: graph.edges()) {
BOOST_TEST(graph.source(e) != c);
BOOST_TEST(graph.target(e) != c);
}
BOOST_TEST(!graph.edge(d, a).has_value());
BOOST_TEST(!graph.edge(a, b).has_value());
BOOST_TEST(graph.edge(b, a).has_value());
BOOST_TEST(!graph.edge(a, c).has_value());
BOOST_TEST(!graph.edge(a, d).has_value());
graph.removeEdge(ba);
graph.removeEdge(bc);
graph.removeEdge(cd);
graph.removeEdge(da);
BOOST_TEST(graph.numEdges() == 0);
graph.removeVertex(a);
graph.removeVertex(b);
BOOST_TEST(graph.numVertices() == 1);
graph.removeVertex(c);
BOOST_TEST(graph.numVertices() == 1);
graph.removeVertex(d);
BOOST_TEST(graph.numVertices() == 0);
}
BOOST_AUTO_TEST_CASE(test_iteration) {
using namespace setgraph;
SetGraph<int> graph;
std::vector<int> vertex_values{1, 3, 5, 7, 9, 11};
auto vertices = vertex_values | ranges::views::transform([&graph] (const auto& value) { return graph.template addVertex(
value); }) | ranges::to<std::vector>();
std::vector<std::pair<size_t, size_t>> edges{{0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 0}, {3, 1}, {0, 4}};
auto edge_mapper = [&vertices] (const decltype(graph)::edge_descriptor& edge) { return std::make_pair(vertices[edge.first], vertices[edge.second]);};
for (auto [u, v]: edges) graph.addEdge(vertices[u], vertices[v]);
{
auto all_vertices = vertices | ranges::to<std::set>;
BOOST_TEST(graph.numVertices() == all_vertices.size());
for (auto v: graph.vertices()) {
BOOST_TEST(all_vertices.contains(v));
all_vertices.erase(v);
}
BOOST_TEST(all_vertices.empty());
}
{
auto all_edges = edges | ranges::views::transform(edge_mapper) | ranges::to<std::set>;
BOOST_TEST(graph.numEdges() == all_edges.size());
for (auto e: graph.edges()) {
BOOST_TEST(all_edges.contains(e), "additional edge " << e.first << "->" << e.second << " enumerated but not inserted");
all_edges.erase(e);
}
BOOST_TEST(all_edges.empty(), "graph.out_edges() did not enumerate all out_edges");
}
for (auto v: vertices) {
auto out_neighbors = edges
| ranges::views::transform(edge_mapper)
| ranges::views::filter([v](auto edge) { return edge.first == v; })
| ranges::views::transform([](auto edge) { return edge.second; })
| ranges::to<std::set>;
BOOST_TEST(graph.outDegree(v) == out_neighbors.size());
for (auto w: graph.neighbors(v)) {
BOOST_TEST(out_neighbors.contains(w));
out_neighbors.erase(w);
}
BOOST_TEST(out_neighbors.empty());
}
for (auto v: vertices) {
auto out_edges = edges
| ranges::views::transform(edge_mapper)
| ranges::views::filter([v](auto edge) { return edge.first == v; })
| ranges::to<std::set>;
BOOST_TEST(graph.outDegree(v) == out_edges.size());
for (auto e: graph.outEdges(v)) {
BOOST_TEST(out_edges.contains(e));
BOOST_TEST(graph.source(e) == v);
BOOST_TEST(graph.target(e) == e.second);
out_edges.erase(e);
}
BOOST_TEST(out_edges.empty());
}
}
BOOST_AUTO_TEST_CASE(test_undirected) {
using namespace setgraph;
using UnGraph = SetGraph<Empty, Empty, EdgeDirection::Undirected>;
using Vertex = UnGraph::vertex_descriptor;
std::vector<set<std::pair<Vertex, Vertex>>> edgeLists({
{ {0, 1}, {0, 4}, {1, 2}, {1, 3}, {1, 4}, {4, 3}, {4, 5}, {2, 3}, {3, 6}, {3, 8}, {5, 10}, {5, 11}, {5, 12}, {10, 9}, {11, 12}, {12, 13}, {8, 9}, {8, 13}, {8, 6}, {6, 7} },
{ {0, 1}, {0, 14}, {0, 15}, {0, 16}, {1, 2}, {2, 3}, {2, 14}, {3, 4}, {3, 5}, {3, 17}, {4, 5}, {5, 6}, {5, 7}, {6, 7}, {6, 28}, {7, 8}, {8, 9}, {8, 10}, {8, 11}, {8, 12}, {8, 54}, {9, 11}, {9, 50}, {10, 12}, {10, 40}, {10, 42}, {11, 12}, {11, 15}, {11, 16}, {12, 13}, {12, 14}, {12, 48}, {13, 14}, {13, 45}, {14, 44}, {17, 18}, {18, 19}, {19, 20}, {20, 21}, {21, 22}, {21, 37}, {22, 23}, {23, 24}, {23, 25}, {25, 26}, {26, 27}, {27, 28}, {28, 51}, {24, 29}, {29, 30}, {30, 31}, {31, 32}, {31, 33}, {33, 34}, {34, 35}, {35, 36}, {35, 39}, {36, 37}, {36, 38}, {37, 43}, {37, 48}, {37, 47}, {38, 56}, {39, 55}, {40, 41}, {40, 42}, {40, 55}, {41, 55}, {43, 44}, {45, 46}, {46, 47}, {47, 48}, {48, 49}, {49, 50}, {51, 52}, {52, 53}, {53, 54}, {55, 56} }
});
for (const auto& edges: edgeLists) {
UnGraph graph;
std::vector<Vertex> vertices;
size_t numVertices = ranges::max(edges | ranges::views::transform([](auto st) { return std::max(st.first, st.second); })) + 1;
BOOST_TEST_MESSAGE("#vertices=" << numVertices);
for (int i = 0; i < numVertices; ++i) vertices.push_back(graph.addVertex());
auto vertexNames = vertices
| ranges::views::enumerate
| ranges::views::transform([](auto st) { return std::make_pair(st.second, st.first);})
| ranges::to<map<UnGraph::vertex_descriptor, size_t>>();
for (auto [s, t]: edges) {
graph.addEdge(vertices[s], vertices[t]);
BOOST_TEST(graph.edge(vertices[s], vertices[t]).has_value(), "edge " << s << "--" << t << " not found after insertion");
}
for (auto edge: graph.edges()) {
auto s = graph.source(edge);
auto t = graph.target(edge);
auto u = vertexNames.at(s);
auto v = vertexNames.at(t);
BOOST_TEST((edges.contains({u, v}) || edges.contains({v, u})), "found unexpected edge " << u << "--" << v);
BOOST_TEST(graph.neighbors(s).contains(t), "vertex " << v << " unexpectedly not a neighbor of " << u);
BOOST_TEST(graph.neighbors(t).contains(s), "vertex " << u << " unexpectedly not a neighbor of " << v);
}
for (auto v: graph.vertices()) {
for (auto w: graph.vertices()) {
if (edges.contains({vertices[v], vertices[w]}) || edges.contains({vertices[w], vertices[v]})) {
BOOST_TEST(graph.neighbors(v).contains(w), "expected neighbor " << v << " of " << w << " not found");
} else {
BOOST_TEST(!graph.neighbors(v).contains(w), "found unexpected neighbor " << w << " of " << v);
BOOST_TEST(!graph.edge(v, w).has_value(), "found unexpected edge " << v << "–" << w);
}
}
}
set<long> del{2, 3, 5, 7, 11};
for (auto v: del) {
graph.removeVertex(v);
}
for (auto v: graph.vertices()) {
BOOST_TEST(!del.contains(v));
for (auto w: graph.neighbors(v)) {
BOOST_TEST(!del.contains(w));
}
for (auto w: graph.inNeighbors(v)) {
BOOST_TEST(!del.contains(w));
}
}
for (auto e: graph.edges()) {
BOOST_TEST(!del.contains(graph.source(e)));
BOOST_TEST(!del.contains(graph.target(e)));
}
}
}
