/*******************************************************************************
+
+  LEDA 3.5
+
+  spanning_tree.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/plane_alg.h>
#include <LEDA/graph_alg.h>

extern list<edge> MIN_SPANNING_TREE(const graph&, 
                                    int(*cmp)(const edge&,const edge&));

static const GRAPH<POINT,int>* T_tmp;

static int cmp_edge_length(const edge& e1, const edge& e2)
{ COORD l1 = T_tmp->inf(source(e1)).sqr_dist(T_tmp->inf(target(e1))); 
  COORD l2 = T_tmp->inf(source(e2)).sqr_dist(T_tmp->inf(target(e2))); 
  return compare(l1,l2);
 }
  
void MIN_SPANNING_TREE(const list<POINT>& L, GRAPH<POINT,int>& T)
{ DELAUNAY_TRIANG(L,T);
  edge_array<bool> tree_edge(T,false);
  list<edge> E = MIN_SPANNING_TREE(T,cmp_edge_length);
  edge e;
  forall(e,E) 
  { tree_edge[e] = true;
    T[e] = 0;
   }
  E = T.all_edges();
  forall(e,E) 
     if (!tree_edge[e]) T.del_edge(e);
}


