#include <LEDA/graphwin.h>
#include <LEDA/graph_alg.h>

#include <LEDA/ugraph.h>
#include <LEDA/stack.h>
#include <LEDA/array.h>
     

static void  find_independent_neighbors(const ugraph& G, 
                                        const node_array<int>& col,
                                        node v, node& u, node& w)
{ array<node> A(G.degree(v));

  int d = 0;
  node x;
  forall_adj_nodes(x,v)
      if (col[x] != -1) A[d++] = x;

  for(int i=0; i<d; i++)
  { u = A[i];
    for(int j=i+1; j<d; j++)
    { w = A[j];
      forall_adj_nodes(x,w) if (x == u) break;
      //G.init_adj_iterator(w);
      if (x != u) return;
     }
   }

  error_handler(1,"no independent neighbors found!");
  return;
 }

static int unused_adj_colors(node v, const node_array<int>& col)
{ int used[6];
  int c;
  for(c = 0; c < 6; c++) used[c] = 0;
  node x;
  forall_adj_nodes(x,v)
  { c = col[x];
    if (c != -1) used[c] = 1;
   }
  c = 0; 
  while(used[c]) c++;
  return c;
 }



void FIVE_COLOR(graph& G, node_array<int>& C)
{
  // G is a planar graph

  ugraph G1 = G;

  //we have to avoid parallel edges

  node_array<int>  C1(G1,0);       // C1[v] = color of node v in G1
  node_array<bool> mark(G1,false);
  node_array<int>  deg(G1);        // deg[v] = current degree of v

  list<node> small_deg;            // list of nodes with deg[v] <= 5
  node_array<list_item> I(G1,nil); // I[v] = location of v in small_deg

  node_array<list<node> > L(G1);   // L[v] = list of nodes of G represented by v

  stack<node>  removed;            // stack of (conceptually) removed nodes

  int N;                           // current number of valid nodes of G1


  // Initialization

  N = G1.number_of_nodes();

  node u,v,w,x;

  u = G.first_node();

  forall_nodes(v,G1)
  { deg[v] = G1.degree(v);
    if(deg[v] <= 5) I[v] = small_deg.append(v);
    L[v].append(u);
    u = G.succ_node(u);
   }

  // shrinking G1

  while (N > 0)
  {
    forall_nodes(v,G1)
    { int d = 0;
      forall_adj_nodes(x,v) if (C1[x] != -1) d++;
      if (C1[v] != -1 && deg[v] != d) 
        error_handler(1,string("N = %d  deg = %d   d = %d",N,deg[v],d));
     }

    if (small_deg.empty())
       error_handler(1,"smalldeg is empty");

    v = small_deg.pop();

    I[v] = nil;

    if (deg[v] == 5)
    {
      find_independent_neighbors(G1,C1,v,u,w);

      if (w == u) error_handler(1,"merging identical nodes"); //parallel edges

      forall_adj_nodes(x,u) mark[x] = true;

      forall_adj_nodes(x,w)
      { if (x == u) error_handler(1,"merging adjacent nodes");
        if (mark[x]) 
           { deg[x]--;
             if (deg[x] == 5) 
                I[x] = small_deg.append(x);
            }
        else
           { G1.new_edge(u,x);
             if (C1[x] != -1) deg[u]++;  
            }
       }

      forall_adj_nodes(x,u) mark[x] = false;

      deg[v]--;


      if (deg[u] > 5 && I[u] != nil)
      { small_deg.del(I[u]);
        I[u] = nil;
       }

      L[u].conc(L[w]);
     
      if (I[w] != nil) small_deg.del(I[w]);

      G1.del_node(w);

      N--;

    }

    //  now deg[v] <= 4

    C1[v] = -1;
    removed.push(v);

    forall_adj_nodes(x,v)
       if ( --deg[x] == 5) 
         I[x] = small_deg.append(x);

    N--;
   }

   // now color the nodes in "removed" from top to bottom

   while ( ! removed.empty() )
   { v = removed.pop();

     int c = unused_adj_colors(v,C1);

     if (c == 5) error_handler(1,"more than 5 different adjacent colors");

     C1[v] = c;
     forall(x,L[v]) C[x] = c;

    }

}


main() {

  graph G;

  GraphWin GW(G);

  GW.display();

  GW.set_node_label_type(no_label);
  GW.set_node_color(grey1);
  GW.set_flush(false);

  while (GW.edit()) {

    Delete_Loops(G);
    Make_Simple(G);
    GW.update_edges();

    if (!PLANAR(G)) 
    { GW.message("graph must be planar");
      continue;
     }

     node_array<int> col(G,0);

     FIVE_COLOR(G,col);

     node v;
     forall_nodes(v,G) GW.set_color(v,color(col[v]+2));
     GW.redraw();

  }

  return 0;
}
