Bipartite Edge Coloring
(graph/bipartite_edge_coloring.hpp)

• View this file on GitHub
• Last update: 2024-01-08 14:54:00+09:00
• Include: #include "graph/bipartite_edge_coloring.hpp"

Description

二部グラフの辺彩色を求める．

Kőnig’s Line Coloring Theorem によると，二部グラフ $G$ の頂点の最大次数を $D$ とすると，$G$ は必ず $D$ 色で辺彩色可能である．

Operations

• vector<int> bipartite_edge_coloring(vector<pair<int, int>> G, int n, int m)
  • 頂点数が $(n, m)$ の二部グラフ $G$ の最小辺彩色における各辺の色を返す
  • 時間計算量: $O(E\sqrt{V} + E\log D)$

Note

計算量解析あってるかわからん．

正則二部グラフの完全マッチングを $O(E\log V)$ 時間で求めるアルゴリズムを用いれば，時間計算量を $O(E\log E)$ に改善できる．ただし，実測では普通に Hopcroft-Karp をやったほうが速かった．アルゴリズムについては，参考文献 (Twitter) を参照．

Reference

• 辺彩色 - slideshare
• 二部グラフの辺彩色 - ei1333の日記
• https://twitter.com/snuke_/status/1246630370415538176
• Noga Alon の二部グラフの辺彩色 - 37zigenのHP

Depends on

• Bipartite Matching (graph/bipartite_matching.hpp)

Verified with

• test/yosupo/bipartite_edge_coloring.test.cpp

Code

#pragma once
#include <algorithm>
#include <bit>
#include <map>
#include <stack>
#include <utility>
#include <vector>

#include "../graph/bipartite_matching.hpp"

std::vector<int> bipartite_edge_coloring(
    const std::vector<std::pair<int, int>>& edges, int n1, int n2) {
    const int E = edges.size();
    // find the maximum degree D
    std::vector<int> deg1(n1), deg2(n2);
    for (auto [a, b] : edges) {
        ++deg1[a], ++deg2[b];
    }
    const int D = std::max(*std::ranges::max_element(deg1),
                           *std::ranges::max_element(deg2));

    // convert to D-regular bipartite graph
    // merge vertices with the sum of degrees <= D
    auto contract = [&](const auto& deg) {
        const int n = deg.size();
        std::vector<std::pair<int, int>> vs(n);
        for (int i = 0; i < n; ++i) vs[i] = {deg[i], i};
        std::ranges::sort(vs);

        std::vector<int> id(n);
        std::vector<int> ndeg;

        int k = 0;
        for (int i = 0; i < n;) {
            int d = 0;
            int j = i;
            while (j < n && d + vs[j].first <= D) {
                d += vs[j].first;
                id[vs[j].second] = k;
                ++j;
            }
            ndeg.push_back(d);
            ++k;
            i = j;
        }

        return std::make_pair(id, ndeg);
    };

    auto [id1, ndeg1] = contract(deg1);
    auto [id2, ndeg2] = contract(deg2);

    using Edge = std::tuple<int, int, int>;
    std::vector<Edge> edges2;
    for (int i = 0; i < E; ++i) {
        auto [a, b] = edges[i];
        edges2.emplace_back(id1[a], id2[b], i);
    }

    // add dummy vertices
    const int n = std::max(ndeg1.size(), ndeg2.size());
    ndeg1.resize(n);
    ndeg2.resize(n);

    // add dummy edges
    int j = 0;
    int nE = E;
    for (int i = 0; i < n; ++i) {
        while (ndeg1[i] < D) {
            while (ndeg2[j] == D) ++j;
            edges2.emplace_back(i, j, nE++);
            ++ndeg1[i];
            ++ndeg2[j];
        }
    }

    // find the edge coloring
    std::vector<int> color(nE);
    int k = 0;

    auto rec = [&](auto& rec, const std::vector<Edge>& edges, int D) -> void {
        if (D == 1) {
            for (auto [a, b, i] : edges) {
                color[i] = k;
            }
            ++k;
            return;
        } else if (D % 2 == 0) {
            // find an eulerian walk for each connected component
            // partition the graph into two
            std::vector<std::vector<std::pair<int, int>>> G(2 * n);
            for (int j = 0; j < (int)edges.size(); ++j) {
                auto [a, b, i] = edges[j];
                G[a].emplace_back(n + b, j);
                G[n + b].emplace_back(a, j);
            }
            std::vector<bool> used_v(2 * n), used_e(edges.size());
            std::vector<std::vector<Edge>> edges2(2);

            for (int v = 0; v < n; ++v) {
                if (used_v[v]) continue;

                std::vector<int> walk;
                std::stack<std::pair<int, int>> st;
                st.emplace(v, -1);
                while (!st.empty()) {
                    auto [u, j] = st.top();
                    used_v[u] = true;
                    while (!G[u].empty() && used_e[G[u].back().second]) {
                        G[u].pop_back();
                    }
                    if (G[u].empty()) {
                        walk.push_back(j);
                        st.pop();
                    } else {
                        auto [v, k] = G[u].back();
                        G[u].pop_back();
                        used_e[k] = true;
                        st.emplace(v, k);
                    }
                }

                for (int i = 0; i < (int)walk.size() - 1; ++i) {
                    edges2[i % 2].push_back(edges[walk[i]]);
                }
            }
            rec(rec, edges2[0], D / 2);

            int nD = std::bit_ceil((unsigned int)(D / 2));

            // add nD-D/2 edges from edges2[0] to edges2[1]
            for (auto [a, b, i] : edges2[0]) {
                if (color[i] >= k - (nD - D / 2)) {
                    edges2[1].emplace_back(a, b, i);
                }
            }
            k -= nD - D / 2;

            rec(rec, edges2[1], nD);
        } else {
            // paint the edges in a perfect matching with the same color
            BipartiteMatching bm(n, n);
            for (auto [a, b, i] : edges) {
                bm.add_edge(a, b);
            }
            std::vector<int> match(n, -1);
            for (auto [a, b] : bm.max_matching()) {
                match[a] = b;
            }
            std::vector<Edge> edges2;
            for (auto [a, b, i] : edges) {
                if (match[a] == b) {
                    color[i] = k;
                    match[a] = -1;
                } else {
                    edges2.emplace_back(a, b, i);
                }
            }
            ++k;
            rec(rec, edges2, D - 1);
        }
    };

    rec(rec, edges2, D);
    color.resize(E);
    return color;
}

