test_depth_first_traversal.cpp

Back to Depth-first traversal

test/pastel/sys/

// Description: Testing for depth-first traversal
// DocumentationOf: depth_first.h

#include "test/test_init.h"

#include "pastel/sys/graph/depth_first.h"

#include <vector>
#include <unordered_set>

TEST_CASE("traverseDepthFirst (traverseDepthFirst)")
{
    auto forEachSeedVertex = 
        [](const std::function<void(integer)>& visit)
    {
        visit(0);
    };

    auto forEachAdjacent =
        [](integer vertex, 
        const std::function<void(integer)>& visit)
    {
        if (vertex < 7)
        {
            visit(2 * vertex + 1);
            visit(2 * vertex + 2);
        }
    };

    std::unordered_set<integer> visitedSet;
    std::vector<integer> reportSet;

    auto mark = 
        [&](integer vertex)
    {
        visitedSet.insert(vertex);
        reportSet.push_back(vertex);
    };

    auto marked =
        [&](integer vertex) -> bool
    {
        return visitedSet.count(vertex);
    };

    traverseGraph<integer>(
        forEachSeedVertex,
        forEachAdjacent,
        mark,
        marked,
        DepthFirst_GraphTraversal());

    integer correctSet[] = {0, 1, 3, 7, 8, 4, 9, 10, 2, 5, 11, 12, 6, 13, 14};
    integer correctSize = std::end(correctSet) - std::begin(correctSet);

    REQUIRE(reportSet.size() == correctSize);

    if (reportSet.size() == correctSize)
    {
        REQUIRE(
            std::equal(std::begin(correctSet), std::end(correctSet),
            std::begin(reportSet)));
    }
}