I was recently working on a project where I needed to read graphs in the graph6 format (used, e.g., by nauty and plantri) and calculate some things on them. I wanted it to be fast, so I chose C++ and the Boost Graph Library for this task.

Either I don’t know how to search properly on the Internet, or there really isn’t a ready-made function to convert graph6 data into a Boost graph. Anyway, I present my implementation — for myself, so I don’t have to look for it if I ever want to use it, and for everyone else who doesn’t want to waste an hour of their time.

graph6 -> Boost
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

#include <boost/graph/adjacency_list.hpp>
#include <boost/range/iterator_range.hpp>

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>
    Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;

std::pair<int, std::vector<int>> data_to_n(const std::vector<int>& data) {
  if (data[0] <= 62) {
    return {data[0], std::vector(data.begin() + 1, data.end())};
  }

  if (data[1] <= 62) {
    int value = (data[1] << 12) + (data[2] << 6) + data[3];
    return {value, std::vector(data.begin() + 4, data.end())};
  }

  int value = (data[2] << 30) + (data[3] << 24) + (data[4] << 18) +
              (data[5] << 12) + (data[6] << 6) + data[7];

  return {value, std::vector(data.begin() + 8, data.end())};
}

Graph from_graph6_bytes(const std::string& bytes_in) {
  std::vector<int> data;
  for (const char c : bytes_in) {
    int val = static_cast<int>(c) - 63;
    if (val < 0 || val > 63) {
      throw std::invalid_argument(
          "Each input character must be in range(63, 127)");
    }
    data.push_back(val);
  }

  auto [n, remaining_data] = data_to_n(data);
  if (remaining_data.size() != (n * (n - 1) / 2 + 5) / 6) {
    throw std::runtime_error("Incorrect data length in graph6");
  }

  Graph G(n);
  int bit_index = 0;
  for (int j = 1; j < n; ++j) {
    for (int i = 0; i < j; ++i) {
      const int byte_index = bit_index / 6;
      const int bit_position = 5 - (bit_index % 6);
      if ((remaining_data[byte_index] >> bit_position) & 1) {
        boost::add_edge(i, j, G);
      }
      ++bit_index;
    }
  }
  return G;
}