Non-connected nodes problem

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <bit>
#include <bitset>

using uint8 = uint8_t;
using uint32 = uint32_t;

// Using switch instead of map
constexpr uint32 CHAR_TO_BIN_F(uint32 c) {
  switch(c) {
    case 'A': return 0b1;
    case 'B': return 0b10;
    case 'C': return 0b100;
    case 'D': return 0b1000;
    case 'E': return 0b10000;
    case 'F': return 0b100000;
    case 'G': return 0b1000000;
    case 'H': return 0b10000000;
    case 'I': return 0b100000000;
    case 'J': return 0b1000000000;
    case 'K': return 0b10000000000;
    case 'L': return 0b100000000000;
    case 'M': return 0b1000000000000;
    case 'N': return 0b10000000000000;
    case 'O': return 0b100000000000000;
    case 'P': return 0b1000000000000000;
    case 'Q': return 0b10000000000000000;
    case 'R': return 0b100000000000000000;
    case 'S': return 0b1000000000000000000;
    case 'T': return 0b10000000000000000000;
    case 'U': return 0b100000000000000000000;
    case 'V': return 0b1000000000000000000000;
    case 'W': return 0b10000000000000000000000;
    case 'X': return 0b100000000000000000000000;
    case 'Y': return 0b1000000000000000000000000;
    case 'Z': return 0b10000000000000000000000000;
  }
  return -1;
};

constexpr uint32 BIN_TO_CHAR_F(uint32 b) {
  switch(b) {
    case 0b1: return 'A';
    case 0b10: return 'B';
    case 0b100: return 'C';
    case 0b1000: return 'D';
    case 0b10000: return 'E';
    case 0b100000: return 'F';
    case 0b1000000: return 'G';
    case 0b10000000: return 'H';
    case 0b100000000: return 'I';
    case 0b1000000000: return 'J';
    case 0b10000000000: return 'K';
    case 0b100000000000: return 'L';
    case 0b1000000000000: return 'M';
    case 0b10000000000000: return 'N';
    case 0b100000000000000: return 'O';
    case 0b1000000000000000: return 'P';
    case 0b10000000000000000: return 'Q';
    case 0b100000000000000000: return 'R';
    case 0b1000000000000000000: return 'S';
    case 0b10000000000000000000: return 'T';
    case 0b100000000000000000000: return 'U';
    case 0b1000000000000000000000: return 'V';
    case 0b10000000000000000000000: return 'W';
    case 0b100000000000000000000000: return 'X';
    case 0b1000000000000000000000000: return 'Y';
    case 0b10000000000000000000000000: return 'Z';
  }
  return -1;
};

/*
std::vector<std::pair<uint32, uint32>> T = {
{'A', 'B'},
{'B', 'C'},
{'C', 'A'},
{'X', 'A'},
{'B', 'X'},
{'X', 'C'},
{'G', 'I'},
{'A', 'I'},
{'I', 'B'},
{'I', 'C'}
};
*/

static std::vector<std::pair<uint32, uint32>> T = {
    {'A', 'B'},
    {'B', 'C'},
    {'C', 'A'},
    {'X', 'A'},
    {'B', 'X'},
    {'X', 'C'},
    {'F', 'J'},
    {'E', 'J'},
    {'G', 'I'},
    {'F', 'E'},
    {'A', 'I'},
    {'I', 'F'},
    {'I', 'B'},
    {'I', 'C'},
    {'I', 'C'}
};


/*
Problem:
From the given undirected graph find the largest set of nodes that are not connected in any way.
For example, in the above set we can see that (A,J,F) is a possible solution because A is not connected to J or F and J is not connected to F.
If there is no bigger set, for example four nodes that are not connected in any way, then the set is a solution.
*/


// use unordered map instead of map
static std::unordered_map<uint32, uint32> SEEN;
static uint32 ALL = 0;

// This function basically goes through all combinations of the solutions of a set of nodes indicated by candidate_set
// We take in a character and a set of all characters it is not linked to.
// We also take in a candidate character from that set.
// We then try to go through the set and try out all solutions (combinations) that yield a solution
// We then finally store the solution
inline void CollectResults0(const uint32 main_char, std::pair<int, uint32>& results, const uint32 candidate_set, const uint32 candidate, decltype(SEEN)::const_iterator b_c) {
    // Take the input set and remove any nodes that the candidate itself is linked to as they cannot be in the solution
    // It becomes this candidate's own solution set
    const uint32 candidate_set_local = candidate_set & (candidate | ((~SEEN.at(candidate)) & ALL));

    // Here we loop through the remaining candidates in the new solution set and try remove each one's linked
    // We use iterator to continue from the previous candidate onwards only. This allows us to only test combinations, not permutations
    // we do not care about permutations (so A-B is same as B-A)
    bool last = true;
    for (; b_c != SEEN.end(); ++b_c) {
        // the way we store the data forces us to go through all characters even if they are not in the set
        // this check makes sure we only test characters that are in the set
        // a potential optimization is to figure out how to avoid going through all characters.
        if (candidate_set_local & b_c->first) {
            CollectResults0(main_char, results, candidate_set_local, b_c->first, std::next(b_c, 1));
            last = false;
        }
    }

    // If this candidate was the last one in this set, then it is the calcuated possible solution
    if (last) {
        const uint32 solution = main_char | candidate_set_local;
        // We need to check if it is better than existing solution
        const auto bits = std::popcount(solution);
        if (bits > results.first) {
          // was a better solution, store it
          results.first = bits;
          results.second = solution;
        }
    }
}

