Aleph-w: Algoritmos y estructuras de datos

---

Kruskal.H

/*
  This file is part of Aleph-w system

  Copyright (c) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
  Leandro Rabindranath León
  All rights reserved.

  Redistribution and use in source and binary forms, with or without
  modification, are permitted provided that the following conditions are
  met: 
  1. Redistributions of source code must retain the above copyright 
     notice, this list of conditions and the following disclaimer.
  2. Redistributions in binary form must reproduce the above copyright 
     notice, this list of conditions and the following disclaimer in the 
     documentation and/or other materials provided with the distribution.
  3. All advertising materials mentioning features or use of this software
     must display the following acknowledgement:

     Copyright (c) 2002-2011 Leandro Rabindranath León. See details of 
     licence.     

     This product includes software developed by the Hewlett-Packard
     Company, Free Software Foundation and Silicon Graphics Computer
     Systems, Inc. 
  4. Neither the name of the <organization> nor the
     names of its contributors may be used to endorse or promote products
     derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY <COPYRIGHT HOLDER> ''AS IS'' AND ANY
EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED. IN NO EVENT SHALL <COPYRIGHT HOLDER> BE LIABLE FOR ANY
DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

  Aleph-w 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.

  I request users of this software to return to 

  Leandro Rabindranath 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
  leandro.r.leon@gmail.com

  any improvements or extensions that they make and grant me the rights
  to redistribute these changes.  
*/

# ifndef KRUSKAL_H
# define KRUSKAL_H

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

using namespace Aleph;

namespace Aleph {

  
 template <class GT, class Distance, 
       class Compare = Aleph::less<typename Distance::Distance_Type>, 
       class SA      = Default_Show_Arc<GT> > 
class Kruskal_Min_Spanning_Tree 
{
  Distance & dist;
  Compare &  cmp;
  SA      &  sa;
  
public:

  Kruskal_Min_Spanning_Tree(Distance && __dist = Distance(),  
                Compare &&  __cmp  = Compare(),
                SA &&       __sa   = SA()) 
    : dist(__dist), cmp(__cmp), sa(__sa) 
  { 
    /* empty */ 
  }

  Kruskal_Min_Spanning_Tree(Distance & __dist, Compare &  __cmp, SA & __sa) 
    : dist(__dist), cmp(__cmp), sa(__sa)  
  { 
    /* empty */ 
  }

private:

  void min_spanning_tree(GT & g, GT & tree)
  {
    if (g.is_digraph())
      throw std::domain_error("g is a digraph");

    g.reset_bit_nodes(Aleph::Kruskal); // limpiar bits de marcado
    clear_graph(tree); // limpia grafo destino 

    typedef Distance_Compare<GT, Distance, Compare> DCMP;
    DCMP comp(dist, cmp);
    g.template sort_arcs<DCMP>(comp);

        // Recorrer arcos ordenados de g hasta que numero de arcos de
        // tree sea igual al numero de nodos de g 
    for (Arc_Iterator<GT, SA> arc_itor(g, sa);       
     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); // origen en g
    typename GT::Node * tree_src_node; // 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 = mapped_node<GT>(g_src_node);

    typename GT::Node * g_tgt_node = g.get_tgt_node(arc);
    typename GT::Node * tree_tgt_node; // 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 = mapped_node<GT>(g_tgt_node);

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

    if (Has_Cycle<GT, SA> (sa) (tree)) // ¿arc_in_tree causa ciclo?
      {     // hay ciclo ==> hay que remover el arco
        tree.remove_arc(arc_in_tree); // eliminar arco y procesar 
        continue;                     // siguiente arco
      }

    GT::map_arcs(arc, arc_in_tree);
      }
  }

public:

  void operator () (GT & g, GT & tree) 
  {
    min_spanning_tree (g, tree);
  }
};
      

} // end namespace Aleph

# endif // KRUSKAL_H

---