/*******************************************************************************
+
+  LEDA 3.5
+
+  _spanning.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.
+ 
*******************************************************************************/

//------------------------------------------------------------------------------
// Spanning Trees 
//                                                                              
// S. N"aher (1989)
//------------------------------------------------------------------------------


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


list<edge> SPANNING_TREE(const graph& G)
{ 
  list<edge>     EL;
  node_partition P(G);

  edge e;
  forall_edges(e,G)
  { node v = G.source(e);
    node w = G.target(e);
    if (! P.same_block(v,w))
    { EL.append(e);
      P.union_blocks(v,w);
     }
   }

  return EL;
}


//------------------------------------------------------------------------------
// Variant of Kruskal's Algorithm using a compare function
//------------------------------------------------------------------------------

list<edge> MIN_SPANNING_TREE(const graph& G, 
                             int (*cmp)(const edge&, const edge&))
{ 
  list<edge> T;
  node_partition P(G);

  list<edge> L= G.all_edges();
  L.sort(cmp);

  edge e;
  forall(e,L)
  { node v = source(e);
    node w = target(e);
    if (! P.same_block(v,w))
    { T.append(e);
      P.union_blocks(v,w);
     }
   }
 
  return T;
}