uint32 acual_main0() {
    // We go through the data set and collect all nodes we have seen into ALL set
    // We also collect all edges (connections) of a single character (node) into SEEN
    for (auto& p : T) { // loop over N
        const auto first_b = CHAR_TO_BIN_F(p.first);
        const auto second_b = CHAR_TO_BIN_F(p.second);
        SEEN[first_b] |= second_b;
        SEEN[second_b] |= first_b;
        ALL |= first_b | second_b;
    }
    /*
    // The final dataset might look like this when inversed. The inverse of connected nodes is non-connected nodes.
    // Below you can see a character and then a number (binary) that is the set of nodes it is NOT connected to.
    // In this printout we have also excluded the node itself from its own non-connections
    // and any characters that do not exist in the dataset are also removed.
    // The reason for these exclusions is that this data is what the CollectResults function will see and use
    A: 00000000000000000000001001110000
    B: 00000000000000000000001001110000
    C: 00000000000000000000001001110000
    E: 00000000100000000000000101000111
    F: 00000000100000000000000001000111
    G: 00000000100000000000001000110111
    I: 00000000100000000000001000010000
    J: 00000000100000000000000101000111
    X: 00000000000000000000001101110000
    */

    std::pair<int, uint32> results; // pair of <set size, the set itself>
    // In this loop we go through all of the rows of the dataset we collected
    // When we check the A row then we have checked all solutions that contain A.
    // This means that we can skip A from other rows. We store this information to already_checked_global for skipping.
    uint32 already_checked_global = 0;
    for (auto p = SEEN.begin(); p != SEEN.end(); ++p) {
        // inverse "connected" into "not connected" set.
        // Then make sure that we only consider nodes we have seen by using ALL.
        // Then remove "self" from the set.
        const uint32 candidate_set = (~p->second) & ALL & ~p->first;
        // When we check a specific bit on a row then we have checked all solutions that contain that bit.
        // This means that we can skip the bit from other rows. We store this information to already_checked for skipping.
        uint32 already_checked = already_checked_global;
        auto bits = std::popcount((candidate_set & ~already_checked) | p->first);
        if (results.first < bits) // skip solutions if  it cannot be better than already found
        {
            // In this loop we go through all of the set bits in a single row
            // In CollectResults we then try to exclude that bit's connections from the row and move to the next set bit recursively.
            // We try all combinations and when all bits of a row have been looped through we have a solution that contains
            // non-connected nodes.
            // Note that we start from the outer loop's current position to skip characters we have already went through in the outer loop. (see already_checked_global)
            for (auto b_c = p; b_c != SEEN.end(); ++b_c) {
                // the way we store the data forces us to go through all characters even if they are not in the set
                // this check makes sure we only test characters that are in the set
                // a potential optimization is to figure out how to avoid going through all characters.
                if (candidate_set & b_c->first) {
                    CollectResults0(p->first, results, (candidate_set & ~already_checked) | b_c->first, b_c->first, std::next(b_c, 1));
                    already_checked |= b_c->first;
                    if (results.first >= --bits)
                        break; // rest of the branches on this row cannot contain better results
                }
            }
        }
        already_checked_global |= p->first;
    }

    // It is possible to modify the algorithm to return all results. However, benchmarks showed that it may be best to collect all possible solutions first
    // and only once the algorithm has finished, find the best solutions just before returning right here.
    // Always benchmark when you make a change, collecting results into a map instead of a pair or a vector within CollectResults function doubled the execution time.
    return results.second;
}

static void TEST0(benchmark::State& state) {
  for (auto _ : state) {
    ALL = 0;
    SEEN.clear();

    benchmark::DoNotOptimize(acual_main0());
  }
}
BENCHMARK(TEST0);
// https://quick-bench.com/q/rkq-fXDE6Tq0V_oyNKzkEhTH908
// https://godbolt.org/z/WrTf9cjxT // Contains debug prints