| 26 | } |
| 27 | |
| 28 | void test_grid() { |
| 29 | std::vector<Line> s = { |
| 30 | Line(Point(0, 0), Point(0, 3)), |
| 31 | Line(Point(0, 0), Point(3, 0)), |
| 32 | Line(Point(3, 3), Point(0, 3)), |
| 33 | Line(Point(3, 3), Point(3, 0)), |
| 34 | Line(Point(1, 0), Point(1, 3)), |
| 35 | Line(Point(2, 0), Point(2, 3)), |
| 36 | Line(Point(0, 1), Point(3, 1)), |
| 37 | Line(Point(0, 2), Point(3, 2)) |
| 38 | }; |
| 39 | auto [pts, adj] = build_graph(s); |
| 40 | auto pts_copy = pts; |
| 41 | std::sort(pts_copy.begin(), pts_copy.end()); |
| 42 | std::vector<Point> pts1 = { |
| 43 | Point(0, 0), Point(0, 1), Point(0, 2), Point(0, 3), |
| 44 | Point(1, 0), Point(1, 1), Point(1, 2), Point(1, 3), |
| 45 | Point(2, 0), Point(2, 1), Point(2, 2), Point(2, 3), |
| 46 | Point(3, 0), Point(3, 1), Point(3, 2), Point(3, 3), |
| 47 | }; |
| 48 | assert(pts_copy == pts1); |
| 49 | std::map<Point, size_t> m; |
| 50 | for (size_t i = 0; i < pts.size(); i++) { |
| 51 | m[pts[i]] = i; |
| 52 | } |
| 53 | for (int i = 0; i < 3; i++) { |
| 54 | for (int j = 0; j <= 3; j++) { |
| 55 | size_t v = m[Point(i, j)]; |
| 56 | size_t u = m[Point(i + 1, j)]; |
| 57 | assert(std::find(adj[v].begin(), adj[v].end(), u) != adj[v].end()); |
| 58 | assert(std::find(adj[u].begin(), adj[u].end(), v) != adj[u].end()); |
| 59 | } |
| 60 | } |
| 61 | for (int i = 0; i < 3; i++) { |
| 62 | for (int j = 0; j <= 3; j++) { |
| 63 | size_t v = m[Point(j, i)]; |
| 64 | size_t u = m[Point(j, i + 1)]; |
| 65 | assert(std::find(adj[v].begin(), adj[v].end(), u) != adj[v].end()); |
| 66 | assert(std::find(adj[u].begin(), adj[u].end(), v) != adj[u].end()); |
| 67 | } |
| 68 | } |
| 69 | } |
| 70 | |
| 71 | void test_multiedges() { |
| 72 | std::vector<Line> s = { |