グラフの平面性テスト(Left-Right Planarity Test)

//グラフの平面性テストのプログラムです。
//Ulrik BrandesのThe Left-Right Planarity Testを参考にしてプログラミングしてみました。
//Embeddingのところは未完成なので参考程度にどうぞ。
//ソースコードはC++です。
//入力:頂点数n、辺数mの単純無向グラフG
//出力:Gが平面的ならば”PLANAR”、そうでないならば"NOT PLANAR"

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <stack>

using namespace std;

const long long inf = 1e18;
const long long null = 1e18+1;
const long long na = 1e18+2;
const long long set = 1;
const long long unset = -1;

typedef pair<long long, long long> Edge;
#define EdgeNull make_pair(null,null)

//graph
long long n;
long long m;
vector< vector<long long> > G;
vector<long long> Roots;
vector< Edge > parent_edge;
vector< vector< Edge > > child_edge;

//orientation
vector<long long> height;
vector< vector<long long> > lowpt;
vector< vector<long long> > lowpt2;
vector< vector<long long> > nesting_depth;

//testing
vector< vector<Edge> > ref;
vector< vector<long long> > side;
stack< pair< pair<Edge, Edge>, pair<Edge, Edge> > > S;
vector< vector< pair< pair<Edge, Edge>, pair<Edge, Edge > > > > stack_bottom;
vector< vector<Edge > > lowpt_edge;

//embedding
vector<Edge> centerRef;
vector<Edge> leftRef;
vector<Edge> rightRef;

//DFS orientation and nesting order
void dfs1(long long v, long long pre_v){
    Edge e = parent_edge[v];
    for(long long i = 0; i < G[v].size(); i++){
        long long w = G[v][i];
        lowpt[v][w] = height[v];
        lowpt2[v][w] = height[v];
        
        if(height[w] == inf){
            parent_edge[w] = make_pair(v, w);
            child_edge[v].push_back(make_pair(v, w));
            height[w] = height[v]+1;
            dfs1(w, v);
        }else{
            if(w != pre_v && height[w] <= height[v]){
                child_edge[v].push_back(make_pair(v, w));
            }
            lowpt[v][w] = height[w];
            
        }
        nesting_depth[v][w] = 2 * lowpt[v][w];
        if(lowpt2[v][w] < height[v]){
            nesting_depth[v][w] = nesting_depth[v][w]+1;
        }
        if(e != EdgeNull){
            if(lowpt[v][w] < lowpt[e.first][e.second]){
                lowpt2[e.first][e.second] = min(lowpt[e.first][e.second], lowpt2[v][w]);
                lowpt[e.first][e.second] = lowpt[v][w];
            }else if(lowpt[v][w] > lowpt[e.first][e.second]){
                lowpt2[e.first][e.second] = min(lowpt2[e.first][e.second], lowpt[v][w]);
            }else{
                lowpt2[e.first][e.second] = min(lowpt2[e.first][e.second], lowpt2[v][w]);
            }
        }
    }
    return;
}

long long lowest(pair<pair<Edge,Edge>,pair<Edge,Edge>> P){
    if(P.first == make_pair(EdgeNull,EdgeNull)){
        return lowpt[P.second.first.first][P.second.first.second];
    }
    if(P.second == make_pair(EdgeNull,EdgeNull)){
        return lowpt[P.first.first.first][P.first.first.second];
    }

    return min(lowpt[P.first.first.first][P.first.first.second],lowpt[P.second.first.first][P.second.first.second]);
}

bool conflicting(pair<Edge,Edge> I, Edge b){
    return (I != make_pair(EdgeNull,EdgeNull) && lowpt[I.second.first][I.second.second] > lowpt[b.first][b.second]);
}

