/*******************************************************************************
+
+  LEDA 7.2.3  
+
+
+  _five_color_c.c
+
+
+  Copyright (c) 1995-2026
+  by Algorithmic Solutions Software GmbH
+  All rights reserved.
+ 
*******************************************************************************/


#include <LEDA/graph/alg_five_color.h>

#include <LEDA/graph/graph_misc.h>
#include <LEDA/core/stack.h>
#include <LEDA/core/array.h>


LEDA_BEGIN_NAMESPACE

static void  find_independent_neighbors(const graph& 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;

  bool indep = false;

  for(int i=0; i<d; i++)
  { u = A[i];
    for(int j=i+1; j<d; j++)
    { w = A[j];
      indep = true;
      forall_adj_nodes(x,w) 
      { if (x == u) 
        { indep = false;
          break;
         }
       }
      if (indep) i = j = d;
     }
   }

  if (!indep)
    LEDA_EXCEPTION(1,"FIVE_COLOR: internal error (no independent neighbors).");
}



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 alg_five_color::operator()(const graph& G, node_array<int>& C) 
{
  start_event(*this);

  /*
    if (!PLANAR(G))
    LEDA_EXCEPTION(1,"FIVE_COLOR: graph must be planar.");
    */
  
  // we work on a copy G1 of G

  GRAPH<node,edge> G1;

  CopyGraph(G1,G);

  //  graph G1 = G;

  node v;
  node_array<node> v_in_G1(G);
  forall_nodes(v,G1) v_in_G1[G1[v]] = v;

  _node_copy = &v_in_G1;

  // remove loops and parallel edges
  Delete_Loops(G1);
  Make_Simple(G1);

  // eliminated reversals
  edge_array<edge> rev(G1);
  Is_Bidirected(G1,rev);
  edge e;
  forall_edges(e,G1) {
    if (rev[e] == nil) continue;
    edge r = rev[e];
    G1.del_edge(e);
    rev[r] = nil;
  }
   

  G1.make_undirected();


  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
  _merged_nodes = &L;

  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=0,w=0,x=0;

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

  // shrinking G1

  while (N > 0) {

//
//  forall_nodes(v,G1)
//  { int d = 0;
//    forall_adj_nodes(x,v) if (C1[x] != -1) d++;
//    assert(C1[v] == -1 || deg[v] == d); 
//   }
//


    if (small_deg.empty())
     LEDA_EXCEPTION(1,"FIVE_COLOR: no node with degree < 5 (graph not planar).");

    v = small_deg.pop();

    touch_node_event(*this,G1[v]);

    I[v] = nil;

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

      if (w == u) { 
	// parallel edges ?
        LEDA_EXCEPTION(1,"FIVE_COLOR: internal error (merging identical nodes)");
      }

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

      forall_adj_nodes(x,w) {
	if (x == u) 
         LEDA_EXCEPTION(1,string("FIVE_COLOR: internal error (merging adjacent nodes %d and %d  v = %d",G.index(u), G.index(w),G.index(v)));
        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]++;  
	}
      }

      merge_nodes_event(*this,G1[u],G1[w]);

      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--;
      
    }

    remove_node_event(*this,G1[v]);
    
    //  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) 
       LEDA_EXCEPTION(1,"FIVE_COLOR: internal error (more than 5 colors).");

     C1[v] = c;
     color_node_event(*this,G1[v],c);
     forall(x,L[v]) { C[x] = c; }
   }

   finish_event(*this);

}

alg_five_color FIVE_COLOR;


LEDA_END_NAMESPACE
