Graph API Test Suite

Overview

A comprehensive unit test suite for a directed graph Abstract Data Type (ADT) implemented in C, written using the Check unit testing framework. The focus was on test design rather than the implementation itself — specifically, how to systematically cover a graph API without leaving dangerous gaps.

What's Being Tested

The graph ADT under test exposes:

• Construction/destruction — graph_create(), graph_destroy()
• Vertex operations — graph_add_vertex(), graph_remove_vertex(), graph_has_vertex()
• Edge operations — graph_add_edge(), graph_remove_edge(), graph_has_edge(), graph_edge_weight()
• Payload operations — graph_set_payload(), graph_get_payload()
• Queries — graph_vertex_count(), graph_edge_count(), graph_degree()
• Algorithms — graph_has_cycle(), graph_is_connected()

Test Design Philosophy

The interesting part of this project wasn't learning the Check API — it was thinking through what needs to be tested.

Equivalence partitioning. Each API function has a set of input classes that should behave identically within the class. For graph_add_edge(), the classes include: both vertices exist, source doesn't exist, destination doesn't exist, neither exists, and edge already exists. Testing one representative from each class is usually sufficient to expose class-level bugs.

Boundary conditions. For the cycle detection and connectivity algorithms, I identified the structurally interesting cases: empty graph, single-vertex graph, a graph with self-loops, a graph that's a simple path, a complete graph, and a disconnected graph. Each of these exercises different code paths.

State-dependent behavior. Some bugs only appear when operations are composed. Adding and removing the same edge twice should leave the graph in the same state as never adding it. Destroying a graph that was never populated should not crash. These "round-trip" tests catch bugs in state management that unit tests on individual operations miss.

Sample Test Structure

START_TEST(test_cycle_detection_no_cycle) {
    Graph *g = graph_create();
    graph_add_vertex(g, 1);
    graph_add_vertex(g, 2);
    graph_add_vertex(g, 3);
    graph_add_edge(g, 1, 2, 1.0);
    graph_add_edge(g, 2, 3, 1.0);
    ck_assert_int_eq(graph_has_cycle(g), 0);
    graph_destroy(g);
}
END_TEST

START_TEST(test_cycle_detection_simple_cycle) {
    Graph *g = graph_create();
    graph_add_vertex(g, 1);
    graph_add_vertex(g, 2);
    graph_add_vertex(g, 3);
    graph_add_edge(g, 1, 2, 1.0);
    graph_add_edge(g, 2, 3, 1.0);
    graph_add_edge(g, 3, 1, 1.0);  // closes the cycle
    ck_assert_int_eq(graph_has_cycle(g), 1);
    graph_destroy(g);
}
END_TEST

Coverage Summary

| Category | Tests | |---|---| | Graph creation and destruction | 8 | | Vertex add / remove / query | 14 | | Edge add / remove / query | 18 | | Payload get / set | 8 | | Degree queries | 10 | | Cycle detection | 12 | | Connectivity | 10 | | Total | 80 |

Build Integration

The test suite integrates with the project's Makefile:

test: $(TEST_OBJS)
    $(CC) $(CFLAGS) -o test_runner $(TEST_OBJS) -lcheck -lm -lpthread
    ./test_runner

valgrind-test: test
    valgrind --leak-check=full --error-exitcode=1 ./test_runner

make valgrind-test catches memory leaks in the ADT implementation — the test suite doubles as a memory safety check by exercising all code paths under Valgrind.

Lessons Learned

The most valuable insight was how test design reveals API design problems. Writing tests for graph_remove_vertex() exposed an underspecified behavior: what happens to edges incident to the removed vertex? The ADT's documentation was silent on this. Writing the test forced a decision — and surfaced it before it became a bug in production code.

Good test suites are as much a design tool as a verification tool.