/*******************************************************************************
+
+  LEDA 3.5
+
+  _kuratowski.c
+
+  This file is part of the LEDA research version (LEDA-R) that can be 
+  used free of charge in academic research and teaching. Any commercial
+  use of this software requires a license which is distributed by the
+  LEDA Software GmbH, Postfach 151101, 66041 Saarbruecken, FRG
+  (fax +49 681 31104).
+
+  Copyright (c) 1991-1997  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 66123 Saarbruecken, Germany     
+  All rights reserved.
+ 
*******************************************************************************/
#include <LEDA/graph_alg.h>

static void dfs(const graph& G, node v, edge_array<bool>& marked,
                                        node_array<int>&  deg)
{ edge e;
  forall_inout_edges(e,v)
    if (marked[e])
    { marked[e] = false;
      node w = G.opposite(v,e);
      if (deg[w] == 2) dfs(G,w,marked,deg);
      else deg[w] = -3;
     }
}


int KURATOWSKI(graph& G, list<node>& V, list<edge>& E, node_array<int>& deg)
{ 
  // deg[v] = 0     not in Kuratowski Subdivison
  //          2     subdivison point
  //          3(-3) sides L(R) of K33
  //          4     nodes of K5

  if (PLANAR(G,E,false)) return 0;

  edge_array<bool> marked(G,false);
  deg.init(G,0);

  edge e;
  forall(e,E) 
  { marked[e] = true;
    if (++deg[source(e)] == 1) V.append(source(e));
    if (++deg[target(e)] == 1) V.append(target(e));
   }

  node v;
  forall(v,V)
    if (deg[v] == 3) 
    { dfs(G,v,marked,deg);
      return 1;
     }

  return 2;
}


