Kruskal.H

/*
  This file is part of Aleph system

  Copyright (c) 2002, 2003, 2004, 2005, 2006
  UNIVERSITY LOS ANDES (ULA) Merida - REPÚBLICA BOLIVARIANA DE VENEZUELA  

  - Center of Studies in Microelectronics & Distributed Systems (CEMISID) 
  - ULA Computer Science Department
  - FUNDACITE Mérida - Ministerio de Ciencia y Tecnología

  PERMISSION TO USE, COPY, MODIFY AND DISTRIBUTE THIS SOFTWARE AND ITS
  DOCUMENTATION IS HEREBY GRANTED, PROVIDED THAT BOTH THE COPYRIGHT
  NOTICE AND THIS PERMISSION NOTICE APPEAR IN ALL COPIES OF THE
  SOFTWARE, DERIVATIVE WORKS OR MODIFIED VERSIONS, AND ANY PORTIONS
  THEREOF, AND THAT BOTH NOTICES APPEAR IN SUPPORTING DOCUMENTATION.

  Aleph is distributed in the hope that it will be useful, but WITHOUT
  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  or FITNESS FOR A PARTICULAR PURPOSE.

  UNIVERSIDAD DE LOS ANDES requests users of this software to return to 

  Leandro Leon
  CEMISID 
  Ed La Hechicera 
  3er piso, ala sur
  Facultad de Ingenieria 
  Universidad de Los Andes 
  Merida - REPÚBLICA BOLIVARIANA DE VENEZUELA    or

  lrleon@ula.ve

  any improvements or extensions that they make and grant Universidad 
  de Los Andes (ULA) the rights to redistribute these changes. 

  Aleph is (or was) granted by: 
  - Consejo de Desarrollo Cientifico, Humanistico, Tecnico de la ULA 
    (CDCHT)
  - Fundacite Mérida
*/

# ifndef KRUSKAL_H
# define KRUSKAL_H

# include <ahFunction.H>
# include <tpl_graph.H>
# include <tpl_graph_utils.H>

using namespace Aleph;

namespace Aleph {

    template <class GT, class Distance, class Compare> inline 
void kruskal_min_spanning_tree(GT & g, GT & tree)
{

  if (g.is_digraph())
    throw std::domain_error("g is a digraph");

  if (not test_connectivity(g))
    throw std::invalid_argument("Input graph is not connected");

  g.reset_bit_nodes(Aleph::Kruskal); // limpiar bits de marcado

  tree.clear_graph(); // limpia grafo destino 

  g.template sort_arcs<Distance_Compare<GT, Distance, Compare> >();
    // Recorrer arcos ordenados de g hasta que numero de arcos de tree sea
    // igual a numero de nodos de g 
  for (typename GT::Arc_Iterator arc_itor(g);       
       tree.get_num_arcs() < g.get_num_nodes() - 1; arc_itor.next()) 
    {     // obtenga siguiente menor arco
      typename GT::Arc * arc = arc_itor.get_current_arc();

      typename GT::Node * g_src_node = g.get_src_node(arc); // nodo origen en g

      typename GT::Node * tree_src_node; // nodo origen en tree

      if (not IS_NODE_VISITED(g_src_node, Aleph::Kruskal)) // ¿está en tree?
        {     // No, crearlo en tree, atarlo al cookie y marcar como visitado
          NODE_BITS(g_src_node).set_bit(Aleph::Kruskal, true); 
          tree_src_node = tree.insert_node(g_src_node->get_info());
          GT::map_nodes(g_src_node, tree_src_node);
        }
       else
         tree_src_node = static_cast<typename GT::Node*>(NODE_COOKIE(g_src_node));
      typename GT::Node * g_tgt_node = g.get_tgt_node(arc);
      typename GT::Node * tree_tgt_node; // Nodo destino en árbol abarcador
      if (not IS_NODE_VISITED(g_tgt_node, Aleph::Kruskal))
        {     // No, crearlo en tree, atarlo al cookie y marcar como visitado
          NODE_BITS(g_tgt_node).set_bit(Aleph::Kruskal, true); 
          tree_tgt_node = tree.insert_node(g_tgt_node->get_info());
          GT::map_nodes(g_tgt_node, tree_tgt_node);
        }
       else
         tree_tgt_node = static_cast<typename GT::Node*>(NODE_COOKIE(g_tgt_node));

      typename GT::Arc * arc_in_tree = 
        tree.insert_arc(tree_src_node, tree_tgt_node, arc->get_info());

      if (has_cycle(tree)) // verifique si nuevo arco causa un ciclo
        {     // hay ciclo ==> hay que remover el arco
          tree.remove_arc(arc_in_tree); // eliminar arco e ir a procesar 
          continue;                     // siguiente arco
        }
      GT::map_arcs(arc, arc_in_tree);
    }
}

    template <class GT, class Distance> inline 
void kruskal_min_spanning_tree(GT & g, GT & tree)
{
  typedef typename Distance::Distance_Type DT;

  kruskal_min_spanning_tree<GT, Distance, Aleph::less<DT> > (g, tree);
}


} // end namespace Aleph

# endif // KRUSKAL_H

---