Prim.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 PRIM_H
# define PRIM_H

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

using namespace Aleph;

namespace Aleph {

template <class GT> struct Prim_Info
{
  typename GT::Node * tree_node; // imagen del nodo en el árbol abarcador
  void *              heap_node; // puntero dentro del heap exclusivo

  Prim_Info() : tree_node(NULL), heap_node(NULL) { /* empty */ } 
};
# define PRIMINFO(p) static_cast<Prim_Info<GT>*>(NODE_COOKIE(p))
# define TREENODE(p) (PRIMINFO(p)->tree_node)
# define HEAPNODE(p) (PRIMINFO(p)->heap_node)
      template <class GT, class Distance, class Compare>
struct Prim_Heap_Info
{
  typedef typename ArcHeap<GT, Distance, Compare, Prim_Heap_Info>::Node Node;
  
  Node *& operator () (typename GT::Node * p)
  {
    return (Node*&) HEAPNODE(p);
  }
};
    template <class GT>
struct Init_Prim_Info
{
  void operator () (GT & g, typename GT::Node * p)
  {
    g.reset_bit(p, Aleph::Prim); 
    NODE_COOKIE(p) = new Prim_Info<GT>;
  }
};
    template <class GT>
struct Uninit_Prim_Info
{
  void operator () (GT &, typename GT::Node * p)
  {
    Prim_Info<GT> * aux = PRIMINFO(p);
    GT::map_nodes(p, TREENODE(p));
    delete aux;
  }
};
    template <class GT, class Distance, class Compare> inline 
void prim_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 conected");
  tree.clear_graph(); 

  g.template operate_on_nodes <Init_Prim_Info <GT> > ();
  typedef Prim_Heap_Info<GT, Distance, Compare> Acc_Heap;
  ArcHeap<GT, Distance, Compare, Acc_Heap> heap;
      // inicializar la raíz con el primer nodo del grafo 
  typename GT::Node * first = g.get_first_node();
  NODE_BITS(first).set_bit(Aleph::Prim, true); // marcarlo visitado

      // guardar imagen de nodo en el árbol abarcador
  TREENODE(first) = tree.insert_node(first->get_info());

      // meter en heap arcos iniciales del primer nodo
  for (typename GT::Node_Arc_Iterator it(first); it.has_current(); it.next())
    {
      typename GT::Arc * arc = it.get_current_arc();
      ARC_BITS(arc).set_bit(Aleph::Prim, true);
      heap.put_arc(arc, it.get_tgt_node());
    }
  while (tree.get_num_nodes() < g.get_num_nodes()) // mientras tree no abarque a g
    {     // obtenga siguiente menor arco 
      typename GT::Arc * min_arc = heap.get_min_arc();

      typename GT::Node * src = g.get_src_node(min_arc);
      typename GT::Node * tgt = g.get_tgt_node(min_arc);

      if (IS_NODE_VISITED(src, Aleph::Prim) and 
          IS_NODE_VISITED(tgt, Aleph::Prim))
        continue; // Este arco cerraría un ciclo en el árbol 

      typename GT::Node * tgt_node = // seleccione nodo no marcado
        IS_NODE_VISITED(src, Aleph::Prim) ? tgt : src;

          // inserte en árbol, guarde node de árbol y marque nodo como visitado
      TREENODE(tgt_node) = tree.insert_node(tgt_node->get_info());
      NODE_BITS(tgt_node).set_bit(Aleph::Prim, true);

          // insertar en heap arcos no visitados de tgt_node
      for (typename GT::Node_Arc_Iterator it(tgt_node); it.has_current(); it.next())
        {
          typename GT::Arc * arc = it.get_current_arc();

          if (IS_ARC_VISITED(arc, Aleph::Prim))
            continue;

          ARC_BITS(arc).set_bit(Aleph::Prim, true); // marcar arco

          typename GT::Node * tgt = it.get_tgt_node();

          if (IS_NODE_VISITED(tgt, Aleph::Dijkstra)) 
            continue; // nodo visitado ==> causará ciclo ==> no se requiere
                      // insertar en heap  

          heap.put_arc(arc, tgt);
        }
            // inserte nuevo arco en tree
      typename GT::Arc * tree_arc = 
        tree.insert_arc(TREENODE(src), TREENODE(tgt), min_arc->get_info());

      GT::map_arcs(min_arc, tree_arc); // mapear arcos
    }
  g.template operate_on_nodes <Uninit_Prim_Info <GT> > ();      
}

    template <class GT, class Distance> inline 
void prim_min_spanning_tree(GT & g, GT & tree)
{
  prim_min_spanning_tree
    <GT, Distance, Aleph::less<typename Distance::Distance_Type> > (g, tree);
}


# undef HEAPNODE
# undef TREENODE
# undef PRIMINFO
} // end namespace Aleph

# endif // PRIM_H

---