Lab_1/clique_tests.cpp at master · Dmi4er4/Lab_1 · 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
#include "clique.h"
#include "gtest/gtest.h"

TEST(Clique, Constructors) {
  const int kMaxN = 100;

  for (int n = 1; n <= kMaxN; n++) {
    Clique graph(n);
    ASSERT_EQ(graph.GetSize(), n);

    std::vector<std::vector<AbstractGraph::Edge>> new_graph;

    for (int i = 0; i < n; i++) {
      int pointer = 0;
      const std::vector<AbstractGraph::Edge>& edges = graph.GetEdges(i);
      new_graph.push_back(edges);

      for (int j = 0; j < n; j++) {
        if (i == j) {
          continue;
        }

        ASSERT_EQ(edges[pointer].to, j);
        ASSERT_EQ(edges[pointer].length, 1);
        pointer++;
      }
    }

    Clique graph_from_other_constructor(new_graph);

    for (int i = 0; i < n; i++) {
      int pointer = 0;
      const std::vector<AbstractGraph::Edge>& edges =
          graph_from_other_constructor.GetEdges(i);

      for (int j = 0; j < n; j++) {
        if (i == j) {
          continue;
        }

        ASSERT_EQ(edges[pointer].to, j);
        ASSERT_EQ(edges[pointer].length, 1);
        pointer++;
      }
    }
  }
}

TEST(Clique, GetPath) {
  const int kMaxN = 100;

  for (int n = 1; n <= kMaxN; n++) {
    Clique graph(n);
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++) {
        std::vector<AbstractGraph::Edge> any_path = graph.GetAnyPath(i, j);
        std::vector<AbstractGraph::Edge>
            shortest_path = graph.GetShortestPath(i, j);
        std::vector<AbstractGraph::Edge> for_check;
        if (i != j) {
          for_check.emplace_back(j, 1);
        }
        ASSERT_EQ(any_path.size(), for_check.size());
        ASSERT_EQ(shortest_path.size(), for_check.size());
        if (!for_check.empty()) {
          ASSERT_EQ(any_path[0].to, for_check[0].to);
          ASSERT_EQ(any_path[0].length, for_check[0].length);
          ASSERT_EQ(shortest_path[0].to, for_check[0].to);
          ASSERT_EQ(shortest_path[0].length, for_check[0].length);
        }
      }
  }
}

TEST(Clique, GetShortestPath) {
  std::vector<std::vector<AbstractGraph::Edge>> connections(3);
  connections[0].emplace_back(1, 3);
  connections[0].emplace_back(2, 1);
  connections[1].emplace_back(2, 1);
  connections[1].emplace_back(0, 1);
  connections[2].emplace_back(0, 1);
  connections[2].emplace_back(1, 1);
  Clique graph(connections);
  std::vector<AbstractGraph::Edge>
      shortest_path = graph.GetShortestPath(0, 1);
  ASSERT_EQ(shortest_path.size(), 2);
  ASSERT_EQ(shortest_path[0].to, 2);
  ASSERT_EQ(shortest_path[1].to, 1);
  ASSERT_EQ(shortest_path[0].length, 1);
  ASSERT_EQ(shortest_path[1].length, 1);
}