Prim.H

# ifndef PRIM_H
# define PRIM_H

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

namespace Aleph {

using namespace Aleph;

    template <class GT> 
struct Prim_Info
{
  typename GT::Node * tree_node; // imagen en el árbol abarcador
  void *              heap_node; // puntero en el 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> 
struct Prim_Heap_Info
{
  typedef typename ArcHeap<GT, Distance, Prim_Heap_Info>::Node Node;

  Node *& operator () (typename GT::Node * p) 
  { 
    return (Node*&) HEAPNODE(p); 
  }
};

  template <class GT, class Distance> 
struct Simple_Prim_Heap
{
  typedef typename ArcHeap<GT, Distance, Simple_Prim_Heap>::Node Node;

  Node *& operator () (typename GT::Node * p) 
  { 
    return (Node*&) NODE_COOKIE(p); 
  }
};

    template <class GT> 
struct Init_Prim_Info
{
  GT & tree;

  Init_Prim_Info(GT & __tree) : tree(__tree) { /* empty */ }

  void operator () (GT & g, typename GT::Node * p)
  {
    g.reset_bit(p, Aleph::Prim); 
    NODE_COOKIE(p) = new Prim_Info<GT>;
    TREENODE(p) = tree.insert_node(p->get_info());
  }
};

    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 = Dft_Dist<GT>, 
           class SA       = Dft_Show_Arc<GT> > 
class Prim_Min_Spanning_Tree
{
  typedef Prim_Heap_Info<GT, Distance> Acc_Heap;

  typedef Simple_Prim_Heap<GT, Distance> Acc_Simple_Heap;

  typedef ArcHeap<GT, Distance, Acc_Heap> Heap;

  typedef ArcHeap<GT, Distance, Acc_Simple_Heap> Simple_Heap;

  Distance & dist;
  SA &       sa; 

public:

  Prim_Min_Spanning_Tree(Distance && __dist = Distance(),  
                         SA &&       __sa = SA())
    : dist(__dist), sa(__sa)
  {
    // empty
  }

  Prim_Min_Spanning_Tree(Distance & __dist, SA & __sa)
    : dist(__dist), sa(__sa)
  {
    // empty
  }

private:

  void paint_min_spanning_tree(GT & g, typename GT::Node * first)
  {
    if (g.is_digraph())
      throw std::domain_error("g is a digraph");

    g.reset_nodes();
    g.reset_arcs();

    NODE_BITS(first).set_bit(Aleph::Prim, true); // visitado

    Simple_Heap heap(dist, Acc_Simple_Heap());
    for (Out_Iterator<GT, SA> it(first, sa); it.has_curr(); it.next())
      {
        typename GT::Arc * arc = it.get_current_arc();
        heap.put_arc(arc, it.get_tgt_node());
      }

    const size_t V1 = g.get_num_nodes() - 1;
    size_t count = 0;

    while (count < V1 and not heap.is_empty()) 
      {     // obtenga siguiente menor arco 
        typename GT::Arc * min_arc = heap.get_min_arc();
        if (IS_ARC_VISITED(min_arc, Aleph::Prim))
          continue;

        ARC_BITS(min_arc).set_bit(Aleph::Prim, true);

        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 = 
          IS_NODE_VISITED(src, Aleph::Prim) ? tgt : src;

        NODE_BITS(tgt_node).set_bit(Aleph::Prim, true);

            // insertar en heap arcos no visitados de tgt_node
        for (Out_Iterator<GT, SA> it(tgt_node, sa); it.has_curr(); it.next())
          {
            typename GT::Arc * arc = it.get_current_arc();
            if (IS_ARC_VISITED(arc, Aleph::Prim))
              continue;

            typename GT::Node * tgt = it.get_tgt_node();
            if (IS_NODE_VISITED(tgt, Aleph::Prim)) 
              continue; // nodo visitado ==> causará ciclo 

            heap.put_arc(arc, tgt);
          }

        ++count;
        ARC_BITS(min_arc).set_bit(Aleph::Prim, true);
      }
  }

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

    clear_graph(tree); 

    Init_Prim_Info <GT> init(tree);
    Operate_On_Nodes <GT, Init_Prim_Info<GT>> () (g, init);

    NODE_BITS(first).set_bit(Aleph::Prim, true); // visitado

    Heap heap(dist, Acc_Heap()) ;
        // meter en heap arcos iniciales del primer nodo
    for (Out_Iterator<GT, SA> it(first, sa); it.has_curr(); it.next())
      {
        typename GT::Arc * arc = it.get_current_arc();
        heap.put_arc(arc, it.get_tgt_node());
      }

    const size_t V1 = g.get_num_nodes() - 1;

    while (tree.get_num_arcs() < V1 and not heap.is_empty()) 
      {     // obtenga siguiente menor arco 
        typename GT::Arc * min_arc = heap.get_min_arc();
        if (IS_ARC_VISITED(min_arc, Aleph::Prim))
          continue;

        ARC_BITS(min_arc).set_bit(Aleph::Prim, true);

        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 = 
          IS_NODE_VISITED(src, Aleph::Prim) ? tgt : src;

        NODE_BITS(tgt_node).set_bit(Aleph::Prim, true);

            // insertar en heap arcos no visitados de tgt_node
        for (Out_Iterator<GT, SA> it(tgt_node, sa); it.has_curr(); it.next())
          {
            typename GT::Arc * arc = it.get_current_arc();
            if (IS_ARC_VISITED(arc, Aleph::Prim))
              continue;

            typename GT::Node * tgt = it.get_tgt_node();
            if (IS_NODE_VISITED(tgt, Aleph::Prim)) 
              continue; // nodo visitado ==> causará ciclo 

            heap.put_arc(arc, tgt);
          }

            // insertar nuevo arco en tree y mapearlo
        typename GT::Arc * tree_arc = 
          tree.insert_arc(TREENODE(src), TREENODE(tgt), min_arc->get_info());
        GT::map_arcs(min_arc, tree_arc); 
      }

    Operate_On_Nodes <GT, Uninit_Prim_Info<GT> > () (g);   
  }

public:

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

  void operator () (GT & g, typename GT::Node * start, GT & tree) 
  {
    min_spanning_tree(g, start, tree);
  }

  void operator () (GT & g) 
  {
    paint_min_spanning_tree(g, g.get_first_node()); 
  }

  void operator () (GT & g, typename GT::Node * start) 
  {
    paint_min_spanning_tree(g, start); 
  }
};

   

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

# endif // PRIM_H