平面性テストと埋め込みのプログラム
// an implementation of the hopcroft and tarjan planarity test and embedding algorithmを参考に平面性テストと埋め込みのプログラムを作成しました。
// 入力 : 頂点数n,辺数mの単純無向グラフG
// 出力 : Gが平面的ならばPLANARと頂点数n,辺数mの平面的グラフの埋め込み、そうでないならばNOTPLANAR
#include<iostream>
#include<vector>
#include<list>
#include<stack>
#include<algorithm>
#include<memory>
using namespace std;
class Graph{
private:
enum class LeftRight{
Empty,
Left,
Right,
};
using Vertex = long long;
using VertexNum = long long;
using Edge = pair<Vertex, Vertex>;
using EdgeNum = long long;
using GraphList = vector<list<Vertex>>;
using Num = long long;
using NumEdgePair = pair<Num, Edge>;
const Vertex VertexNull = -1;
class Block{
private:
list<Num> Latt,Ratt;
list<Edge> Lseg,Rseg;
public:
Block(Edge e, list<Num> &A){
Lseg.push_back(e);
Latt.insert(Latt.end(), A.begin(), A.end());
A.clear();
}
void flip(){
swap(Latt, Ratt);
swap(Lseg, Rseg);
}
Num headOfLatt(){
return Latt.front();
}
bool emptyLatt(){
return Latt.empty();
}
Num headOfRatt(){
return Ratt.front();
}
bool emptyRatt(){
return Ratt.empty();
}
bool leftInterlace(stack<unique_ptr<Block>> &S){
if(Latt.empty()){
cout << "Latt is never empty." << endl;
exit(0);
}
if(!S.empty() && !(S.top()->emptyLatt()) && Latt.back() < S.top()->headOfLatt()){
return true;
}else{
return false;
}
}
bool rightInterlace(stack<unique_ptr<Block>> &S){
if(Latt.empty()){
cout << "Latt is never empty." << endl;
exit(0);
}
if(!S.empty() && !(S.top()->emptyRatt()) && Latt.back() < S.top()->headOfRatt()){
return true;
}else{
return false;
}
}
void combine(unique_ptr<Block> &Bprime){
Latt.insert(Latt.end(), Bprime->Latt.begin(), Bprime->Latt.end());
Ratt.insert(Ratt.end(), Bprime->Ratt.begin(), Bprime->Ratt.end());
Lseg.insert(Lseg.end(), Bprime->Lseg.begin(), Bprime->Lseg.end());
Rseg.insert(Rseg.end(), Bprime->Rseg.begin(), Bprime->Rseg.end());
Bprime->Latt.clear();
Bprime->Ratt.clear();
Bprime->Lseg.clear();
Bprime->Rseg.clear();
}
bool clean(Num dfsnum_w, vector<vector<LeftRight>> &alpha, vector<Num> &dfsnum){
while(!Latt.empty() && Latt.front() == dfsnum_w){
Latt.pop_front();
}
while(!Ratt.empty() && Ratt.front() == dfsnum_w){
Ratt.pop_front();
}
if(!Latt.empty() || !Ratt.empty()){
return false;
}
for(auto itr = Lseg.begin(); itr != Lseg.end(); ++itr){
Edge e = *itr;
alpha[e.first][e.second] = LeftRight::Left;
}
for(auto itr = Rseg.begin(); itr != Rseg.end(); ++itr){
Edge e = *itr;
alpha[e.first][e.second] = LeftRight::Right;
}
return true;
}
void addToAtt(list<Num> &Att, Num dfsnum_w0, vector<vector<LeftRight>> &alpha, vector<Num> &dfsnum){
if(!Ratt.empty() && headOfRatt() > dfsnum_w0){
flip();
}
Att.insert(Att.end(), Latt.begin(), Latt.end());
Latt.clear();
Att.insert(Att.end(), Ratt.begin(), Ratt.end());
Ratt.clear();
for(auto itr = Lseg.begin(); itr != Lseg.end(); ++itr){
Edge e = *itr;
alpha[e.first][e.second] = LeftRight::Left;
}
for(auto itr = Rseg.begin(); itr != Rseg.end(); ++itr){
Edge e = *itr;
alpha[e.first][e.second] = LeftRight::Right;
}
}
};
bool runPlanarityTest;
bool isPlanarityGraph;
bool runPlanarEmbed;
VertexNum n;
EdgeNum m;
GraphList G_list;
GraphList Gin_list;
void countSort(vector<NumEdgePair> &input, Num exp){
EdgeNum num = static_cast<Num>(input.size());
vector<NumEdgePair> output(num);
vector<Num> count(10, 0);
for(EdgeNum i = 0; i < num; ++i){
++count[(input[i].first / exp) % 10];
}
for(Num i = 1; i < 10; ++i){
count[i] += count[i-1];
}
for(EdgeNum i = num-1; i >= 0; --i){
output[count[(input[i].first / exp) % 10]-1] = input[i];
--count[(input[i].first / exp) % 10];
}
for(EdgeNum i = 0; i < num; ++i){
input[i] = output[i];
}
}
void radixSort(vector<NumEdgePair> &input){
EdgeNum num = static_cast<EdgeNum>(input.size());
Num maxNum = input[0].first;
for(EdgeNum i = 0; i < num; ++i){
maxNum = max(maxNum, input[i].first);
}
for(Num exp = 1; maxNum /exp > 0; exp *= 10){
countSort(input, exp);
}
}
void dfs(Vertex now, vector<bool> &reached){
reached[now] = true;
for(auto itr = G_list[now].begin(); itr != G_list[now].end(); ++itr){
Vertex next = *itr;
if(!reached[next]){
dfs(next, reached);
}
}
}
void makeBiconnectedGraph(){
vector<bool> reached(n, false);
Vertex u = 0;
for(Vertex v = 0; v < n; ++v){
if(!reached[v]){
dfs(v, reached);
if(u != v){
G_list[u].push_back(v);
G_list[v].push_back(u);
}
}
}
for(Vertex v = 0; v < n; ++v){
reached[v] = false;
}
vector<Num> dfsnum(n);
vector<Vertex> parent(n, VertexNull);
Num dfs_count = 0;
vector<Num> lowpt(n);
dfsInMakeBiconnectedGraph(0, dfs_count, reached, dfsnum, lowpt, parent);
}
void dfsInMakeBiconnectedGraph(Vertex v, Num &dfs_count, vector<bool> &reached, vector<Num> &dfsnum, vector<Num> &lowpt, vector<Vertex> &parent){
dfsnum[v] = dfs_count;
++dfs_count;
lowpt[v] = dfsnum[v];
reached[v] = true;
if(G_list[v].empty()){
return;
}
Vertex u = G_list[v].front();
for(auto itr = G_list[v].begin(); itr != G_list[v].end(); ++itr){
Vertex w = *itr;
if(!reached[w]){
parent[w] = v;
dfsInMakeBiconnectedGraph(w, dfs_count, reached, dfsnum, lowpt, parent);
if(lowpt[w] == dfsnum[v]){
if(w == u && parent[v] != VertexNull){
G_list[w].push_back(parent[v]);
G_list[parent[v]].push_back(w);
}
if(w != u){
G_list[u].push_back(w);
G_list[w].push_back(u);
}
}
lowpt[v] = min(lowpt[v], lowpt[w]);
}else{
lowpt[v] = min(lowpt[v], dfsnum[w]);
}
}
}
void reorder(vector<Num> &dfsnum, vector<Vertex> &parent){
vector<bool> reached(n, false);
Num dfs_count = 0;
list<Edge> Del;
vector<Num> lowpt1(n), lowpt2(n);
Vertex first_vertex = 0;
dfsInReorder(Del, first_vertex, dfs_count, reached, dfsnum, lowpt1, lowpt2, parent);
for(auto it = Del.begin(); it != Del.end(); ++it){
Edge e = *it;
Vertex u = e.first;
Vertex v = e.second;
for(auto itr = G_list[u].begin(); itr != G_list[u].end(); ){
if(*itr == v){
itr = G_list[u].erase(itr);
continue;
}
++itr;
}
}
vector<vector<Num>> cost(n, vector<Num>(n, 0));
vector<Edge> edges;
for(Vertex v = 0; v < n; ++v){
for(auto itr = G_list[v].begin(); itr != G_list[v].end(); ++itr){
Vertex w = *itr;
Num c = (dfsnum[w] < dfsnum[v] ? 2*dfsnum[w] : (lowpt2[w] >= dfsnum[v] ? 2*lowpt1[w] : 2*lowpt1[w]+1));
cost[v][w] = c;
edges.push_back(make_pair(v, w));
}
}
vector<NumEdgePair> sort_edges;
for(Vertex u = 0; u < n; ++u){
for(auto itr = G_list[u].begin(); itr != G_list[u].end(); ++itr){
Vertex v = *itr;
sort_edges.push_back(make_pair(cost[u][v], make_pair(u, v)));
}
}
radixSort(sort_edges);
G_list.clear();
G_list.resize(n);
for(EdgeNum i = 0; i < static_cast<EdgeNum>(sort_edges.size()); ++i){
Edge e = sort_edges[i].second;
G_list[e.first].push_back(e.second);
}
}
void dfsInReorder(list<Edge> &Del, Vertex v, Num &dfs_count, vector<bool> &reached, vector<Num> &dfsnum, vector<Num> &lowpt1, vector<Num> &lowpt2, vector<Vertex> &parent){
dfsnum[v] = dfs_count;
++dfs_count;
lowpt1[v] = dfsnum[v];
lowpt2[v] = dfsnum[v];
reached[v] = true;
for(auto itr = G_list[v].begin(); itr != G_list[v].end(); ++itr){
Vertex w = *itr;
if(!reached[w]){
parent[w] = v;
dfsInReorder(Del, w, dfs_count, reached, dfsnum, lowpt1, lowpt2, parent);
lowpt1[v] = min(lowpt1[v], lowpt1[w]);
}else{
lowpt1[v] = min(lowpt1[v], dfsnum[w]);
if(dfsnum[w] >= dfsnum[v] || w == parent[v]){
Del.push_back(make_pair(v, w));
}
}
}
for(auto itr = G_list[v].begin(); itr != G_list[v].end(); ++itr){
Vertex w = *itr;
if(parent[w] == v){
if(lowpt1[w] != lowpt1[v]){
lowpt2[v] = min(lowpt2[v], lowpt1[w]);
}
lowpt2[v] = min(lowpt2[v], lowpt2[w]);
}else{
if(lowpt1[v] != dfsnum[w]){
lowpt2[v] = min(lowpt2[v], dfsnum[w]);
}
}
}
}
bool stronglyPlanar(Edge e0, list<Num> &Att, vector<vector<LeftRight>> &alpha, vector<Num> &dfsnum, vector<Vertex> &parent){
// determine the cycle C(e0)
Vertex x = e0.first;
Vertex y = e0.second;
Edge e = make_pair(y, G_list[y].front());
Vertex wk = y;
while(dfsnum[e.second] > dfsnum[wk]){
wk = e.second;
e = make_pair(wk, G_list[wk].front());
}
Vertex w0 = e.second;
// process all edges leaving the spine
Vertex w = wk;
stack<unique_ptr<Block>> S;
while(w != x){
Num count = 0;
for(auto itr = G_list[w].begin(); itr != G_list[w].end(); ++itr){
e = make_pair(w, *itr);
++count;
if(count != 1){
// test recursively
list<Num> A;
if(dfsnum[w] < dfsnum[e.second]){
if(!stronglyPlanar(e, A, alpha, dfsnum, parent)){
while(!S.empty()){
S.pop();
}
return false;
}
}else{
A.push_back(dfsnum[e.second]);
}
// update stack S of attachments
unique_ptr<Block> B(new Block(e, A));
while(true){
if(B->leftInterlace(S)){
S.top()->flip();
}
if(B->leftInterlace(S)){
while(!S.empty()){
S.pop();
}
return false;
}
if(B->rightInterlace(S)){
B->combine(S.top());
S.pop();
}else{
break;
}
}
S.push(move(B));
}
}
// prepare for next iteration
while(!S.empty() && S.top()->clean(dfsnum[parent[w]], alpha, dfsnum)){
S.pop();
}
w = parent[w];
}
// test strong planarity and compute Att
Att.clear();
while(!S.empty()){
unique_ptr<Block> B(move(S.top()));
S.pop();
if(!B->emptyLatt() && !B->emptyRatt() && (B->headOfLatt() > dfsnum[w0]) && (B->headOfRatt() > dfsnum[w0])){
while(!S.empty()){
S.pop();
}
return false;
}
B->addToAtt(Att, dfsnum[w0], alpha, dfsnum);
}
if(w0 != x){
Att.push_back(dfsnum[w0]);
}
return true;
}
void embedding(Edge e0, LeftRight t, vector<vector<LeftRight>> &alpha, vector<Num> &dfsnum, list<Edge> &T, list<Edge> &A, Num &cur_nr, vector<vector<Num>> &sort_num, vector<Edge> &tree_edge_into, vector<Vertex> &parent){
// embed : determine the cycle C(e0)
Vertex x = e0.first;
Vertex y = e0.second;
tree_edge_into[y] = e0;
Edge e = make_pair(y, G_list[y].front());
Vertex wk = y;
while(dfsnum[e.second] > dfsnum[wk]){
wk = e.second;
tree_edge_into[wk] = e;
e = make_pair(wk, G_list[wk].front());
}
Vertex w0 = e.second;
Edge back_edge_into_w0 = e;
// process the subsegments
Vertex w = wk;
list<Edge> Al, Ar;
list<Edge> Tprime, Aprime;
T.clear();
T.push_back(e);
while(w != x){
Num count = 0;
for(auto itr = G_list[w].begin(); itr != G_list[w].end(); ++itr){
e = make_pair(w, *itr);
++count;
if(count != 1){
// embed recursively
if(dfsnum[w] < dfsnum[e.second]){
LeftRight tprime = (t == alpha[e.first][e.second] ? LeftRight::Left : LeftRight::Right);
embedding(e, tprime, alpha, dfsnum, Tprime, Aprime, cur_nr, sort_num, tree_edge_into, parent);
}else{
Tprime.push_back(e);
Aprime.push_back(make_pair(e.second, e.first));
}
// update list T,Al ans Ar
if(t == alpha[e.first][e.second]){
Tprime.insert(Tprime.end(), T.begin(), T.end());
T.clear();
swap(T, Tprime);
Al.insert(Al.end(), Aprime.begin(), Aprime.end());
Aprime.clear();
}else{
T.insert(T.end(), Tprime.begin(), Tprime.end());
Tprime.clear();
Aprime.insert(Aprime.end(), Ar.begin(), Ar.end());
Aprime.clear();
swap(Ar, Aprime);
}
}
}
// compute ws adjacency list and prepare for next iteration
Edge ew = tree_edge_into[w];
T.push_back(make_pair(ew.second, ew.first));
for(auto itr = T.begin(); itr != T.end(); ++itr){
sort_num[e.first][e.second] = cur_nr;
++cur_nr;
}
T.clear();
while(!Al.empty() && Al.back().first == parent[w]){
T.push_back(Al.back());
Al.pop_back();
}
T.push_back(tree_edge_into[w]);
while(!Ar.empty() && Ar.front().first == parent[w]){
T.push_back(Ar.front());
Ar.pop_front();
}
w = parent[w];
}
// prepare the output
A.clear();
swap(A, Ar);
A.push_back(make_pair(back_edge_into_w0.second, back_edge_into_w0.first));
A.insert(A.end(), Al.begin(), Al.end());
Al.clear();
}
public:
void initialize(VertexNum n, EdgeNum m, GraphList G_list){
this->n = n;
this->m = m;
this->G_list = G_list;
this->Gin_list = G_list;
runPlanarityTest = false;
isPlanarityGraph = false;
runPlanarEmbed = false;
}
bool planar(){
if(runPlanarityTest){
return isPlanarityGraph;
}
runPlanarityTest = true;
if(n <= 3){
isPlanarityGraph = true;
return true;
}
if(3*n-6 < m){
return false;
}
// make G a copy of Gin and add edges to make G bidirected
vector<Edge> companion_in_G;
vector<Vertex> link(n);
bool Gin_is_bidirected = true;
for(Vertex u = 0; u < n; ++u){
link[u] = u;
}
for(Vertex u = 0; u < n; ++u){
for(auto itr = G_list[u].begin(); itr != G_list[u].end(); ++itr){
Vertex v = *itr;
companion_in_G.push_back(make_pair(link[u],link[v]));
}
}
// bidirect G
vector<Num> nr(n);
vector<vector<Num>> cost(n, vector<Num>(n,0));
Num cur_nr = 0;
for(Vertex u = 0; u < n; ++u){
nr[u] = cur_nr;
++cur_nr;
}
for(EdgeNum i = 0; i < static_cast<EdgeNum>(companion_in_G.size()); ++i){
Edge e = companion_in_G[i];
Vertex u = e.first;
Vertex v = e.second;
cost[u][v] = ( ( nr[u] < nr[v] ) ? n*nr[u]+nr[v] : n*nr[v]+nr[u] );
}
vector<NumEdgePair> sort_edges;
for(Vertex u = 0; u < n; ++u){
for(auto itr = G_list[u].begin(); itr != G_list[u].end(); ++itr){
Vertex v = *itr;
sort_edges.push_back(make_pair(cost[u][v], make_pair(u, v)));
}
}
radixSort(sort_edges);
G_list.clear();
G_list.resize(n);
for(EdgeNum i = 0; i < static_cast<EdgeNum>(sort_edges.size()); ++i){
Edge e = sort_edges[i].second;
G_list[e.first].push_back(e.second);
}
list<Edge> L;
for(Num i = 0; i < static_cast<Num>(sort_edges.size()); ++i){
L.push_back(sort_edges[i].second);
}
while(!L.empty()){
Edge e = L.front();
L.pop_front();
if(!L.empty() && (e.first == L.front().second) && (L.front().first == e.second)){
L.pop_front();
}else{
G_list[e.second].push_back(e.first);
Gin_is_bidirected = false;
}
}
// make G biconnected
makeBiconnectedGraph();
// make H a copy of G
GraphList H_list = G_list;
vector<Edge> companion_in_H = companion_in_G;
vector<Edge> reversal;
for(Num i = 0; i < static_cast<Num>(companion_in_H.size()); ++i){
Edge e = companion_in_H[i];
reversal.push_back(make_pair(e.second, e.first));
}
// test planarity
vector<Num> dfsnum(n);
vector<Vertex> parent(n, VertexNull);
reorder(dfsnum, parent);
vector<vector<LeftRight>> alpha(n, vector<LeftRight>(n, LeftRight::Empty));
list<Num> Att;
Vertex first_vertex = 0;
Edge e0 = make_pair(first_vertex, G_list[first_vertex].front());
alpha[e0.first][e0.second] = LeftRight::Left;
if(!stronglyPlanar(e0, Att, alpha, dfsnum, parent)){
return false;
}
// construct embedding
list<Edge> T,A;
cur_nr = 0;
vector<vector<Num>> sort_num(n, vector<Num>(n));
vector<Edge> tree_edge_into(n);
e0 = make_pair(first_vertex, G_list[first_vertex].front());;
embedding(e0, LeftRight::Left, alpha, dfsnum, T, A, cur_nr, sort_num, tree_edge_into, parent);
T.insert(T.end(), A.begin(), A.end());
for(auto itr = T.begin(); itr != T.end(); ++itr){
Edge e = *itr;
sort_num[e.first][e.second] = cur_nr;
++cur_nr;
}
vector<NumEdgePair> sort_Gin;
for(Vertex u = 0; u < n; ++u){
for(auto itr = Gin_list[u].begin(); itr != Gin_list[u].end(); ++itr){
Vertex v = *itr;
sort_Gin.push_back(make_pair(sort_num[u][v], make_pair(u, v)));
}
}
radixSort(sort_Gin);
Gin_list.clear();
Gin_list.resize(n);
for(Num i = 0; i < static_cast<Num>(sort_Gin.size()); ++i){
Edge e = sort_Gin[i].second;
Gin_list[e.first].push_back(e.second);
}
isPlanarityGraph = true;
runPlanarEmbed = true;
return true;
}
void printPlanarEmbedding(){
if(!runPlanarEmbed){
cout << "Do not run planar embed." << endl;
return ;
}
printGin_list();
}
void printG_list(){
for(Vertex u = 0; u < n; ++u){
cout << u << " : ";
for(auto itr = G_list[u].begin(); itr != G_list[u].end(); ++itr){
Vertex v = *itr;
cout << v << " ";
}cout << endl;
}cout << endl;
}
void printGin_list(){
for(Vertex u = 0; u < n; ++u){
cout << u << " : ";
for(auto itr = Gin_list[u].begin(); itr != Gin_list[u].end(); ++itr){
Vertex v = *itr;
cout << v << " ";
}cout << endl;
}cout << endl;
}
};
int main(){
long long n, m;
cin >> n >> m;
vector<list<long long>> G_list(n);
for(long long i = 0; i < m; ++i){
long long u, v;
cin >> u >> v;
G_list[u].push_back(v);
G_list[v].push_back(u);
}
Graph G;
G.initialize(n, m, G_list);
//G.printG_list();
if(G.planar()){
cout << "PLANAR" << endl;
G.printPlanarEmbedding();
}else{
cout << "NOTPLANAR" << endl;
}
return 0;
}
