description: Chordality certificate: a perfect-elimination ordering, or an induced cycle of length at least four when the graph is not chordal.¶
chordal_graph.hpp¶
Chordality certificate: a perfect-elimination ordering, or an induced cycle of length at least four when the graph is not chordal.
Verified by chordal_graph_recognition.
判定图是否为弦图，并给出完美消除序或无弦环证据；适合利用弦图结构做着色或团问题。
Implementation¶
#ifndef NOYA_CHORDAL_GRAPH_HPP
#define NOYA_CHORDAL_GRAPH_HPP 1
/// @complexity Time: O((V + E) log V) with the priority-queue MCS implementation.
/// Space: O(V + E).
#include <algorithm>
#include <cassert>
#include <queue>
#include <utility>
#include <vector>
namespace noya {
/// @brief Chordality certificate: a perfect-elimination ordering, or an
/// induced cycle of length at least four when the graph is not chordal.
struct chordal_graph_result {
bool chordal = false;
std::vector<int> elimination_order;
std::vector<int> induced_cycle;
};
/// @brief Recognize an undirected simple graph in O(n+m) expected practical
/// time using maximum cardinality search and return a certificate.
inline chordal_graph_result
chordal_graph(int n, const std::vector<std::pair<int, int>> &edges) {
assert(n >= 0);
std::vector<std::vector<int>> graph(n);
for (auto [first, second] : edges) {
assert(0 <= first && first < n);
assert(0 <= second && second < n);
if (first != second) {
graph[first].push_back(second);
graph[second].push_back(first);
}
}
for (auto &neighbors : graph) {
std::sort(neighbors.begin(), neighbors.end());
neighbors.erase(std::unique(neighbors.begin(), neighbors.end()),
neighbors.end());
}
std::priority_queue<std::pair<int, int>> queue;
std::vector<int> weight(n), chosen(n);
for (int vertex = 0; vertex < n; vertex++) {
queue.emplace(0, vertex);
}
std::vector<int> selection;
selection.reserve(n);
while (!queue.empty()) {
auto [current_weight, vertex] = queue.top();
queue.pop();
if (chosen[vertex] || current_weight != weight[vertex]) {
continue;
}
chosen[vertex] = true;
selection.push_back(vertex);
for (int next : graph[vertex]) {
if (!chosen[next]) {
queue.emplace(++weight[next], next);
}
}
}
chordal_graph_result result;
result.elimination_order.assign(selection.rbegin(), selection.rend());
std::vector<int> position(n);
for (int index = 0; index < n; index++) {
position[result.elimination_order[index]] = index;
}
for (int index = 0; index < n; index++) {
int vertex = result.elimination_order[index];
int parent = -1;
for (int next : graph[vertex]) {
if (position[next] > index &&
(parent == -1 || position[next] < position[parent])) {
parent = next;
}
}
if (parent == -1) {
continue;
}
for (int next : graph[vertex]) {
if (position[next] <= index || next == parent ||
std::binary_search(graph[parent].begin(), graph[parent].end(),
next)) {
continue;
}
std::vector<int> previous(n, -1);
std::queue<int> bfs;
previous[next] = next;
bfs.push(next);
while (!bfs.empty() && previous[parent] == -1) {
int current = bfs.front();
bfs.pop();
for (int candidate : graph[current]) {
if (candidate == vertex || position[candidate] <= index ||
previous[candidate] != -1) {
continue;
}
if (candidate != parent &&
std::binary_search(graph[vertex].begin(), graph[vertex].end(),
candidate)) {
continue;
}
previous[candidate] = current;
bfs.push(candidate);
}
}
if (previous[parent] != -1) {
result.induced_cycle = {vertex, next};
std::vector<int> path;
for (int current = parent; current != next;
current = previous[current]) {
path.push_back(current);
}
std::reverse(path.begin(), path.end());
result.induced_cycle.insert(result.induced_cycle.end(), path.begin(),
path.end());
}
return result;
}
}
result.chordal = true;
return result;
}
} // namespace noya
#endif // NOYA_CHORDAL_GRAPH_HPP
#include <algorithm>
#include <cassert>
#include <queue>
#include <utility>
#include <vector>
/// @complexity Time: O((V + E) log V) with the priority-queue MCS implementation.
/// Space: O(V + E).
namespace noya {
/// @brief Chordality certificate: a perfect-elimination ordering, or an
/// induced cycle of length at least four when the graph is not chordal.
struct chordal_graph_result {
bool chordal = false;
std::vector<int> elimination_order;
std::vector<int> induced_cycle;
};
/// @brief Recognize an undirected simple graph in O(n+m) expected practical
/// time using maximum cardinality search and return a certificate.
inline chordal_graph_result
chordal_graph(int n, const std::vector<std::pair<int, int>> &edges) {
assert(n >= 0);
std::vector<std::vector<int>> graph(n);
for (auto [first, second] : edges) {
assert(0 <= first && first < n);
assert(0 <= second && second < n);
if (first != second) {
graph[first].push_back(second);
graph[second].push_back(first);
}
}
for (auto &neighbors : graph) {
std::sort(neighbors.begin(), neighbors.end());
neighbors.erase(std::unique(neighbors.begin(), neighbors.end()),
neighbors.end());
}
std::priority_queue<std::pair<int, int>> queue;
std::vector<int> weight(n), chosen(n);
for (int vertex = 0; vertex < n; vertex++) {
queue.emplace(0, vertex);
}
std::vector<int> selection;
selection.reserve(n);
while (!queue.empty()) {
auto [current_weight, vertex] = queue.top();
queue.pop();
if (chosen[vertex] || current_weight != weight[vertex]) {
continue;
}
chosen[vertex] = true;
selection.push_back(vertex);
for (int next : graph[vertex]) {
if (!chosen[next]) {
queue.emplace(++weight[next], next);
}
}
}
chordal_graph_result result;
result.elimination_order.assign(selection.rbegin(), selection.rend());
std::vector<int> position(n);
for (int index = 0; index < n; index++) {
position[result.elimination_order[index]] = index;
}
for (int index = 0; index < n; index++) {
int vertex = result.elimination_order[index];
int parent = -1;
for (int next : graph[vertex]) {
if (position[next] > index &&
(parent == -1 || position[next] < position[parent])) {
parent = next;
}
}
if (parent == -1) {
continue;
}
for (int next : graph[vertex]) {
if (position[next] <= index || next == parent ||
std::binary_search(graph[parent].begin(), graph[parent].end(),
next)) {
continue;
}
std::vector<int> previous(n, -1);
std::queue<int> bfs;
previous[next] = next;
bfs.push(next);
while (!bfs.empty() && previous[parent] == -1) {
int current = bfs.front();
bfs.pop();
for (int candidate : graph[current]) {
if (candidate == vertex || position[candidate] <= index ||
previous[candidate] != -1) {
continue;
}
if (candidate != parent &&
std::binary_search(graph[vertex].begin(), graph[vertex].end(),
candidate)) {
continue;
}
previous[candidate] = current;
bfs.push(candidate);
}
}
if (previous[parent] != -1) {
result.induced_cycle = {vertex, next};
std::vector<int> path;
for (int current = parent; current != next;
current = previous[current]) {
path.push_back(current);
}
std::reverse(path.begin(), path.end());
result.induced_cycle.insert(result.induced_cycle.end(), path.begin(),
path.end());
}
return result;
}
}
result.chordal = true;
return result;
}
} // namespace noya