tpl_test_acyclique.H

# ifndef TPL_TEST_ACYCLIQUE_H
# define TPL_TEST_ACYCLIQUE_H

namespace Aleph {



      template <class GT, class SA = Dft_Show_Arc<GT>> 
class Is_Graph_Acyclique
{
  SA & sa;

  bool is_acyclique(typename GT::Node * curr)
  {
    if (IS_NODE_VISITED(curr, Is_Acyclique)) 
      return false;

    NODE_BITS(curr).set_bit(Is_Acyclique, true); // marcar nodo

    for (Node_Arc_Iterator<GT, SA> i(curr, sa); i.has_current(); i.next())
      {
        typename GT::Arc * arc = i.get_current_arc();
        if (IS_ARC_VISITED(arc, Is_Acyclique)) 
          continue; 

        ARC_BITS(arc).set_bit(Is_Acyclique, true); 

        if (not is_acyclique(i.get_tgt_node())) 
          return false;
      }

    // todos los arcos recorridos sin encontrar ciclo ==>
    // el grafo es acíclico pasando por curr_node
    return true; 
  }

  bool is_acyclique(GT & g, size_t num_arcs)
  {
    if (g.is_digraph())
      throw std::domain_error("is_graph_acyclique() does not work for digraps");

    if (num_arcs >= g.get_num_nodes()) 
      return false; 

    g.reset_bit_arcs(Is_Acyclique);
    g.reset_bit_nodes(Is_Acyclique);

    for (typename GT::Node_Iterator it(g); it.has_current(); it.next()) 
    {
      typename GT::Node * curr = it.get_current_node();
      if (IS_NODE_VISITED(curr, Is_Acyclique)) 
        continue; 

      if (not is_acyclique(curr)) 
        return false;
    }

  return true;
}

public:
  
  Is_Graph_Acyclique(SA && __sa = SA()) : sa(__sa) { /* empty */ }

  Is_Graph_Acyclique(SA & __sa) : sa(__sa) { /* empty */ }

  bool operator () (GT & g, size_t num_arcs) 
  {
    return is_acyclique(g, num_arcs);
  }

  bool operator () (GT & g) 
  {
    return is_acyclique(g, g.get_num_arcs());
  }
};

      template <class GT, class SA = Dft_Show_Arc<GT>> 
class Has_Cycle
{
  SA & sa;

public:

  Has_Cycle(SA && __sa = SA()) : sa(__sa) { /* empty */ }

  Has_Cycle(SA & __sa) : sa(__sa) { /* empty */ }

  bool operator () (GT & g) const
  {
    return not Is_Graph_Acyclique <GT, SA> (sa) (g);
  }

  bool operator () (GT & g, size_t num_arcs) const
  {
    return not Is_Graph_Acyclique <GT, SA> (sa) (g, num_arcs);
  }
};




} // end namespace Aleph

# endif //  TPL_TEST_ACYCLIQUE_H