//testing for LR partition
void dfs2(long long v){
    Edge e = parent_edge[v];
    //ordered by nesting_depth
    vector< pair< long long, Edge > > E;
    for(long long i = 0; i < child_edge[v].size(); i++){
        Edge ei = child_edge[v][i];
        E.push_back(make_pair(nesting_depth[ei.first][ei.second], ei));
    }
    sort(E.begin(), E.end());
    for(long long i = 0; i < E.size(); i++){
        Edge ei = E[i].second;
        stack_bottom[ei.first][ei.second] = S.top();
        if(ei == parent_edge[ei.second]){
            dfs2(ei.second);
        }else{
            lowpt_edge[ei.first][ei.second] = ei;
            S.push(make_pair(make_pair(EdgeNull, EdgeNull), make_pair(ei,ei)));
        }
        if(lowpt[ei.first][ei.second] < height[v]){
            Edge e1 = E[0].second; 
            if(ei == e1){
                lowpt_edge[e.first][e.second] = lowpt_edge[e1.first][e1.second];
            }else{
                //add constraints of ei
                pair< pair<Edge, Edge>, pair<Edge, Edge > > P = make_pair(make_pair(EdgeNull,EdgeNull),make_pair(EdgeNull,EdgeNull));
                do{
                    pair< pair<Edge, Edge>, pair<Edge, Edge > > Q = S.top();S.pop();
                    if(Q.first != make_pair(EdgeNull,EdgeNull)){
                        swap(Q.first,Q.second);
                    }
                    if(Q.first != make_pair(EdgeNull,EdgeNull)){
                        cout << "NOT PLANAR" << endl;
                        exit(0);
                    }else{
                        if(lowpt[Q.second.first.first][Q.second.first.second] > lowpt[e.first][e.second]){
                            if(P.second == make_pair(EdgeNull,EdgeNull)){
                                P.second.second = Q.second.second;
                            }else{
                                ref[P.second.first.first][P.second.first.second] = Q.second.second;
                            }
                            P.second.first = Q.second.first;
                        }else{
                            ref[Q.second.first.first][Q.second.first.second] = lowpt_edge[e.first][e.second];
                        }
                    }
                }while(S.top() != stack_bottom[ei.first][ei.second]);
                while(conflicting(S.top().first, ei) || conflicting(S.top().second, ei)){
                    pair< pair<Edge, Edge>, pair<Edge, Edge > > Q = S.top();S.pop();
                    if(conflicting(Q.second, ei)){
                        swap(Q.first, Q.second);
                    }
                    if(conflicting(Q.second, ei)){
                        cout << "NOT PLANAR" << endl;
                        exit(0);
                    }else{
                        ref[P.second.first.first][P.second.first.second] = Q.second.second;
                        if(Q.second.first != make_pair(null,null)){
                            P.second.first = Q.second.first;
                        }
                    }
                    if(P.first == make_pair(EdgeNull,EdgeNull)){
                        P.first.second = Q.first.second;
                    }else{
                        ref[P.first.first.first][P.first.first.second] = Q.first.second;
                    }
                    P.first.first = Q.first.first;
                }
                if(P != make_pair(make_pair(EdgeNull,EdgeNull), make_pair(EdgeNull,EdgeNull))){
                    S.push(P);
                }
            }
        }
    }
    //remove back edges returning to parent
    if(e != EdgeNull){
        long long u = e.first;
        //trim back edges ending at parent u
        while(S.size() != 1 && lowest(S.top()) == height[u]){
            pair< pair<Edge, Edge>, pair<Edge, Edge > > P = S.top();S.pop();
            if(P.first.first != EdgeNull){
                side[P.first.first.first][P.first.first.second] = unset;
            }
        }
        if(S.size() != 1){
            pair< pair<Edge, Edge>, pair<Edge, Edge > > P = S.top();S.pop();
            //trim left interval
            while(P.first.second != EdgeNull && P.first.second.second == u){
                P.first.second = ref[P.first.second.first][P.first.second.second];
            }
            if(P.first.second == EdgeNull && P.first.first != EdgeNull){
                ref[P.first.first.first][P.first.first.second] = P.second.first;
                side[P.first.first.first][P.first.first.second] = unset;
                P.first.first = EdgeNull;
            }

            //trim right interval
            while(P.second.second != EdgeNull && P.second.second.second == u){
                P.second.second = ref[P.second.second.first][P.second.second.second];
            }
            if(P.second.second == EdgeNull && P.second.first != EdgeNull){
                ref[P.second.first.first][P.second.first.second] = P.first.first;
                side[P.second.first.first][P.second.first.second] = unset;
                P.second.first = EdgeNull;
            }
            S.push(P);
        }

        //side of e is side of a highest return edge
        if(lowpt[e.first][e.second] < height[u]){
            Edge hL = S.top().first.second;
            Edge hR = S.top().second.second;
            if(hL != EdgeNull && (hR == EdgeNull || lowpt[hL.first][hL.second] > lowpt[hR.first][hR.second])){
                ref[e.first][e.second] = hL;
            }else{
                ref[e.first][e.second] = hR;
            }
        }
    }
    return;
}

void dfs3(long long v){
    vector< pair< long long, Edge > > E;
    for(long long i = 0; i < child_edge[v].size(); i++){
        Edge ei = child_edge[v][i];
        E.push_back(make_pair(nesting_depth[ei.first][ei.second], ei));
    }
    sort(E.begin(), E.end());
    for(long long i = 0; i < E.size(); i++){
        Edge ei = E[i].second;
        long long w = ei.second;
        if(ei == parent_edge[w]){
            centerRef.push_back(ei);
            //rightRef[v] = ei;
            //leftRef[v] = ei;
            dfs3(w);
        }else{
            if(side[ei.first][ei.second] == set){
                rightRef.push_back(ei);
                //rightRef[w] = ei;
            }else{
                leftRef.push_back(ei);
                //leftRef[w] = ei;
            }
        }
    }
    return;
}

long long sign(Edge e){
    if(ref[e.first][e.second] != EdgeNull){
        side[e.first][e.second] = side[e.first][e.second] * sign(ref[e.first][e.second]);
        ref[e.first][e.second] = EdgeNull;
    }
    return side[e.first][e.second];
}

