bipartite_edge_coloring.hpp¶
Color every edge of a bipartite multigraph with Delta colors so incident edges differ. Low-degree vertices are contracted before regularization, keeping the number of real and dummy edges linear.
Verified by bipartite_edge_coloring.
用最大度种颜色给二分多重图的边染色，使相邻边颜色不同。
Implementation¶
#ifndef NOYA_BIPARTITE_EDGE_COLORING_HPP
#define NOYA_BIPARTITE_EDGE_COLORING_HPP 1
/// @complexity Time: O(E sqrt(V) log Delta) with Euler splitting and sparse
/// perfect matchings; Space: O(V + E).
#include <algorithm>
#include <cassert>
#include <functional>
#include <numeric>
#include <queue>
#include <utility>
#include <vector>
namespace noya {
namespace bipartite_edge_coloring_internal {
struct dsu {
std::vector<int> parent;
explicit dsu(int size) : parent(size, -1) {}
int leader(int vertex) {
if (parent[vertex] < 0) {
return vertex;
}
return parent[vertex] = leader(parent[vertex]);
}
int merge(int first, int second) {
first = leader(first);
second = leader(second);
if (first == second) {
return first;
}
if (parent[first] > parent[second]) {
std::swap(first, second);
}
parent[first] += parent[second];
parent[second] = first;
return first;
}
};
inline std::pair<std::vector<int>, int>
contract_vertices(const std::vector<int> °ree, int maximum_degree) {
const int size = int(degree.size());
dsu components(size);
std::priority_queue<std::pair<int, int>> queue;
for (int vertex = 0; vertex < size; vertex++) {
queue.emplace(-degree[vertex], vertex);
}
while (queue.size() > 1) {
auto [negative_first, first] = queue.top();
queue.pop();
auto [negative_second, second] = queue.top();
queue.pop();
if (-negative_first - negative_second > maximum_degree) {
break;
}
int root = components.merge(first, second);
queue.emplace(negative_first + negative_second, root);
}
std::vector<int> root_id(size, -1);
std::vector<int> result(size);
int count = 0;
for (int vertex = 0; vertex < size; vertex++) {
int root = components.leader(vertex);
if (root_id[root] == -1) {
root_id[root] = count++;
}
result[vertex] = root_id[root];
}
return {result, count};
}
struct edge_record {
int left;
int right;
int original_id;
};
inline std::vector<int>
perfect_matching(int size, const std::vector<edge_record> &all_edges,
const std::vector<int> &edge_ids) {
std::vector<std::vector<int>> adjacency(size);
for (int id : edge_ids) {
adjacency[all_edges[id].left].push_back(id);
}
std::vector<int> match_left(size, -1);
std::vector<int> match_right(size, -1);
std::vector<int> distance(size);
std::vector<int> cursor(size);
while (true) {
std::queue<int> queue;
std::fill(distance.begin(), distance.end(), -1);
std::fill(cursor.begin(), cursor.end(), 0);
for (int left = 0; left < size; left++) {
if (match_left[left] == -1) {
distance[left] = 0;
queue.push(left);
}
}
while (!queue.empty()) {
int left = queue.front();
queue.pop();
for (int id : adjacency[left]) {
int next_id = match_right[all_edges[id].right];
if (next_id == -1) {
continue;
}
int next_left = all_edges[next_id].left;
if (distance[next_left] == -1) {
distance[next_left] = distance[left] + 1;
queue.push(next_left);
}
}
}
std::function<bool(int)> augment = [&](int left) {
for (int &index = cursor[left]; index < int(adjacency[left].size());
index++) {
int id = adjacency[left][index];
int right = all_edges[id].right;
int next_id = match_right[right];
if (next_id == -1 ||
(distance[all_edges[next_id].left] == distance[left] + 1 &&
augment(all_edges[next_id].left))) {
match_left[left] = id;
match_right[right] = id;
return true;
}
}
distance[left] = -1;
return false;
};
int augmented = 0;
for (int left = 0; left < size; left++) {
if (match_left[left] == -1) {
augmented += augment(left);
}
}
if (augmented == 0) {
break;
}
}
for (int id : match_left) {
assert(id != -1);
}
return match_left;
}
inline std::pair<std::vector<int>, std::vector<int>>
split_even_regular(int size, const std::vector<edge_record> &all_edges,
const std::vector<int> &edge_ids) {
std::vector<std::vector<int>> adjacency(2 * size);
for (int id : edge_ids) {
adjacency[all_edges[id].left].push_back(id);
adjacency[size + all_edges[id].right].push_back(id);
}
std::vector<int> cursor(2 * size);
std::vector<bool> used(all_edges.size());
std::vector<int> first;
std::vector<int> second;
first.reserve(edge_ids.size() / 2);
second.reserve(edge_ids.size() / 2);
for (int start = 0; start < 2 * size; start++) {
while (cursor[start] < int(adjacency[start].size()) &&
used[adjacency[start][cursor[start]]]) {
cursor[start]++;
}
if (cursor[start] == int(adjacency[start].size())) {
continue;
}
std::vector<int> vertex_stack{start};
std::vector<int> edge_stack;
std::vector<int> circuit;
while (!vertex_stack.empty()) {
int vertex = vertex_stack.back();
while (cursor[vertex] < int(adjacency[vertex].size()) &&
used[adjacency[vertex][cursor[vertex]]]) {
cursor[vertex]++;
}
if (cursor[vertex] == int(adjacency[vertex].size())) {
vertex_stack.pop_back();
if (!edge_stack.empty()) {
circuit.push_back(edge_stack.back());
edge_stack.pop_back();
}
continue;
}
int id = adjacency[vertex][cursor[vertex]++];
if (used[id]) {
continue;
}
used[id] = true;
int next = vertex < size ? size + all_edges[id].right
: all_edges[id].left;
vertex_stack.push_back(next);
edge_stack.push_back(id);
}
assert(circuit.size() % 2 == 0);
for (int index = 0; index < int(circuit.size()); index++) {
(index & 1 ? second : first).push_back(circuit[index]);
}
}
assert(first.size() == edge_ids.size() / 2);
assert(second.size() == edge_ids.size() / 2);
return {std::move(first), std::move(second)};
}
inline void color_regular(int size, const std::vector<edge_record> &all_edges,
std::vector<int> edge_ids, int degree, int offset,
std::vector<int> &result) {
if (degree == 0) {
assert(edge_ids.empty());
return;
}
assert(edge_ids.size() == std::size_t(size) * degree);
if (degree == 1) {
for (int id : edge_ids) {
if (all_edges[id].original_id != -1) {
result[all_edges[id].original_id] = offset;
}
}
return;
}
if (degree % 2 == 0) {
auto [first, second] = split_even_regular(size, all_edges, edge_ids);
color_regular(size, all_edges, std::move(first), degree / 2, offset,
result);
color_regular(size, all_edges, std::move(second), degree / 2,
offset + degree / 2, result);
return;
}
std::vector<int> matching = perfect_matching(size, all_edges, edge_ids);
std::vector<bool> selected(all_edges.size());
for (int id : matching) {
selected[id] = true;
if (all_edges[id].original_id != -1) {
result[all_edges[id].original_id] = offset;
}
}
std::vector<int> remaining;
remaining.reserve(edge_ids.size() - size);
for (int id : edge_ids) {
if (!selected[id]) {
remaining.push_back(id);
}
}
color_regular(size, all_edges, std::move(remaining), degree - 1,
offset + 1, result);
}
} // namespace bipartite_edge_coloring_internal
/// @brief Color every edge of a bipartite multigraph with Delta colors so
/// incident edges differ. Low-degree vertices are contracted before
/// regularization, keeping the number of real and dummy edges linear.
inline std::vector<int>
bipartite_edge_coloring(int left_size, int right_size,
const std::vector<std::pair<int, int>> &edges) {
using namespace bipartite_edge_coloring_internal;
assert(left_size >= 0 && right_size >= 0);
std::vector<int> left_degree(left_size);
std::vector<int> right_degree(right_size);
int maximum_degree = 0;
for (auto [left, right] : edges) {
assert(0 <= left && left < left_size);
assert(0 <= right && right < right_size);
maximum_degree = std::max(maximum_degree, ++left_degree[left]);
maximum_degree = std::max(maximum_degree, ++right_degree[right]);
}
if (edges.empty()) {
return {};
}
auto [left_id, left_count] =
contract_vertices(left_degree, maximum_degree);
auto [right_id, right_count] =
contract_vertices(right_degree, maximum_degree);
int size = std::max(left_count, right_count);
std::vector<int> contracted_left_degree(size);
std::vector<int> contracted_right_degree(size);
std::vector<edge_record> all_edges;
all_edges.reserve(edges.size() * 2);
for (int id = 0; id < int(edges.size()); id++) {
int left = left_id[edges[id].first];
int right = right_id[edges[id].second];
all_edges.push_back({left, right, id});
contracted_left_degree[left]++;
contracted_right_degree[right]++;
}
int left = 0;
int right = 0;
while (left < size && right < size) {
while (left < size && contracted_left_degree[left] == maximum_degree) {
left++;
}
while (right < size && contracted_right_degree[right] == maximum_degree) {
right++;
}
if (left == size || right == size) {
break;
}
int count = std::min(maximum_degree - contracted_left_degree[left],
maximum_degree - contracted_right_degree[right]);
for (int index = 0; index < count; index++) {
all_edges.push_back({left, right, -1});
}
contracted_left_degree[left] += count;
contracted_right_degree[right] += count;
}
assert(std::all_of(contracted_left_degree.begin(),
contracted_left_degree.end(),
[&](int degree) { return degree == maximum_degree; }));
assert(std::all_of(contracted_right_degree.begin(),
contracted_right_degree.end(),
[&](int degree) { return degree == maximum_degree; }));
std::vector<int> edge_ids(all_edges.size());
std::iota(edge_ids.begin(), edge_ids.end(), 0);
std::vector<int> result(edges.size(), -1);
color_regular(size, all_edges, std::move(edge_ids), maximum_degree, 0,
result);
for (int color : result) {
assert(0 <= color && color < maximum_degree);
}
return result;
}
} // namespace noya
#endif // NOYA_BIPARTITE_EDGE_COLORING_HPP
#include <algorithm>
#include <cassert>
#include <functional>
#include <numeric>
#include <queue>
#include <utility>
#include <vector>
/// @complexity Time: O(E sqrt(V) log Delta) with Euler splitting and sparse
/// perfect matchings; Space: O(V + E).
namespace noya {
namespace bipartite_edge_coloring_internal {
struct dsu {
std::vector<int> parent;
explicit dsu(int size) : parent(size, -1) {}
int leader(int vertex) {
if (parent[vertex] < 0) {
return vertex;
}
return parent[vertex] = leader(parent[vertex]);
}
int merge(int first, int second) {
first = leader(first);
second = leader(second);
if (first == second) {
return first;
}
if (parent[first] > parent[second]) {
std::swap(first, second);
}
parent[first] += parent[second];
parent[second] = first;
return first;
}
};
inline std::pair<std::vector<int>, int>
contract_vertices(const std::vector<int> °ree, int maximum_degree) {
const int size = int(degree.size());
dsu components(size);
std::priority_queue<std::pair<int, int>> queue;
for (int vertex = 0; vertex < size; vertex++) {
queue.emplace(-degree[vertex], vertex);
}
while (queue.size() > 1) {
auto [negative_first, first] = queue.top();
queue.pop();
auto [negative_second, second] = queue.top();
queue.pop();
if (-negative_first - negative_second > maximum_degree) {
break;
}
int root = components.merge(first, second);
queue.emplace(negative_first + negative_second, root);
}
std::vector<int> root_id(size, -1);
std::vector<int> result(size);
int count = 0;
for (int vertex = 0; vertex < size; vertex++) {
int root = components.leader(vertex);
if (root_id[root] == -1) {
root_id[root] = count++;
}
result[vertex] = root_id[root];
}
return {result, count};
}
struct edge_record {
int left;
int right;
int original_id;
};
inline std::vector<int>
perfect_matching(int size, const std::vector<edge_record> &all_edges,
const std::vector<int> &edge_ids) {
std::vector<std::vector<int>> adjacency(size);
for (int id : edge_ids) {
adjacency[all_edges[id].left].push_back(id);
}
std::vector<int> match_left(size, -1);
std::vector<int> match_right(size, -1);
std::vector<int> distance(size);
std::vector<int> cursor(size);
while (true) {
std::queue<int> queue;
std::fill(distance.begin(), distance.end(), -1);
std::fill(cursor.begin(), cursor.end(), 0);
for (int left = 0; left < size; left++) {
if (match_left[left] == -1) {
distance[left] = 0;
queue.push(left);
}
}
while (!queue.empty()) {
int left = queue.front();
queue.pop();
for (int id : adjacency[left]) {
int next_id = match_right[all_edges[id].right];
if (next_id == -1) {
continue;
}
int next_left = all_edges[next_id].left;
if (distance[next_left] == -1) {
distance[next_left] = distance[left] + 1;
queue.push(next_left);
}
}
}
std::function<bool(int)> augment = [&](int left) {
for (int &index = cursor[left]; index < int(adjacency[left].size());
index++) {
int id = adjacency[left][index];
int right = all_edges[id].right;
int next_id = match_right[right];
if (next_id == -1 ||
(distance[all_edges[next_id].left] == distance[left] + 1 &&
augment(all_edges[next_id].left))) {
match_left[left] = id;
match_right[right] = id;
return true;
}
}
distance[left] = -1;
return false;
};
int augmented = 0;
for (int left = 0; left < size; left++) {
if (match_left[left] == -1) {
augmented += augment(left);
}
}
if (augmented == 0) {
break;
}
}
for (int id : match_left) {
assert(id != -1);
}
return match_left;
}
inline std::pair<std::vector<int>, std::vector<int>>
split_even_regular(int size, const std::vector<edge_record> &all_edges,
const std::vector<int> &edge_ids) {
std::vector<std::vector<int>> adjacency(2 * size);
for (int id : edge_ids) {
adjacency[all_edges[id].left].push_back(id);
adjacency[size + all_edges[id].right].push_back(id);
}
std::vector<int> cursor(2 * size);
std::vector<bool> used(all_edges.size());
std::vector<int> first;
std::vector<int> second;
first.reserve(edge_ids.size() / 2);
second.reserve(edge_ids.size() / 2);
for (int start = 0; start < 2 * size; start++) {
while (cursor[start] < int(adjacency[start].size()) &&
used[adjacency[start][cursor[start]]]) {
cursor[start]++;
}
if (cursor[start] == int(adjacency[start].size())) {
continue;
}
std::vector<int> vertex_stack{start};
std::vector<int> edge_stack;
std::vector<int> circuit;
while (!vertex_stack.empty()) {
int vertex = vertex_stack.back();
while (cursor[vertex] < int(adjacency[vertex].size()) &&
used[adjacency[vertex][cursor[vertex]]]) {
cursor[vertex]++;
}
if (cursor[vertex] == int(adjacency[vertex].size())) {
vertex_stack.pop_back();
if (!edge_stack.empty()) {
circuit.push_back(edge_stack.back());
edge_stack.pop_back();
}
continue;
}
int id = adjacency[vertex][cursor[vertex]++];
if (used[id]) {
continue;
}
used[id] = true;
int next = vertex < size ? size + all_edges[id].right
: all_edges[id].left;
vertex_stack.push_back(next);
edge_stack.push_back(id);
}
assert(circuit.size() % 2 == 0);
for (int index = 0; index < int(circuit.size()); index++) {
(index & 1 ? second : first).push_back(circuit[index]);
}
}
assert(first.size() == edge_ids.size() / 2);
assert(second.size() == edge_ids.size() / 2);
return {std::move(first), std::move(second)};
}
inline void color_regular(int size, const std::vector<edge_record> &all_edges,
std::vector<int> edge_ids, int degree, int offset,
std::vector<int> &result) {
if (degree == 0) {
assert(edge_ids.empty());
return;
}
assert(edge_ids.size() == std::size_t(size) * degree);
if (degree == 1) {
for (int id : edge_ids) {
if (all_edges[id].original_id != -1) {
result[all_edges[id].original_id] = offset;
}
}
return;
}
if (degree % 2 == 0) {
auto [first, second] = split_even_regular(size, all_edges, edge_ids);
color_regular(size, all_edges, std::move(first), degree / 2, offset,
result);
color_regular(size, all_edges, std::move(second), degree / 2,
offset + degree / 2, result);
return;
}
std::vector<int> matching = perfect_matching(size, all_edges, edge_ids);
std::vector<bool> selected(all_edges.size());
for (int id : matching) {
selected[id] = true;
if (all_edges[id].original_id != -1) {
result[all_edges[id].original_id] = offset;
}
}
std::vector<int> remaining;
remaining.reserve(edge_ids.size() - size);
for (int id : edge_ids) {
if (!selected[id]) {
remaining.push_back(id);
}
}
color_regular(size, all_edges, std::move(remaining), degree - 1,
offset + 1, result);
}
} // namespace bipartite_edge_coloring_internal
/// @brief Color every edge of a bipartite multigraph with Delta colors so
/// incident edges differ. Low-degree vertices are contracted before
/// regularization, keeping the number of real and dummy edges linear.
inline std::vector<int>
bipartite_edge_coloring(int left_size, int right_size,
const std::vector<std::pair<int, int>> &edges) {
using namespace bipartite_edge_coloring_internal;
assert(left_size >= 0 && right_size >= 0);
std::vector<int> left_degree(left_size);
std::vector<int> right_degree(right_size);
int maximum_degree = 0;
for (auto [left, right] : edges) {
assert(0 <= left && left < left_size);
assert(0 <= right && right < right_size);
maximum_degree = std::max(maximum_degree, ++left_degree[left]);
maximum_degree = std::max(maximum_degree, ++right_degree[right]);
}
if (edges.empty()) {
return {};
}
auto [left_id, left_count] =
contract_vertices(left_degree, maximum_degree);
auto [right_id, right_count] =
contract_vertices(right_degree, maximum_degree);
int size = std::max(left_count, right_count);
std::vector<int> contracted_left_degree(size);
std::vector<int> contracted_right_degree(size);
std::vector<edge_record> all_edges;
all_edges.reserve(edges.size() * 2);
for (int id = 0; id < int(edges.size()); id++) {
int left = left_id[edges[id].first];
int right = right_id[edges[id].second];
all_edges.push_back({left, right, id});
contracted_left_degree[left]++;
contracted_right_degree[right]++;
}
int left = 0;
int right = 0;
while (left < size && right < size) {
while (left < size && contracted_left_degree[left] == maximum_degree) {
left++;
}
while (right < size && contracted_right_degree[right] == maximum_degree) {
right++;
}
if (left == size || right == size) {
break;
}
int count = std::min(maximum_degree - contracted_left_degree[left],
maximum_degree - contracted_right_degree[right]);
for (int index = 0; index < count; index++) {
all_edges.push_back({left, right, -1});
}
contracted_left_degree[left] += count;
contracted_right_degree[right] += count;
}
assert(std::all_of(contracted_left_degree.begin(),
contracted_left_degree.end(),
[&](int degree) { return degree == maximum_degree; }));
assert(std::all_of(contracted_right_degree.begin(),
contracted_right_degree.end(),
[&](int degree) { return degree == maximum_degree; }));
std::vector<int> edge_ids(all_edges.size());
std::iota(edge_ids.begin(), edge_ids.end(), 0);
std::vector<int> result(edges.size(), -1);
color_regular(size, all_edges, std::move(edge_ids), maximum_degree, 0,
result);
for (int color : result) {
assert(0 <= color && color < maximum_degree);
}
return result;
}
} // namespace noya