std::vector<std::pair<int, int>> regular_bipartite_matching(
    const std::vector<std::pair<int, int>>& edges, int D) {
    const int n = edges.size() / D;

    auto rec = [&](auto& rec, const auto& edges, int D) {
        if (D == 1) {
            return edges;
        } else if (D % 2 == 0) {
            // find an eulerian walk for each connected component
            // partition the graph into two
            std::vector<std::vector<std::pair<int, int>>> G(2 * n);
            for (int j = 0; j < (int)edges.size(); ++j) {
                auto [a, b, d] = edges[j];
                G[a].emplace_back(n + b, j);
                G[n + b].emplace_back(a, j);
            }
            std::vector<bool> used_v(2 * n), used_e(edges.size());
            std::vector<std::vector<std::tuple<int, int, bool>>> edges2(2);
            std::vector<int> dummy_cnt(2);

            for (int v = 0; v < n; ++v) {
                if (used_v[v]) continue;

                std::vector<int> walk;
                std::stack<std::pair<int, int>> st;
                st.emplace(v, -1);
                while (!st.empty()) {
                    auto [u, j] = st.top();
                    used_v[u] = true;
                    while (!G[u].empty() && used_e[G[u].back().second]) {
                        G[u].pop_back();
                    }
                    if (G[u].empty()) {
                        walk.push_back(j);
                        st.pop();
                    } else {
                        auto [v, k] = G[u].back();
                        G[u].pop_back();
                        used_e[k] = true;
                        st.emplace(v, k);
                    }
                }

                for (int i = 0; i < (int)walk.size() - 1; ++i) {
                    edges2[i % 2].push_back(edges[walk[i]]);
                    dummy_cnt[i % 2] += std::get<2>(edges[walk[i]]);
                }
            }
            return rec(rec, dummy_cnt[0] < dummy_cnt[1] ? edges2[0] : edges2[1],
                       D / 2);
        } else {
            int size = std::bit_ceil((unsigned int)D);

            // add size-D dummy edges
            auto edges2 = edges;
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < size - D; ++j) {
                    edges2.emplace_back(i, i, true);
                }
            }

            while (true) {
                auto res = rec(rec, edges2, size);
                int cnt = 0;
                for (auto [a, b, d] : res) {
                    cnt += d;
                }
                if (cnt == 0) return res;
                // add res size-D times
                edges2 = edges;
                for (auto [a, b, d] : res) {
                    for (int j = 0; j < size - D; ++j) {
                        edges2.emplace_back(a, b, d);
                    }
                }
            }
        }
    };

    std::vector<std::tuple<int, int, bool>> edges2;
    for (auto [a, b] : edges) {
        edges2.emplace_back(a, b, false);
    }
    auto res = rec(rec, edges2, D);
    std::vector<std::pair<int, int>> ret;
    for (auto [a, b, d] : res) {
        ret.emplace_back(a, b);
    }
    return ret;
}

