グラフ, 格子状のグラフ, 次元拡張グラフを同じコードで扱う抽象化BFS, DijkstraのC++14実装

Last updated Apr 27, 2020

Algorithm

これすごく悩んでいたんですけど, 新しい実装法を考えたらスッキリしたのでまとめます.

先駆者がいたらごめん, 勝手ににう式グラフ抽象化って言っちゃおうかな

# 意思

DijkstraやBFSのライブラリを書いておきたい！

# 問題点

同じアルゴリズムのライブラリを, 種類の違うグラフに対して一つずつ書くのは本当にイヤ
格子状のグラフをわざわざ, std::vector<std::vector<int>> Gに構築するのは定数倍があるのでイヤ.
問題を解くために次元拡張したグラフをわざわざ構築するのは, キレイじゃない
struct edgeがC++においてはなんかイヤ, 隣接する頂点がint toで固定しないとダメだったりでイヤ(Rustのtraitとかあるならまだしも個人差あり)
そもそもstruct edgeを毎回書くのもイヤ(競プロなので)
隣接リストを毎回std::vector<edge>で返すのもキレイじゃない, できるだけ無駄はなくしたい.

どうしよう(欲求が多すぎる)

# 解決

抽象化しにくいのはなぜかというと, struct edgeと隣接行列の保持の仕方がグラフの種類ごとに違うからです. なので, 方針としては

struct edgeは, ライブラリに触れさせない
隣接行列は, 直接ライブラリに触れさせない

という点を実現できれば良いです. ですが, 隣接行列をstd::vector<なんたら>で返す関数を返すのも美しくありません. なので, これを関数で受けることにします.

具体的には,

BFS関数は, deltaという隣接行列を生成する関数を受け取ります.
隣接する頂点を列挙する時は, deltaに, 現在の頂点$v$と, $v$と隣接する頂点を引数にとる, 探索をする関数を渡します.
deltaが隣接する頂点を, 引数で渡された関数の引数に入れて探索をしてもらいます.
できる!

Dijkstraの場合には, deltaに渡す関数を(V t /* 隣接頂点 */, W cost /* 辺のコスト */)にしておけばOKですね.

頂点の抽象化は, index(V) -> intがあればいいです.

# コード

# BFS

 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
#include <vector>
#include <queue>
using i64 = long long;

/*
 * delta(V v, fn (V t))
 * index(V v) -> int
 */
template<class V, class Delta, class Index>
std::vector<i64> bfs(std::size_t N, V s, Delta delta, Index index) {
  std::vector<i64> dist(N, -1);
  std::queue<V> que;
  dist[index(s)] = 0;
  que.push(s);
  while(!que.empty()) {
    V v = que.front();
    que.pop();
    delta(v, [&](V t) {
        if(dist[index(t)] == -1) {
          dist[index(t)] = dist[index(v)] + 1;
          que.push(t);
        }
    });
  }
  return dist;
}

# Dijkstra

 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
#include <vector>
#include <queue>

/*
 * delta(V v, fn (V t, W weight))
 * index(V v) -> int
 */
template<class V, class W, class Delta, class Index>
std::vector<W> dijkstra(std::size_t N, W inf, V s, Delta delta, Index index) {
  std::vector<W> dist(N, inf);
  using P = std::pair<W, V>;
  std::priority_queue<P, std::vector<P>, std::greater<P>> que;
  que.push({ dist[index(s)] = W(), s });
  while(!que.empty()) {
    W d = que.top().first;
    V v = que.top().second;
    que.pop();
    if(dist[index(v)] < d) continue;
    delta(v, [&](V t, W weight) {
        if(dist[index(t)] > dist[index(v)] + weight) {
          que.push({ dist[index(t)] = dist[index(v)] + weight, t });
        }
    });
  }
  return dist;
}

# How To Use

格子グラフに関しては, こんな感じに予めライブラリを書いておくと楽です.

 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
template<class F>
struct lattice_delta {
  i64 H, W;
  F f;
  using P = std::pair<i64, i64>;
  lattice_delta(i64 H, i64 W, F f): H(H), W(W), f(f) {}
  template<class Func>
  void operator()(P v, Func func) {
    const static vector<i64> dx { 1, 0, -1, 0 };
    i64 i = v.first;
    i64 j = v.second;
    for(i64 q = 0; q < 2; q++) {
      i64 x = i + dx[q];
      i64 y = j + dx[q ^ 1];
      if(0 <= x && x < H && 0 <= y && y < W) {
        f(P(i, j), P(x, y), func);
      }
    }
  }
};
 
template<class F>
lattice_delta<F> make_lattice_delta(i64 H, i64 W, F f) { return lattice_delta<F>(H, W, f); }
 
struct lattice_index {
  i64 H, W;
  using P = std::pair<i64, i64>;
  lattice_index(i64 H, i64 W): H(H), W(W) {}
  i64 operator()(P v) {
    return v.first * W + v.second;
  }
};

これで, Maze Masterは以下のように解くことができます.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main() {
  i64 H, W;
  cin >> H >> W;
  vector<string> S(H);
  rep(i,0,H) {
    cin >> S[i];
  }
  i64 ans = 0;

  using P = std::pair<i64, i64>;
  auto delta = make_lattice_delta(H, W, [&](P v, P t, auto func) {
    if(S[t.first][t.second] == '.') func(t);
    }
  );
  auto index = lattice_index(H, W);

  rep(i,0,H) rep(j,0,W) {
    if(S[i][j] == '#') continue;
    auto res = bfs(H * W, P(i, j), delta, index);
    ans = std::max(ans, *std::max_element(all(res)));
  }
  cout << ans << endl;
}

また, 次元拡張グラフを扱う E - Two Currenciesは, こんな感じで.

 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
int main() {
  i64 N, M, S;
  cin >> N >> M >> S;
  S = std::min(S, 2500ll);
 
  struct edge {
    i64 to;
    i64 a;
    i64 b;
  };
 
  vector<vector<edge>> G(N);
  rep(i,0,M) {
    i64 u, v, a, b;
    cin >> u >> v >> a >> b;
    u--;
    v--;
    G[u].push_back({ v, a, b });
    G[v].push_back({ u, a, b });
  }
 
  vector<i64> C(N);
  vector<i64> D(N);
  rep(i,0,N) {
    cin >> C[i] >> D[i];
  }
 
  using P = std::pair<i64, i64>;
  auto index = [&](P p) { return p.first * 2501 + p.second; };
  auto delta = [&](P vv, auto func) {
    i64 v = vv.first;
    i64 c = vv.second;
    func(P(v, std::min(c + C[v], 2500ll)), D[v]);
    for(auto e: G[v]) {
      if(e.a <= c) {
        func(P(e.to, c - e.a), e.b);
      }
    }
  };
  auto res = dijkstra(N * 2501, (i64)(1e17), P(0, S), delta, index);
  rep(i,1,N) {
    i64 ans = res[index(P(i, 0))];
    rep(j,0,2501) {
      ans = std::min(ans, res[index(P(i, j))]);
    }
    cout << ans << "\n";
  }
}

C++14ならジェネリックラムダあるので, auto funcって書き殴れるのでいいですね.

# 提出ページ

格子グラフのBFS: D - Maze Master - 提出 #11773027 - AtCoder Beginner Contest 151 ちょっとコード違うけど許して
格子グラフの01dial(01-bfs): A - Range Flip Find Route - 提出 #11773947 - AtCoder Grand Contest 043
次元拡張グラフのDijkstra: E - Two Currencies - 提出 #12401080 - AtCoder Beginner Contest 164