graph-v3/tests/edge_list/test_edge_list_concepts.cpp at 2a214797aaeeb0940e9e28121fa5d37d01eb5f9f · stdgraph/graph-v3 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
#include <catch2/catch_test_macros.hpp>
#include <graph/edge_list/edge_list.hpp>
#include <graph/edge_list/edge_list_descriptor.hpp>
#include <graph/graph_data.hpp>
#include <graph/adj_list/adjacency_list_concepts.hpp>
#include <vector>
#include <tuple>

using namespace graph;
// Don't use `using namespace graph::edge_list` to avoid ambiguity with adj_list::edge_descriptor


// =============================================================================
// Concept Satisfaction Tests
// =============================================================================

TEST_CASE("basic_sourced_edgelist concept with pairs", "[edge_list][concepts]") {
  using edge_list_type = std::vector<std::pair<int, int>>;
  STATIC_REQUIRE(edge_list::basic_sourced_edgelist<edge_list_type>);
  STATIC_REQUIRE(edge_list::basic_sourced_index_edgelist<edge_list_type>);
  STATIC_REQUIRE(!edge_list::has_edge_value<edge_list_type>);
}

TEST_CASE("basic_sourced_edgelist concept with 2-tuples", "[edge_list][concepts]") {
  using edge_list_type = std::vector<std::tuple<int, int>>;
  STATIC_REQUIRE(edge_list::basic_sourced_edgelist<edge_list_type>);
  STATIC_REQUIRE(edge_list::basic_sourced_index_edgelist<edge_list_type>);
  STATIC_REQUIRE(!edge_list::has_edge_value<edge_list_type>);
}

TEST_CASE("basic_sourced_edgelist concept with 3-tuples", "[edge_list][concepts]") {
  using edge_list_type = std::vector<std::tuple<int, int, double>>;
  STATIC_REQUIRE(edge_list::basic_sourced_edgelist<edge_list_type>);
  STATIC_REQUIRE(edge_list::basic_sourced_index_edgelist<edge_list_type>);
  STATIC_REQUIRE(edge_list::has_edge_value<edge_list_type>);
}

TEST_CASE("basic_sourced_edgelist concept with edge_data (no value)", "[edge_list][concepts]") {
  using edge_type      = graph::edge_data<int, true, void, void>;
  using edge_list_type = std::vector<edge_type>;
  STATIC_REQUIRE(edge_list::basic_sourced_edgelist<edge_list_type>);
  STATIC_REQUIRE(edge_list::basic_sourced_index_edgelist<edge_list_type>);
  STATIC_REQUIRE(!edge_list::has_edge_value<edge_list_type>);
}

TEST_CASE("basic_sourced_edgelist concept with edge_data (with value)", "[edge_list][concepts]") {
  using edge_type      = graph::edge_data<int, true, void, double>;
  using edge_list_type = std::vector<edge_type>;
  STATIC_REQUIRE(edge_list::basic_sourced_edgelist<edge_list_type>);
  STATIC_REQUIRE(edge_list::basic_sourced_index_edgelist<edge_list_type>);
  STATIC_REQUIRE(edge_list::has_edge_value<edge_list_type>);
}

TEST_CASE("basic_sourced_edgelist concept with edge_descriptor (no value)", "[edge_list][concepts]") {
  using edge_list_type = std::vector<edge_list::edge_descriptor<int, void>>;
  STATIC_REQUIRE(edge_list::basic_sourced_edgelist<edge_list_type>);
  STATIC_REQUIRE(edge_list::basic_sourced_index_edgelist<edge_list_type>);
  STATIC_REQUIRE(!edge_list::has_edge_value<edge_list_type>);
}

TEST_CASE("basic_sourced_edgelist concept with edge_descriptor (with value)", "[edge_list][concepts]") {
  using edge_list_type = std::vector<edge_list::edge_descriptor<int, double>>;
  STATIC_REQUIRE(edge_list::basic_sourced_edgelist<edge_list_type>);
  STATIC_REQUIRE(edge_list::basic_sourced_index_edgelist<edge_list_type>);
  STATIC_REQUIRE(edge_list::has_edge_value<edge_list_type>);
}

TEST_CASE("basic_sourced_edgelist concept with string vertex IDs", "[edge_list][concepts]") {
  using edge_list_type = std::vector<std::pair<std::string, std::string>>;
  STATIC_REQUIRE(edge_list::basic_sourced_edgelist<edge_list_type>);
  STATIC_REQUIRE(!edge_list::basic_sourced_index_edgelist<edge_list_type>); // strings are not integral
  STATIC_REQUIRE(!edge_list::has_edge_value<edge_list_type>);
}

