graph_to_tree.H

# ifndef GRAPH_TO_TREE_H
# define GRAPH_TO_TREE_H

# include <tpl_tree_node.H>
# include <tpl_graph.H>
# include <tpl_graph_utils.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)
{ 
  if (not is_graph_acyclique<GT>(g))
    throw std::domain_error("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;

  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())
      {
        Arc * arc = it.get_current_arc();
        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)
  { 
    if (not is_graph_acyclique<GT>(g))
      throw std::domain_error("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 */ }

  Graph_To_Tree_Node(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_current(); it.next())
    {
      Arc * arc = it.get_current_arc();
      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