graph_to_tree.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 GRAPH_TO_TREE_H
# define GRAPH_TO_TREE_H
 
# include <tpl_tree_node.H>
# include <tpl_graph.H>
# include <tpl_graph_utils.H>
 # include <ah-errors.H>
 
namespace Aleph {
 
    template <class GT, typename Key, class Convert> static
Tree_Node<Key> * graph_to_tree_node(GT & g, typename GT::Node * groot);
    template <class GT, typename Key, class Convert> static void 
__graph_to_tree_node(GT & g, typename GT::Node * groot, 
                     Tree_Node<Key> * troot);
 
  template <class GT, typename Key, typename Convert, class SA> static inline
void __graph_to_tree_node(GT & g, typename GT::Node * groot,
                          Tree_Node<Key> * troot);
 
    template <class GT, typename Key, 
              class Convert, class SA = Dft_Show_Arc<GT>> inline
Tree_Node<Key> * graph_to_tree_node(GT & g, typename GT::Node * groot)
{ 
  ah_domain_error_if(not is_graph_acyclique<GT>(g))
    << "Graph is not a tree (not acyclique)";
 
  Tree_Node<Key> * troot = new Tree_Node<Key>; // apartar memoria raíz
 
  Convert () (groot, troot); //convertir de groot y copiar a troot
 
  __graph_to_tree_node <GT, Key, Convert, SA> (g, groot, troot);
 
  return troot;
}
 
    template <class GT, typename Key, 
        class Convert, 
        class SA = Dft_Show_Arc<GT> > 
class Graph_To_Tree_Node
{
  SA        sa;
  Convert * convert = nullptr;
 
  void graph_to_tree(typename GT::Node * groot, Tree_Node<Key> * troot)
  {           
    typedef typename GT::Node Node;
    typedef typename GT::Arc Arc;
 
        // recorrer arcos de groot y construir recursivamente
    for (Node_Arc_Iterator<GT, SA> it(groot, sa); it.has_curr(); it.next_ne())
      {
  Arc * arc = it.get_current_arc_ne();
  if (IS_ARC_VISITED(arc, Convert_Tree)) 
    continue;
 
  ARC_BITS(arc).set_bit(Convert_Tree, true); // arc visitado 
  Node * gtgt = it.get_tgt_node();
  Tree_Node<Key> * ttgt = new Tree_Node<Key>; 
 
  (*convert) (gtgt, ttgt); // asignarle la clave
 
  troot->insert_rightmost_child(ttgt); // insertarlo como hijo 
 
  graph_to_tree(gtgt, ttgt);
      }
  }
 
  Tree_Node<Key> * graph_to_tree(GT & g,
         typename GT::Node * groot,
         Convert & conv)
  { 
    ah_domain_error_if(not is_graph_acyclique<GT>(g))
      << "Graph is not a tree (not acyclique)";
 
    Tree_Node<Key> * troot = new Tree_Node<Key>; // apartar memoria raíz
 
    convert = &conv;
 
    (*convert) (groot, troot); //convertir de groot y copiar a troot
 
    graph_to_tree(groot, troot);
 
    return troot;
  }
 
public:
 
  Graph_To_Tree_Node(SA __sa = SA()) : sa(__sa) { /* empty */ }
 
      Tree_Node<Key> * 
  operator () (GT & g, typename GT::Node * groot, Convert && conv = Convert())
  { 
    return graph_to_tree(g, groot, conv);
  }
 
      Tree_Node<Key> * 
  operator () (GT & g, typename GT::Node * groot, Convert & conv)
  { 
    return graph_to_tree(g, groot, conv);
  }
};
 
 
  template <class GT, typename Key, typename Convert, class SA> static inline
void __graph_to_tree_node(GT & g, typename GT::Node * groot,
                          Tree_Node<Key> * troot)
{           
  typedef typename GT::Node Node;
  typedef typename GT::Arc Arc;
 
      // recorrer arcos de groot y construir recursivamente
  for (Node_Arc_Iterator<GT, SA> it(groot); it.has_curr(); it.next_ne())
    {
      Arc * arc = it.get_current_arc_ne();
      if (IS_ARC_VISITED(arc, Convert_Tree)) 
        continue;
 
      ARC_BITS(arc).set_bit(Convert_Tree, true); // arc visitado 
      Node * gtgt = it.get_tgt_node();
      Tree_Node<Key> * ttgt = new Tree_Node<Key>; 
 
      Convert () (gtgt, ttgt); // asignarle la clave
 
      troot->insert_rightmost_child(ttgt); // insertarlo como hijo 
 
      __graph_to_tree_node <GT, Key, Convert, SA> (g, gtgt, ttgt);
    }
}
 
} // end namespace Aleph
 
# endif // GRAPH_TO_TREE_H