#line 2 "graph/bipartite_edge_coloring.hpp"
#include <algorithm>
#include <bit>
#include <map>
#include <stack>
#include <utility>
#include <vector>

#line 3 "graph/bipartite_matching.hpp"
#include <limits>
#include <queue>
#line 7 "graph/bipartite_matching.hpp"

class BipartiteMatching {
   public:
    BipartiteMatching() = default;
    BipartiteMatching(int U, int V)
        : U(U),
          V(V),
          NIL(U + V),
          G(U),
          level(U + V + 1),
          match(U + V + 1, NIL) {}

    void add_edge(int u, int v) { G[u].emplace_back(U + v); }

    std::vector<std::pair<int, int>> max_matching() {
        while (bfs()) {
            for (int u = 0; u < U; ++u) {
                if (match[u] == NIL) {
                    dfs(u);
                }
            }
        }
        std::vector<std::pair<int, int>> ret;
        for (int u = 0; u < U; ++u) {
            if (match[u] != NIL) ret.emplace_back(u, match[u] - U);
        }
        return ret;
    }

   private:
    static constexpr int INF = std::numeric_limits<int>::max() / 2;

    const int U, V, NIL;
    std::vector<std::vector<int>> G;
    std::vector<int> level, match;

    bool bfs() {
        std::ranges::fill(level, INF);
        std::queue<int> q;
        for (int u = 0; u < U; ++u) {
            if (match[u] == NIL) {
                level[u] = 0;
                q.push(u);
            }
        }
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            if (level[u] < level[NIL]) {
                for (int v : G[u]) {
                    if (level[match[v]] == INF) {
                        level[match[v]] = level[u] + 1;
                        q.push(match[v]);
                    }
                }
            }
        }
        return level[NIL] != INF;
    }

    bool dfs(int u) {
        if (u == NIL) return true;
        for (int v : G[u]) {
            if (level[match[v]] == level[u] + 1 && dfs(match[v])) {
                match[v] = u;
                match[u] = v;
                return true;
            }
        }
        level[u] = INF;
        return false;
    }
};

/*
 * Bipartite matching using Ford-Fulkerson algorithm
 * Time complexity: O(VE)
 */
class BipartiteMatchingFF {
   public:
    BipartiteMatchingFF() = default;
    explicit BipartiteMatchingFF(int n) : G(n), used(n), match(n) {}

    void add_edge(int u, int v) {
        G[u].push_back(v);
        G[v].push_back(u);
    }

    std::vector<std::pair<int, int>> max_matching() {
        int res = 0;
        std::ranges::fill(match, -1);
        for (int v = 0; v < (int)G.size(); ++v) {
            if (match[v] == -1) {
                std::fill(used.begin(), used.end(), false);
                if (dfs(v)) ++res;
            }
        }

        std::vector<std::pair<int, int>> ret;
        for (int i = 0; i < (int)G.size(); ++i) {
            if (i < match[i]) ret.emplace_back(i, match[i]);
        }
        return ret;
    }

