How to test methods of heavy data structures using Google Test?

Question

Suppose we have the following class:

class Graph {
 public:

  Graph(int num_vertices, int num_edges, const EdgeList& edge_list)
    : num_vertices_(num_vertices), num_edges_(num_edges), edge_list_(edge_list) { }

  int GetNumberOfComponents() { ... }

 private:
  int num_vertices_;
  int num_edges_;
  EdgeList edge_list;
}

In the file gtest.cpp I have something like this:

#include "gtest/gtest.h"

TEST(Test, NumberOfComponentsTest) {
  Graph graph(4, 3, {{1, 2}, {2, 3}, {1, 3}});
  EXPECT_EQ(2, graph.GetNumberOfComponents());
}

int main(int argc, char **argv) {
  ::testing::InitGoogleTest(&argc, argv);
  return RUN_ALL_TESTS();
}

The goal is to check that GetNumberOfComponents() works correctly using Google Test framework.

But let's consider the large test case for example if num_vertices = 1000, number_edges = 100000. How to write such a test in this case if I don't want to hardcode all the edges ? ;)

Answer 1

The question actually hides two questions:

1. What am I really testing?
2. Assuming I decided I really need to test for 100K edges what is the best way to do it?

From my point of view and experience, the most important question is 1:

• Am I testing performance? Then yes, I need to test the 100K edge case (and measure time or other resources usage).
• Am I testing boundary conditions and I know that the implementation has conditional code around 100K edges? Then yes I need to test this case.
• Am I testing robustness or security and I have reasons to think I might be able to break the system under test with 100K edges? Then yes I need to test this case.
• On the other hand, if I am "just" testing correctness, why do I have the feeling that testing for, say, 10 edges is not enough to convince myself that the implementation will also work for 100K edges? I need to answer this question before continuing.

To make a comparison: say I am testing a function that returns the sum of a list of numbers. Say I have a test for lists of 0,1 and 5 elements. Why should I think that 5 elements is not a good-enough representative of the generic case?

What I am trying to say is that first one must really understand what one is testing and why, before jumping into the coding of the test.

For question 2, I think robert's answer is right, I can only paraphrase it. You need to write a as simple as possible helper function to generate the graph at run-time.

But looking at the code it looks like there are design problems of the Graph class that should be addressed before:

• Since the constructor requires the edge list, why is it also requiring the size of such list in parameter num_edges? The implementation can easily obtain the size of the list from the list itself.
• Also the fact of requiring the number of vertices is problematic, always for the same reason that it is receiving the edge list. The number of vertices should be calculated from the edge list, otherwise what happens if there is a contradiction between num_vertices and the number of vertices calculated from the edge list?

The fact that you are writing a test is very good, because the test is forcing you to question the design of Graph. Think about it and consider redesigning, using other, simpler tests to guide your design.