graph/vs_to_es.hpp

View this file on GitHub
Last update: 2024-08-26 01:20:39+09:00
Include: #include "graph/vs_to_es.hpp"

Depends on

ds/hashmap.hpp

Required by

graph/eulerwalk.hpp

Verified with

Code

#pragma once

#include "ds/hashmap.hpp"

template <typename GT>
vc<int> vs_to_es(GT& G, vc<int>& vs, bool allow_use_twice = false) {
  assert(!vs.empty());

  HashMap<int> MP(G.M);
  vc<int> nxt(G.M, -1);

  auto get = [&](ll a, ll b) -> u64 {
    if (!GT::is_directed && a > b) swap(a, b);
    return a * G.N + b;
  };

  FOR(eid, G.M) {
    u64 k = get(G.edges[eid].frm, G.edges[eid].to);
    int x = MP.get(k, -1);
    nxt[eid] = x, MP[k] = eid;
  }
  int n = len(vs);
  vc<int> es(n - 1);
  FOR(i, n - 1) {
    u64 k = get(vs[i], vs[i + 1]);
    int eid = MP.get(k, -1);
    assert(eid != -1);
    es[i] = eid;
    if (!allow_use_twice) { MP[k] = nxt[eid]; }
  }
  return es;
}

#line 2 "graph/vs_to_es.hpp"

#line 2 "ds/hashmap.hpp"

// u64 -> Val

template <typename Val>
struct HashMap {
  // n は入れたいものの個数で ok

  HashMap(u32 n = 0) { build(n); }
  void build(u32 n) {
    u32 k = 8;
    while (k < n * 2) k *= 2;
    cap = k / 2, mask = k - 1;
    key.resize(k), val.resize(k), used.assign(k, 0);
  }

  // size を保ったまま. size=0 にするときは build すること.

  void clear() {
    used.assign(len(used), 0);
    cap = (mask + 1) / 2;
  }
  int size() { return len(used) / 2 - cap; }

  int index(const u64& k) {
    int i = 0;
    for (i = hash(k); used[i] && key[i] != k; i = (i + 1) & mask) {}
    return i;
  }

  Val& operator[](const u64& k) {
    if (cap == 0) extend();
    int i = index(k);
    if (!used[i]) { used[i] = 1, key[i] = k, val[i] = Val{}, --cap; }
    return val[i];
  }

  Val get(const u64& k, Val default_value) {
    int i = index(k);
    return (used[i] ? val[i] : default_value);
  }

  bool count(const u64& k) {
    int i = index(k);
    return used[i] && key[i] == k;
  }

  // f(key, val)

  template <typename F>
  void enumerate_all(F f) {
    FOR(i, len(used)) if (used[i]) f(key[i], val[i]);
  }

private:
  u32 cap, mask;
  vc<u64> key;
  vc<Val> val;
  vc<bool> used;

  u64 hash(u64 x) {
    static const u64 FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count();
    x += FIXED_RANDOM;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return (x ^ (x >> 31)) & mask;
  }

  void extend() {
    vc<pair<u64, Val>> dat;
    dat.reserve(len(used) / 2 - cap);
    FOR(i, len(used)) {
      if (used[i]) dat.eb(key[i], val[i]);
    }
    build(2 * len(dat));
    for (auto& [a, b]: dat) (*this)[a] = b;
  }
};
#line 4 "graph/vs_to_es.hpp"

template <typename GT>
vc<int> vs_to_es(GT& G, vc<int>& vs, bool allow_use_twice = false) {
  assert(!vs.empty());

  HashMap<int> MP(G.M);
  vc<int> nxt(G.M, -1);

  auto get = [&](ll a, ll b) -> u64 {
    if (!GT::is_directed && a > b) swap(a, b);
    return a * G.N + b;
  };

  FOR(eid, G.M) {
    u64 k = get(G.edges[eid].frm, G.edges[eid].to);
    int x = MP.get(k, -1);
    nxt[eid] = x, MP[k] = eid;
  }
  int n = len(vs);
  vc<int> es(n - 1);
  FOR(i, n - 1) {
    u64 k = get(vs[i], vs[i + 1]);
    int eid = MP.get(k, -1);
    assert(eid != -1);
    es[i] = eid;
    if (!allow_use_twice) { MP[k] = nxt[eid]; }
  }
  return es;
}