   private:
    std::vector<std::vector<int>> G;
    std::vector<bool> used;
    std::vector<int> match;

    bool dfs(int u) {
        used[u] = true;
        for (int v : G[u]) {
            int w = match[v];
            if (w == -1 || (!used[w] && dfs(w))) {
                match[u] = v;
                match[v] = u;
                return true;
            }
        }
        return false;
    }
};
#line 10 "graph/bipartite_edge_coloring.hpp"

std::vector<int> bipartite_edge_coloring(
    const std::vector<std::pair<int, int>>& edges, int n1, int n2) {
    const int E = edges.size();
    // find the maximum degree D
    std::vector<int> deg1(n1), deg2(n2);
    for (auto [a, b] : edges) {
        ++deg1[a], ++deg2[b];
    }
    const int D = std::max(*std::ranges::max_element(deg1),
                           *std::ranges::max_element(deg2));

    // convert to D-regular bipartite graph
    // merge vertices with the sum of degrees <= D
    auto contract = [&](const auto& deg) {
        const int n = deg.size();
        std::vector<std::pair<int, int>> vs(n);
        for (int i = 0; i < n; ++i) vs[i] = {deg[i], i};
        std::ranges::sort(vs);

        std::vector<int> id(n);
        std::vector<int> ndeg;

        int k = 0;
        for (int i = 0; i < n;) {
            int d = 0;
            int j = i;
            while (j < n && d + vs[j].first <= D) {
                d += vs[j].first;
                id[vs[j].second] = k;
                ++j;
            }
            ndeg.push_back(d);
            ++k;
            i = j;
        }

        return std::make_pair(id, ndeg);
    };

    auto [id1, ndeg1] = contract(deg1);
    auto [id2, ndeg2] = contract(deg2);

    using Edge = std::tuple<int, int, int>;
    std::vector<Edge> edges2;
    for (int i = 0; i < E; ++i) {
        auto [a, b] = edges[i];
        edges2.emplace_back(id1[a], id2[b], i);
    }

    // add dummy vertices
    const int n = std::max(ndeg1.size(), ndeg2.size());
    ndeg1.resize(n);
    ndeg2.resize(n);

    // add dummy edges
    int j = 0;
    int nE = E;
    for (int i = 0; i < n; ++i) {
        while (ndeg1[i] < D) {
            while (ndeg2[j] == D) ++j;
            edges2.emplace_back(i, j, nE++);
            ++ndeg1[i];
            ++ndeg2[j];
        }
    }

    // find the edge coloring
    std::vector<int> color(nE);
    int k = 0;

    auto rec = [&](auto& rec, const std::vector<Edge>& edges, int D) -> void {
        if (D == 1) {
            for (auto [a, b, i] : edges) {
                color[i] = k;
            }
            ++k;
            return;
        } else if (D % 2 == 0) {
            // find an eulerian walk for each connected component
            // partition the graph into two
            std::vector<std::vector<std::pair<int, int>>> G(2 * n);
            for (int j = 0; j < (int)edges.size(); ++j) {
                auto [a, b, i] = edges[j];
                G[a].emplace_back(n + b, j);
                G[n + b].emplace_back(a, j);
            }
            std::vector<bool> used_v(2 * n), used_e(edges.size());
            std::vector<std::vector<Edge>> edges2(2);

            for (int v = 0; v < n; ++v) {
                if (used_v[v]) continue;

                std::vector<int> walk;
                std::stack<std::pair<int, int>> st;
                st.emplace(v, -1);
                while (!st.empty()) {
                    auto [u, j] = st.top();
                    used_v[u] = true;
                    while (!G[u].empty() && used_e[G[u].back().second]) {
                        G[u].pop_back();
                    }
                    if (G[u].empty()) {
                        walk.push_back(j);
                        st.pop();
                    } else {
                        auto [v, k] = G[u].back();
                        G[u].pop_back();
                        used_e[k] = true;
                        st.emplace(v, k);
                    }
                }

                for (int i = 0; i < (int)walk.size() - 1; ++i) {
                    edges2[i % 2].push_back(edges[walk[i]]);
                }
            }
            rec(rec, edges2[0], D / 2);

            int nD = std::bit_ceil((unsigned int)(D / 2));

            // add nD-D/2 edges from edges2[0] to edges2[1]
            for (auto [a, b, i] : edges2[0]) {
                if (color[i] >= k - (nD - D / 2)) {
                    edges2[1].emplace_back(a, b, i);
                }
            }
            k -= nD - D / 2;

            rec(rec, edges2[1], nD);
        } else {
            // paint the edges in a perfect matching with the same color
            BipartiteMatching bm(n, n);
            for (auto [a, b, i] : edges) {
                bm.add_edge(a, b);
            }
            std::vector<int> match(n, -1);
            for (auto [a, b] : bm.max_matching()) {
                match[a] = b;
            }
            std::vector<Edge> edges2;
            for (auto [a, b, i] : edges) {
                if (match[a] == b) {
                    color[i] = k;
                    match[a] = -1;
                } else {
                    edges2.emplace_back(a, b, i);
                }
            }
            ++k;
            rec(rec, edges2, D - 1);
        }
    };

    rec(rec, edges2, D);
    color.resize(E);
    return color;
}