int main(){
    cin >> n >> m;

    if(n <= 4){
        cout << "PLANAR" << endl;
        exit(0);
    }else if(3* n -6 < m){
        cout << "NOT PLANAR" << endl;
        exit(0);
    }

    //graph
    G.resize(n);
    for(long long i = 0; i < m; i++){
        long long v;
        long long w;
        cin >> v >> w;
        G[v].push_back(w);
        G[w].push_back(v);
    }
    parent_edge.resize(n, EdgeNull);
    child_edge.resize(n);

    //orientation
    height.resize(n, inf);
    lowpt.resize(n, vector<long long>(n, na));
    lowpt2.resize(n, vector<long long>(n, na));
    nesting_depth.resize(n, vector<long long>(n, na));
    for(long long s = 0; s < n; s++){
        if(height[s] == inf){
            height[s] = 0;
            Roots.push_back(s);
            dfs1(s,null);
        }
    }

    /*
    //確認用
    cout << "G : " << endl;
    for(long long i = 0; i < n; i++){
        cout << i << " : ";
        for(long long j = 0; j < G[i].size(); j++){
            cout << G[i][j] << " ";
        }cout << endl;
    }cout << endl;

    cout << "parent_edge : " << endl;
    for(long long i = 0; i < n; i++){
        cout << i << " : " <<parent_edge[i].first<<"-"<<parent_edge[i].second << endl;
    }cout << endl;

    cout << "child_edge : " << endl;
    for(long long i = 0; i < n; i++){
        cout << i << " : ";
        for(long long j = 0; j < child_edge[i].size(); j++){
            cout << child_edge[i][j].second << " ";
        }cout << endl;
    }cout << endl;

    cout << "height : " << endl;
    for(long long i = 0; i < n; i++){
        cout << i <<" : " << height[i] << endl;
    }cout << endl;

    cout << "lowpt : " << endl;
    for(long long i = 0; i < n; i++){
        cout << i << " : ";
        for(long long j = 0; j < n; j++){
            if(lowpt[i][j] == na){
                cout << -1 << " ";
            }else{
                cout << lowpt[i][j] << " ";
            }
        }cout << endl;
    }cout << endl;

    cout << "lowpt2 : " << endl;
    for(long long i = 0; i < n; i++){
        cout << i << " : ";
        for(long long j = 0; j < n; j++){
            if(lowpt2[i][j] == na){
                cout << -1 << " ";
            }else{
                cout << lowpt2[i][j] << " ";
            }
        }cout << endl;
    }cout << endl;

    cout << "nesting_depth : " << endl;
    for(long long i = 0; i < n; i++){
        cout << i << " : ";
        for(long long j = 0; j < n; j++){
            if(nesting_depth[i][j] == na){
                cout << -1 << " ";
            }else{
                cout << nesting_depth[i][j] << " ";
            }
        }cout << endl;
    }cout << endl;
    */

    //testing
    ref.resize(n, vector<Edge>(n, EdgeNull));
    side.resize(n, vector<long long>(n, set));
    stack_bottom.resize(n, vector< pair<pair<Edge,Edge>, pair<Edge,Edge>> >(n, make_pair(make_pair(EdgeNull, EdgeNull), make_pair(EdgeNull, EdgeNull))));
    S.push(make_pair(make_pair(EdgeNull, EdgeNull), make_pair(EdgeNull, EdgeNull)));
    lowpt_edge.resize(n, vector<Edge>(n, EdgeNull));
    for(long long i = 0; i < Roots.size(); i++){
        long long s = Roots[i];
        dfs2(s);
    }
    cout << "PLANAR" << endl;

    /*
    //embedding
    //centerRef.resize(n,EdgeNull);
    //leftRef.resize(n,EdgeNull);
    //rightRef.resize(n,EdgeNull);
    for(long long v = 0; v < n; v++){
        for(long long j = 0; j < G[v].size(); j++){
            Edge e = make_pair(v, G[v][j]);
            nesting_depth[e.first][e.second] = sign(e)*nesting_depth[e.first][e.second];
        }
    }
    for(long long i = 0; i < Roots.size(); i++){
        long long s = Roots[i];
        dfs3(s);
    }

    cout << "centerRef : " << endl;
    for(long long i = 0; i < centerRef.size(); i++){    
        cout << centerRef[i].first <<"-"<< centerRef[i].second << " ";
    }cout << endl;

    cout << "leftRef : " << endl;
    for(long long i = 0; i < leftRef.size(); i++){
        cout << leftRef[i].first <<"-"<< leftRef[i].second << " ";
    }cout << endl;

    cout << "rightRef : " << endl;
    for(long long i = 0; i < rightRef.size(); i++){
        cout << rightRef[i].first <<"-"<< rightRef[i].second << " ";
    }cout << endl;
    */

    return 0;
}