Performance Measurements with Valgrind:

@angriman, @fabratu
To assess performance implications, I created the following benchmark program:

#include "networkit/graph/Graph.hpp"
#include "networkit/distance/FloydWarshall.hpp"
#include <valgrind/callgrind.h>

NetworKit::Graph get_graph()
{
    NetworKit::Graph graph({{0, 2, 4}, {0, 3, 4}, {0, 4, 2}, {0, 5, 2}, {0, 6, 1}, {0, 7, 14}, ...
    });
    return graph;
}

int main()
{
    auto graph = get_graph();
    NetworKit::FloydWarshall test(graph);
    test.run();
    int negative{};
    int positive{};
    for(NetworKit::node node{}; node < graph.numberOfNodes(); node++)
    {
        bool inNegCycle = test.isNodeInNegativeCycle(node);
        if (inNegCycle)
            negative++;
        else
            positive++;
    }
    std::cout << negative << std::endl;
    std::cout << positive << std::endl;
    return negative;
}

where get_graph provides a graph with 50 nodes and about 1000 edges.
I build networkit using this config:
cmake -DNETWORKIT_BUILD_TESTS=OFF -DCMAKE_BUILD_TYPE=RelWithDebInfo -GNinja ..
and my sample program:
cmake -DCMAKE_BUILD_TYPE=RelWithDebInfo -G Ninja ..
using gcc-11.4.
I executed the program with Valgrind-3.18.1 using Callgrind:
valgrind --tool=callgrind floyd_warshall
which results in:
4,444,940,581 Dynamic Instructions
I repeated the measurement to obtain an approximate estimate of the intrinsic measurement noise
4,507,148,633 Dynamic Instructions
I expect this noise due to the use of OpenMP.

Next I changed the std::vector<bool> nodesInNegativeCycle; in the class FloydWarshall to std::vector<uint8_t> nodesInNegativeCycle;, reran the measurements and observed:
4,470,597,816 Dynamic Instructions
the second measurement resulted in
4,489,718,891 Dynamic Instructions

From these observations, I conclude that the performance difference between std::vector<bool> and std::vector<uint8_t> for this specific use case is negligible, and any minor differences observed fall within the intrinsic measurement noise.

Comparison of std::vector<bool> and std::vector<uint8_t>

To gain insight specifically into the overhead of accessing std::vector<bool>, I used Callgrind instrumentation macros around only the node-checking loop:

CALLGRIND_START_INSTRUMENTATION;
for(NetworKit::node node{}; node < graph.numberOfNodes(); node++)
{
    bool inNegCycle = test.isNodeInNegativeCycle(node);
    if (inNegCycle)
        negative++;
    else
        positive++;
}
CALLGRIND_STOP_INSTRUMENTATION;

and called valgrind using an additional option:
valgrind --tool=callgrind --instr-atstart=no ./cmake-build-debug/floyd_warshall
For the std::vector<bool> case I found:
1,608 Dynamic Instructions
and this result is reproducible (since no OpenMP calls are involved in the loop).
When using the macros with std::vector<uint8_t> and just measure the loop I found:
908 Dynamic Instructions
This targeted measurement reveals an approximate 40% instruction-count reduction when using std::vector<uint8_t>.
For loops executed frequently, such optimization could be significant.

I hope I haven't overlooked anything or made any mistakes. Please feel free to comment.

Thanks for doing the benchmarks. This seems to back the assumption, that in the case at hand, there is no significant difference in performance.

Thanks a lot for setting up those benchmarks and sharing the results. For this particular application, it looks that using std::vector<uint8_t> does not bring noticeable performance improvements, so I'd recommend to use std::vector<bool>.