std::vector<std::pair<int, int>> regular_bipartite_matching(
    const std::vector<std::pair<int, int>>& edges, int D) {
    const int n = edges.size() / D;

    auto rec = [&](auto& rec, const auto& edges, int D) {
        if (D == 1) {
            return edges;
        } else if (D % 2 == 0) {
            // find an eulerian walk for each connected component
            // partition the graph into two
            std::vector<std::vector<std::pair<int, int>>> G(2 * n);
            for (int j = 0; j < (int)edges.size(); ++j) {
                auto [a, b, d] = edges[j];
                G[a].emplace_back(n + b, j);
                G[n + b].emplace_back(a, j);
            }
            std::vector<bool> used_v(2 * n), used_e(edges.size());
            std::vector<std::vector<std::tuple<int, int, bool>>> edges2(2);
            std::vector<int> dummy_cnt(2);

            for (int v = 0; v < n; ++v) {
                if (used_v[v]) continue;

                std::vector<int> walk;
                std::stack<std::pair<int, int>> st;
                st.emplace(v, -1);
                while (!st.empty()) {
                    auto [u, j] = st.top();
                    used_v[u] = true;
                    while (!G[u].empty() && used_e[G[u].back().second]) {
                        G[u].pop_back();
                    }
                    if (G[u].empty()) {
                        walk.push_back(j);
                        st.pop();
                    } else {
                        auto [v, k] = G[u].back();
                        G[u].pop_back();
                        used_e[k] = true;
                        st.emplace(v, k);
                    }
                }

                for (int i = 0; i < (int)walk.size() - 1; ++i) {
                    edges2[i % 2].push_back(edges[walk[i]]);
                    dummy_cnt[i % 2] += std::get<2>(edges[walk[i]]);
                }
            }
            return rec(rec, dummy_cnt[0] < dummy_cnt[1] ? edges2[0] : edges2[1],
                       D / 2);
        } else {
            int size = std::bit_ceil((unsigned int)D);

            // add size-D dummy edges
            auto edges2 = edges;
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < size - D; ++j) {
                    edges2.emplace_back(i, i, true);
                }
            }

            while (true) {
                auto res = rec(rec, edges2, size);
                int cnt = 0;
                for (auto [a, b, d] : res) {
                    cnt += d;
                }
                if (cnt == 0) return res;
                // add res size-D times
                edges2 = edges;
                for (auto [a, b, d] : res) {
                    for (int j = 0; j < size - D; ++j) {
                        edges2.emplace_back(a, b, d);
                    }
                }
            }
        }
    };

    std::vector<std::tuple<int, int, bool>> edges2;
    for (auto [a, b] : edges) {
        edges2.emplace_back(a, b, false);
    }
    auto res = rec(rec, edges2, D);
    std::vector<std::pair<int, int>> ret;
    for (auto [a, b, d] : res) {
        ret.emplace_back(a, b);
    }
    return ret;
}

Back to top page