Prim.H

Go to the documentation of this file.

 
/*
                          Aleph_w
 
  Data structures & Algorithms
  version 2.0.0b
  https://github.com/lrleon/Aleph-w
 
  This file is part of Aleph-w library
 
  Copyright (c) 2002-2026 Leandro Rabindranath Leon
 
  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:
 
  The above copyright notice and this permission notice shall be included in all
  copies or substantial portions of the Software.
 
  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  SOFTWARE.
*/
 
 
# ifndef PRIM_H
# define PRIM_H
 
# include <tpl_agraph.H>
# include <tpl_graph_utils.H>
# include <archeap.H>
# include <ah-errors.H>
# include <cookie_guard.H>
 
namespace Aleph
{
  using namespace Aleph;
 
  template <class GT>
  struct Prim_Info
  {
    typename GT::Node *tree_node = nullptr; // imagen en el árbol abarcador
    void *heap_node = nullptr; // puntero en el heap exclusivo
 
    Prim_Info() : tree_node(nullptr), heap_node(nullptr)
    { /* 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
  {
    // Returns reference to the heap_node pointer stored in Prim_Info
    // The actual type is determined by ArcHeap, but stored as void*
    void *& operator ()(typename GT::Node *p)
    {
      return PRIMINFO(p)->heap_node;
    }
  };
 
  template <class GT, class Distance>
  struct Simple_Prim_Heap
  {
    // Returns reference to the cookie pointer used as heap node storage
    void *& operator ()(typename GT::Node *p)
    {
      return p->cookie;
    }
  };
 
  template <class GT>
  struct Init_Prim_Info
  {
    GT & tree;
 
    Init_Prim_Info(GT & __tree) : tree(__tree)
    { /* empty */
    }
 
    void operator ()(const GT & g, typename GT::Node *p)
    {
      g.reset_bit(p, Aleph::Spanning_Tree);
      NODE_COOKIE(p) = new Prim_Info<GT>;
      TREENODE(p) = tree.insert_node(p->get_info());
    }
  };
 
  template <class GT>
  struct Uninit_Prim_Info
  {
    void operator ()(const GT &, typename GT::Node *p)
    {
      const 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
    }
 
  private:
    void paint_min_spanning_tree(const GT & g, typename GT::Node *first)
    {
      ah_domain_error_if(g.is_digraph()) << "g is a digraph";
 
      g.reset_nodes();
      g.reset_arcs();
 
      NODE_BITS(first).set_bit(Aleph::Spanning_Tree, true); // visitado
 
      Simple_Heap heap(dist, Acc_Simple_Heap());
      for (Node_Arc_Iterator<GT, SA> it(first, sa); it.has_curr(); it.next_ne())
        {
          typename GT::Arc *arc = it.get_current_arc_ne();
          heap.put_arc(arc, it.get_tgt_node_ne());
        }
 
      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::Spanning_Tree))
            continue;
 
          ARC_BITS(min_arc).set_bit(Aleph::Spanning_Tree, 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::Spanning_Tree) and
              IS_NODE_VISITED(tgt, Aleph::Spanning_Tree))
            continue; // este arco cerraría un ciclo en el árbol
 
          typename GT::Node *tgt_node =
              IS_NODE_VISITED(src, Aleph::Spanning_Tree) ? tgt : src;
 
          NODE_BITS(tgt_node).set_bit(Aleph::Spanning_Tree, true);
 
          // insertar en heap arcos no visitados de tgt_node
          for (Node_Arc_Iterator<GT, SA> it(tgt_node, sa); it.has_curr();
               it.next_ne())
            {
              typename GT::Arc *arc = it.get_current_arc_ne();
              if (IS_ARC_VISITED(arc, Aleph::Spanning_Tree))
                continue;
 
              typename GT::Node *tgt = it.get_tgt_node_ne();
              if (IS_NODE_VISITED(tgt, Aleph::Spanning_Tree))
                continue; // nodo visitado ==> causará ciclo
 
              heap.put_arc(arc, tgt);
            }
 
          ++count;
          ARC_BITS(min_arc).set_bit(Aleph::Spanning_Tree, true);
        }
    }
 
    void min_spanning_tree(const GT & g, typename GT::Node *first, GT & tree)
    {
      ah_domain_error_if(g.is_digraph()) << "g is a digraph";
 
      clear_graph(tree);
 
      Init_Prim_Info<GT> init(tree);
      Operate_On_Nodes<GT, Init_Prim_Info<GT>>()(g, init);
      g.reset_arcs();
 
      // Scope guard for exception safety - ensures Uninit is always called
      Scope_Guard cleanup_guard(g, [](const GT & graph) {
        Operate_On_Nodes<GT, Uninit_Prim_Info<GT>>()(graph);
      });
 
      NODE_BITS(first).set_bit(Aleph::Spanning_Tree, true); // visitado
 
      Heap heap(dist, Acc_Heap());
      // meter en heap arcos iniciales del primer nodo
      for (Node_Arc_Iterator<GT, SA> it(first, sa); it.has_curr(); it.next_ne())
        {
          typename GT::Arc *arc = it.get_current_arc_ne();
          heap.put_arc(arc, it.get_tgt_node_ne());
        }
 
      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::Spanning_Tree))
            continue;
 
          ARC_BITS(min_arc).set_bit(Aleph::Spanning_Tree, 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::Spanning_Tree) and
              IS_NODE_VISITED(tgt, Aleph::Spanning_Tree))
            continue; // este arco cerraría un ciclo en el árbol
 
          typename GT::Node *tgt_node =
              IS_NODE_VISITED(src, Aleph::Spanning_Tree) ? tgt : src;
 
          NODE_BITS(tgt_node).set_bit(Aleph::Spanning_Tree, true);
 
          // insertar en heap arcos no visitados de tgt_node
          for (Node_Arc_Iterator<GT, SA> it(tgt_node, sa); it.has_curr();
               it.next_ne())
            {
              typename GT::Arc *arc = it.get_current_arc_ne();
              if (IS_ARC_VISITED(arc, Aleph::Spanning_Tree))
                continue;
 
              typename GT::Node *tgt = it.get_tgt_node_ne();
              if (IS_NODE_VISITED(tgt, Aleph::Spanning_Tree))
                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);
        }
 
      // cleanup_guard destructor will call Uninit_Prim_Info for all nodes
    }
 
  public:
    void operator ()(const GT & g, GT & tree)
    {
      min_spanning_tree(g, g.get_first_node(), tree);
    }
 
    void operator ()(const GT & g, typename GT::Node *start, GT & tree)
    {
      min_spanning_tree(g, start, tree);
    }
 
    void operator ()(const GT & g)
    {
      paint_min_spanning_tree(g, g.get_first_node());
    }
 
    void operator ()(const GT & g, typename GT::Node *start)
    {
      paint_min_spanning_tree(g, start);
    }
  };
 
 
# undef HEAPNODE
# undef TREENODE
# undef PRIMINFO
} // end namespace Aleph
 
# endif // PRIM_H