TEST_CASE("Nested ranges should NOT satisfy basic_sourced_edgelist", "[edge_list][concepts]") {
  // Adjacency list pattern - vector of vectors
  using nested_type = std::vector<std::vector<int>>;
  STATIC_REQUIRE(!edge_list::basic_sourced_edgelist<nested_type>);
}

// =============================================================================
// Type Alias Tests
// =============================================================================

TEST_CASE("edge_list type aliases", "[edge_list][types]") {
  using EL = std::vector<std::tuple<int, int, double>>;

  // These should compile
  using edge_range = edge_list::edge_range_t<EL>;
  using edge_iter  = edge_list::edge_iterator_t<EL>;
  using edge       = edge_list::edge_t<EL>;
  using edge_val   = edge_list::edge_value_t<EL>;
  using vid        = edge_list::vertex_id_t<EL>;

  STATIC_REQUIRE(std::is_same_v<edge, std::tuple<int, int, double>>);
  STATIC_REQUIRE(std::is_same_v<vid, int>);
  STATIC_REQUIRE(std::is_same_v<edge_val, double>);

  SUCCEED("Type aliases compile successfully");
}

TEST_CASE("edge_list type aliases without edge value", "[edge_list][types]") {
  using EL = std::vector<std::pair<int, int>>;

  using edge_range = edge_list::edge_range_t<EL>;
  using edge_iter  = edge_list::edge_iterator_t<EL>;
  using edge       = edge_list::edge_t<EL>;
  using vid        = edge_list::vertex_id_t<EL>;

  STATIC_REQUIRE(std::is_same_v<edge, std::pair<int, int>>);
  STATIC_REQUIRE(std::is_same_v<vid, int>);

  SUCCEED("Type aliases compile successfully");
}

// =============================================================================
// Runtime Behavior Tests
// =============================================================================

TEST_CASE("basic_sourced_edgelist runtime behavior with pairs", "[edge_list][runtime]") {
  std::vector<std::pair<int, int>> edges = {{1, 2}, {2, 3}, {3, 4}};

  STATIC_REQUIRE(edge_list::basic_sourced_edgelist<decltype(edges)>);

  for (const auto& e : edges) {
    auto src = graph::source_id(edges, e);
    auto tgt = graph::target_id(edges, e);
    REQUIRE(src < tgt); // All our test edges have src < tgt
  }
}

TEST_CASE("basic_sourced_edgelist runtime behavior with edge_descriptor", "[edge_list][runtime]") {
  int s1 = 1, t1 = 2;
  int s2 = 2, t2 = 3;

  edge_list::edge_descriptor<int, void> e1(s1, t1);
  edge_list::edge_descriptor<int, void> e2(s2, t2);

  std::vector<edge_list::edge_descriptor<int, void>> edges = {e1, e2};

  STATIC_REQUIRE(edge_list::basic_sourced_edgelist<decltype(edges)>);

  auto src = graph::source_id(edges, e1);
  auto tgt = graph::target_id(edges, e1);

  REQUIRE(src == 1);
  REQUIRE(tgt == 2);
}

TEST_CASE("has_edge_value runtime behavior", "[edge_list][runtime]") {
  int                                     s = 5, t = 6;
  double                                  v = 3.14;
  edge_list::edge_descriptor<int, double> e(s, t, v);

  std::vector<edge_list::edge_descriptor<int, double>> edges = {e};

  STATIC_REQUIRE(edge_list::has_edge_value<decltype(edges)>);

  auto val = graph::edge_value(edges, e);
  REQUIRE(val == 3.14);
}

// =============================================================================
// Interop with adj_list::edge<G,E> concept (I.2)
// =============================================================================

TEST_CASE("edge_list types satisfy adj_list::edge concept", "[edge_list][concepts][interop]") {
  // After dropping the is_edge_descriptor_v gate, any type whose elements
  // support source_id(g,e) and target_id(g,e) satisfies edge<G,E>.

  // tuple<source, target, value>
  using tuple_el = std::vector<std::tuple<int, int, double>>;
  STATIC_REQUIRE(adj_list::edge<tuple_el, std::tuple<int, int, double>>);

  // pair<source, target>
  using pair_el = std::vector<std::pair<int, int>>;
  STATIC_REQUIRE(adj_list::edge<pair_el, std::pair<int, int>>);

  // edge_data with value
  using ed_type = graph::edge_data<int, true, void, double>;
  using ed_el   = std::vector<ed_type>;
  STATIC_REQUIRE(adj_list::edge<ed_el, ed_type>);

  // edge_list::edge_descriptor
  using desc_type = edge_list::edge_descriptor<int, double>;
  using desc_el   = std::vector<desc_type>;
  STATIC_REQUIRE(adj_list::edge<desc_el, desc_type>);
}