graph/treeHash.cpp

View this file on GitHub
Last update: 2024-04-05 19:44:35+08:00

Verified with

test/rooted_tree_isomorphism_classification.test.cpp

Code

template<bool ordered = false>
pair<int, vector<int>> treeHash(vector<vector<int>> &g, int root = 0) {
  int nxt = 0;
  static map<vector<int>, int> toId;
  vector<int> id(ssize(g));
  auto dfs = [&](int v, int p, auto self) -> int {
    vector<int> seq;
    seq.reserve(ssize(g[v]));
    for(int x : g[v]) if (x != p)
      seq.emplace_back(self(x, v, self));
    if constexpr (!ordered)
      ranges::sort(seq);
    if (!toId.contains(seq))
      toId[seq] = nxt++;
    return id[v] = toId[seq];
  };

  dfs(root, -1, dfs);

  return make_pair(nxt, id);
}

#line 1 "graph/treeHash.cpp"
template<bool ordered = false>
pair<int, vector<int>> treeHash(vector<vector<int>> &g, int root = 0) {
  int nxt = 0;
  static map<vector<int>, int> toId;
  vector<int> id(ssize(g));
  auto dfs = [&](int v, int p, auto self) -> int {
    vector<int> seq;
    seq.reserve(ssize(g[v]));
    for(int x : g[v]) if (x != p)
      seq.emplace_back(self(x, v, self));
    if constexpr (!ordered)
      ranges::sort(seq);
    if (!toId.contains(seq))
      toId[seq] = nxt++;
    return id[v] = toId[seq];
  };

  dfs(root, -1, dfs);

  return make_pair(nxt, id);
}