tpl_graph.H

/*
  This file is part of Aleph system

  Copyright (c) 2002, 2003, 2004, 2005, 2006
  UNIVERSITY LOS ANDES (ULA) Merida - REPÚBLICA BOLIVARIANA DE VENEZUELA  

  - Center of Studies in Microelectronics & Distributed Systems (CEMISID) 
  - ULA Computer Science Department
  - FUNDACITE Mérida - Ministerio de Ciencia y Tecnología

  PERMISSION TO USE, COPY, MODIFY AND DISTRIBUTE THIS SOFTWARE AND ITS
  DOCUMENTATION IS HEREBY GRANTED, PROVIDED THAT BOTH THE COPYRIGHT
  NOTICE AND THIS PERMISSION NOTICE APPEAR IN ALL COPIES OF THE
  SOFTWARE, DERIVATIVE WORKS OR MODIFIED VERSIONS, AND ANY PORTIONS
  THEREOF, AND THAT BOTH NOTICES APPEAR IN SUPPORTING DOCUMENTATION.

  Aleph is distributed in the hope that it will be useful, but WITHOUT
  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  or FITNESS FOR A PARTICULAR PURPOSE.

  UNIVERSIDAD DE LOS ANDES requests users of this software to return to 

  Leandro Leon
  CEMISID 
  Ed La Hechicera 
  3er piso, ala sur
  Facultad de Ingenieria 
  Universidad de Los Andes 
  Merida - REPÚBLICA BOLIVARIANA DE VENEZUELA    or

  lrleon@ula.ve

  any improvements or extensions that they make and grant Universidad 
  de Los Andes (ULA) the rights to redistribute these changes. 

  Aleph is (or was) granted by: 
  - Consejo de Desarrollo Cientifico, Humanistico, Tecnico de la ULA 
    (CDCHT)
  - Fundacite Mérida
*/


# ifndef TPL_GRAPH_H
# define TPL_GRAPH_H

# include <memory>
# include <bitArray.H>
# include <tpl_dynArray.H>
# include <tpl_sort_utils.H>
# include <tpl_dynMapTree.H>
# include <tpl_dynDlist.H>
# include <tpl_treapRk.H>

# define NODE_BITS(p)            ((p)->control_bits)

# define NODE_COUNTER(p)         ((p)->counter)

# define IS_NODE_VISITED(p, bit) (NODE_BITS(p).get_bit(bit))

# define NODE_COOKIE(p)          ((p)->cookie) 

# define ARC_COUNTER(p)          ((p)->counter)

# define ARC_BITS(p)             ((p)->control_bits)

# define IS_ARC_VISITED(p, bit)  (ARC_BITS(p).get_bit(bit))

# define ARC_COOKIE(p)           ((p)->cookie) 

using namespace Aleph;

namespace Aleph {

template <typename Node_Info> class Graph_Node; 

template <typename Arc_Info> class Graph_Arc; 

class Arc_Node;

template <typename GT> class Path;

template <typename __Graph_Node, typename __Graph_Arc> class List_Graph;

template <typename __Graph_Node, typename __Graph_Arc> class List_Digraph;

template <typename GT> class Mat_Graph;

template <typename MT, typename Entry_Info, typename Copy> class Ady_MaT;

static const long No_Visited = 0; // nodo o arco no ha sido visitado

enum Graph_Bits 
{
  Depth_First,   
  Breadth_First, 
  Test_Cycle,    
  Is_Acyclique,  
  Test_Path,     
  Find_Path,     
  Kruskal,       
  Prim,          
  Dijkstra,      
  Euler,         
  Hamilton,      
  Spanning_Tree, 
  Build_Subtree, 
  Convert_Tree,  
  Cut,           
  Min,           

  Num_Bits_Graph 

};
class Bit_Fields
{

public:

  unsigned int depth_first    : 1; 
  unsigned int breadth_first  : 1; 
  unsigned int test_cycle     : 1; 
  unsigned int is_acyclique   : 1; 
  unsigned int test_path      : 1; 
  unsigned int find_path      : 1; 
  unsigned int kruskal        : 1; 
  unsigned int prim           : 1; 
  unsigned int dijkstra       : 1; 
  unsigned int euler          : 1; 
  unsigned int hamilton       : 1; 
  unsigned int spanning_tree  : 1; 
  unsigned int build_subtree  : 1; 
  unsigned int convert_tree   : 1; 
  unsigned int cut            : 1; 
  unsigned int min            : 1; 

  Bit_Fields() 
    : depth_first(0), breadth_first(0), test_cycle(0), find_path(0), 
      kruskal(0), prim(0), dijkstra(0), euler(0), hamilton(0), 
      spanning_tree(0), build_subtree(0), convert_tree(0), cut(0), min(0)
  { /* empty */ }
  
  bool get_bit(const int & bit) const 

    throw(std::exception, std::out_of_range)

  {
    switch (bit)
      {
      case Aleph::Depth_First:   return depth_first;
      // ...

      case Aleph::Breadth_First: return breadth_first;
      case Aleph::Test_Cycle:    return test_cycle;
      case Aleph::Is_Acyclique:  return is_acyclique;
      case Aleph::Test_Path:     return test_path;
      case Aleph::Find_Path:     return find_path;
      case Aleph::Kruskal:       return kruskal;
      case Aleph::Prim:          return prim;
      case Aleph::Dijkstra:      return dijkstra;
      case Aleph::Euler:         return euler;
      case Aleph::Hamilton:      return hamilton;
      case Aleph::Spanning_Tree: return spanning_tree;
      case Aleph::Build_Subtree: return build_subtree;
      case Aleph::Convert_Tree:  return convert_tree;
      case Aleph::Cut:           return cut;
      case Aleph::Min:           return min;
      default:
        throw std::out_of_range("bit number out of range");

      }
  }
  void set_bit(const int & bit, const int & value) 
    {

      I(value == 0 or value == 1);

      switch (bit)
        {
        case Aleph::Depth_First:   depth_first   = value; break;
          // ...

        case Aleph::Breadth_First: breadth_first = value; break;
        case Aleph::Test_Cycle:    test_cycle    = value; break;
        case Aleph::Is_Acyclique:  is_acyclique  = value; break;
        case Aleph::Test_Path:     test_path     = value; break;
        case Aleph::Find_Path:     find_path     = value; break;
        case Aleph::Kruskal:       kruskal       = value; break;
        case Aleph::Prim:          prim          = value; break;
        case Aleph::Dijkstra:      dijkstra      = value; break;
        case Aleph::Euler:         euler         = value; break;
        case Aleph::Hamilton:      hamilton      = value; break;
        case Aleph::Spanning_Tree: spanning_tree = value; break;
        case Aleph::Build_Subtree: build_subtree = value; break;
        case Aleph::Convert_Tree:  convert_tree  = value; break;
        case Aleph::Cut:           cut           = value; break;
        case Aleph::Min:           min           = value; break;
        default:
          throw std::out_of_range("bit number out of range");

       }
    }
  void reset(const int & bit) { set_bit(bit, 0); }

  void reset()
  {
    depth_first   = 0; 
    breadth_first = 0; 
    test_cycle    = 0; 
    is_acyclique  = 0; 
    test_path     = 0; 
    find_path     = 0; 
    kruskal       = 0; 
    prim          = 0; 
    dijkstra      = 0; 
    euler         = 0; 
    hamilton      = 0; 
    spanning_tree = 0; 
    build_subtree = 0; 
    convert_tree  = 0;
    cut           = 0;
    min           = 0;
  }
};
    template <typename Node_Info> 
class Graph_Node : public Dlink
{

public:

  typedef Graph_Node Node;
  typedef Node_Info Node_Type; 
  friend class Arc_Node;
  Node_Info  node_info;
  Node_Info & get_info() { return node_info;} 
  size_t       num_arcs; 

  Graph_Node() : num_arcs(0), counter(No_Visited), cookie(NULL) { /* empty */ }

  Graph_Node(const Node_Info & info) 
    : node_info(info), num_arcs(0), counter(No_Visited), cookie(NULL) 
  { 
    /* empty */ 
  }

  Graph_Node(Graph_Node * node) 
    : node_info(node->get_info()), num_arcs(0), counter(No_Visited), cookie(NULL)
  { 
    /* empty */ 
  }
  Bit_Fields control_bits;
  long counter;
  void *     cookie; 
  Dlink arc_list; 
};
    template <typename Arc_Info> 
class Graph_Arc : public Dlink    
{

public:

  typedef Graph_Arc Arc; 
  typedef Arc_Info Arc_Type;
  Arc_Info   arc_info;
  Bit_Fields control_bits;
  long counter;
  void *     cookie; 
  void *     src_node; // nodo origen
  void *     tgt_node; // nodo destino
  Arc_Node * src_arc_node; // puntero al Arc_Node del nodo fuente
  Arc_Node * tgt_arc_node; // puntero al Arc_Node del nodo destino
  Arc_Info & get_info() { return arc_info; }
  void * get_connected_node(void * node) 
  {
    return src_node == node ? tgt_node : src_node;
  }

  Graph_Arc() 
    : counter(No_Visited), cookie(NULL),
      src_node(NULL), tgt_node(NULL), src_arc_node(NULL), tgt_arc_node(NULL)
  { 
    /* empty */ 
  }

  Graph_Arc(const Arc_Info & info) 
    : arc_info(info), counter(No_Visited), cookie(NULL),
      src_node(NULL), tgt_node(NULL), src_arc_node(NULL), tgt_arc_node(NULL)
  { 
    /* empty */ 
  }
  Graph_Arc(void * src, void * tgt, const Arc_Info & data) 
    : arc_info(data), counter(No_Visited), cookie(NULL),
      src_node(src), tgt_node(tgt), src_arc_node(NULL), tgt_arc_node(NULL)
  { 
    // empty
  }
};
struct Arc_Node : public Dlink
{
  void * arc;
  Arc_Node() : arc(NULL) { /* empty */ }
  Arc_Node(void * __arc) : arc(__arc) { /* empty */ }
};
    template <typename GT> 
class Path
{
  
  public:

    typedef typename GT::Node_Type Node_Type;
    typedef typename GT::Arc_Type Arc_Type;
  GT *                g;

  private:

    typedef typename GT::Node Node;
    typedef typename GT::Arc Arc;
  struct Path_Desc
  {
    Node * node; // nodo origen
    Arc *  arc;  // arco adyacente

    Path_Desc(Node * _node = NULL, Arc * _arc = NULL) : node(_node), arc(_arc) {}
  };
  DynDlist<Path_Desc> list;
  GT & get_graph() { return *g; }

  public:

  bool inside_graph(GT & gr) const { return g == &gr; }
  Path(GT & _g) : g(&_g) { /* empty */ }
  Path() : g(NULL) { /* empty */ }
  void init(Node * start_node)
  {
    list.append(Path_Desc(start_node));
  }
  Path(GT & _g, Node * start_node) : g(&_g)
  {
    init(start_node);
  }
  void set_graph(GT & __g, Node * start_node = NULL)
  {
    clear_path();

    g = &__g;

    if (start_node == NULL)
      return;

    init(start_node);
  }
  const long & size() const { return list.size(); }
  bool is_empty() const { return list.is_empty(); }
  void clear_path()
  {
    while (not list.is_empty())
      list.remove_first();
  }
  Path(const Path & path) : g(path.g), list(path.list) { /* empty */ }

  Path & operator = (const Path & path)
  {

    if (this == &path)
      return *this;

    clear_path();

    g = path.g;
    list = path.list;

    return *this;
  }
  void append(Arc * arc)
  {

    if (list.is_empty())
      throw std::domain_error("path is empty");

    Path_Desc & last_path_desc = list.get_last(); // ultimo elemento de list

    if (not g->node_belong_to_arc(arc, last_path_desc.node))
      throw std::invalid_argument("last node in path does "
                                  "not incide on arc");

    last_path_desc.arc = arc;

    list.append(Path_Desc(g->get_connected_node(arc, last_path_desc.node)));
  }
  void append(Node * node)
  {
    if (list.is_empty())
      {
        init(node);
        return;
      }

    Node * last_node = get_last_node();

    Arc * arc = g->search_arc(last_node, node); // busque arco last_node-node

    if (arc == NULL)
      throw std::domain_error("There is no arc connecting node");


    append(arc);
  }
  void insert(Arc * arc)
  {
    if (list.is_empty())
      throw std::domain_error("path is empty");

    Path_Desc & first_path_desc = list.get_first(); // ultimo elemento de list

    if (not g->node_belong_to_arc(arc, first_path_desc.node))
      throw std::invalid_argument("first node in path does "
                                  "not incide on arc");

    first_path_desc.arc = arc;

    list.insert(Path_Desc(g->get_connected_node(arc, first_path_desc.node)));
  }
  void insert(Node * node)
  {
    if (list.is_empty())
      {
        init(node);
        
        return;
      }

    Node * first_node = get_first_node();

    Arc * arc = g->search_arc(first_node, node); // busque arco last_node-node

    if (arc == NULL)
      throw std::domain_error("There is no arc connecting node");

    insert(arc);
  }
  Node * get_first_node() { return list.get_first().node; }
  Node * get_last_node() { return list.get_last().node; }
  Arc * get_first_arc() { return list.get_first().arc; }
  Arc * get_last_arc()
  {

    if (list.is_unitarian())
      throw std::domain_error("Path with only a node (without any arc");

    typename DynDlist<Path_Desc>::Iterator it(list);
    it.reset_last();
    it.prev();

    return it.get_current().arc; 
  }
  bool is_cycle() const { return get_first_node() == get_last_node(); }
  void remove_last_node()
  {
    list.remove_last();
    list.get_last().arc = NULL;
  }
  void remove_first_node()
  {
    list.remove_first();
  }
  void swap(Path & path)
  {
    Aleph::swap(g, path.g);
    list.swap(path.list);
  }
  class Iterator : public DynDlist<Path_Desc>::Iterator
  {

  public:

     // ...

    Iterator() { /* empty */ }

    Iterator(Path & path) : DynDlist<Path_Desc>::Iterator(path.list) { }

    Iterator(const Iterator & it) : DynDlist<Path_Desc>::Iterator(it) { }
      
    Iterator & operator = (const Iterator & it) 
    {
      DynDlist<Path_Desc>::Iterator::operator = (it);
      return *this;
    }

    Node * get_current_node() { return this->get_current().node; }

    Arc * get_current_arc() 
    { 

      if (this->is_in_last())
        throw std::overflow_error("Path iterator is in last node of path");

      return this->get_current().arc; 
    }
  };
  template <class Operation> void operate_on_nodes()
  {
    for (Iterator it(*this); it.has_current(); it.next())
      Operation () (it.get_current_node());
  }
  template <class Operation> void operate_on_arcs()
  {
    for (Iterator it(*this); it.has_current(); it.next())
      Operation () (it.get_current_arc());
  }
  template <class Operation> void operate_on_nodes(void * ptr)
  {
    for (Iterator it(*this); it.has_current(); it.next())
      Operation(ptr) (it.get_current_node());
  }

  template <class Operation> void operate_on_arcs(void * ptr)
  {
    for (Iterator it(*this); it.has_current(); it.next())
      Operation(ptr) (it.get_current_arc());
  }
}; 
    template <class GT> inline 
bool find_path_depth_first(GT&                 g, 
                           typename GT::Node * start_node, 
                           typename GT::Node * end_node,
                           Path<GT> &          path);
    template <class GT> inline static bool 
__find_path_depth_first(GT&                 g,  
                        typename GT::Node * curr_node, // nodo actual
                        typename GT::Arc *  curr_arc,  // arco procedencia
                        typename GT::Node * end_node,  // nodo destino
                        Path<GT> &          curr_path) // camino actual
{
  if (curr_node == end_node) // ¿se alcanzó nodo final?
    {     // sí, terminar añadir el arco y terminar
      curr_path.append(curr_arc);

      return true;
    }

  if (IS_NODE_VISITED(curr_node, Find_Path)) // ¿No ha sido visitado?
    return false; // sí ==> desde él no hay camino

  curr_path.append(curr_arc); // añadir curr_arc al camino

  NODE_BITS(curr_node).set_bit(Find_Path, true); // marcar nodo

      // buscar recursivamente a través de arcos de curr_node
  for (typename GT::Node_Arc_Iterator i(curr_node); i.has_current(); i.next())
    {
      typename GT::Arc * next_arc = i.get_current_arc();
      
      if (IS_ARC_VISITED(next_arc, Find_Path))
        continue; // ya se pasó por este arco 

      ARC_BITS(next_arc).set_bit(Find_Path, true); // marcar arco

      typename GT::Node * next_node = i.get_tgt_node(); 

          // continuamos exploración en profundidad desde next_node
      if (__find_path_depth_first <GT> (g, next_node, next_arc, 
                                        end_node, curr_path))

        {
          I(curr_path.get_last_node() == end_node);

        return true; // se encontró camino, terminar retornando true

        }

    }
      // no se encontró camino por curr_arc ==> eliminarlo de path
  curr_path.remove_last_node();

  return false;
}
    template <class GT> inline 
bool find_path_depth_first(GT&                 g, 
                           typename GT::Node * start_node, 
                           typename GT::Node * end_node,
                           Path<GT> &          path)
{

  if (not path.inside_graph(g))
    throw std::invalid_argument("Path does not belong to graph");

  path.clear_path();     // limpiamos path
  path.init(start_node); // insertamos nodo origen

  g.reset_bit_nodes(Find_Path);
  g.reset_bit_arcs(Find_Path); 

  NODE_BITS(start_node).set_bit(Find_Path, true); // marcar start_node visitado

      // explorar recursivamente cada arco de start_node
  for (typename GT::Node_Arc_Iterator i(start_node); i.has_current(); i.next())
    {
      typename GT::Arc * arc = i.get_current_arc();

          // marcar arco como visitado
      ARC_BITS(arc).set_bit(Find_Path, true); 

      typename GT::Node * next_node = i.get_tgt_node();

      if (IS_NODE_VISITED(next_node, Find_Path))
        continue; 

      if (__find_path_depth_first(g, next_node, arc, end_node, path))
        return true;
    }
  return false;
}
    template <typename __Graph_Node, typename __Graph_Arc>
class List_Graph
{

public:

  
  public:

  typedef __Graph_Node             Node;      
  typedef __Graph_Arc              Arc;       
  typedef typename Node::Node_Type Node_Type; 
  typedef typename Arc::Arc_Type   Arc_Type;

private:

  struct Reset_Node
  {
    void operator () (List_Graph&, Node * node)
    {
      node->control_bits.reset();
      node->counter = 0;
      node->cookie = NULL;
    }
  };
  struct Reset_Arc
  {
    void operator () (List_Graph&, Arc * arc)
    {
      arc->control_bits.reset();
      arc->counter = 0;
      arc->cookie = NULL;
    }
  };
  Dlink  node_list; // lista de nodos
  size_t num_nodes; // cantidad de nodos

  Dlink  arc_list;  // lista de arcos
  size_t num_arcs;  // cantidad de arcos
  static Node * dlink_to_node(Dlink * p)
  {
    return static_cast<Node*>(p);
  }
  static Arc * dlink_to_arc(Dlink * p)
  {
    return static_cast<Arc*>(p);
  }
  static Arc_Node * dlink_to_arc_node(Dlink * p)
  {
    return static_cast<Arc_Node*>(p);
  }
  static Arc * void_to_arc(Arc_Node * arc_node)
  {
    return static_cast<Arc*>(arc_node->arc); 
  }

  protected:

    bool digraph;

  private:

      template <class Cmp>
  struct Cmp_Arc
  {
    bool operator () (Dlink * d1, Dlink * d2) const
    {
      Arc * arc1 = dlink_to_arc(d1); // convertir dlink d1 de arco a Arc
      Arc * arc2 = dlink_to_arc(d2); // convertir dlink d2 de arco a Arc

          // al tener dos arcos invocamos a Cmp
      return Cmp () (arc1, arc2);
    }
  };

public:

  bool is_digraph() const;
  void verify_graphs(List_Graph & g);
  inline Node * insert_node(Node * node);
  inline Node * insert_node(const Node_Type & node_info);
  inline void remove_node(Node * node);
  inline Node * get_first_node();
  inline const size_t & get_num_nodes() const;
       template <class Equal>
  Node * search_node(const Node_Type & node_info);
  Node * search_node(const Node_Type & node_info);
  bool node_belong_to_graph(Node * node);
       template <class Equal>
  Node * search_node(void * ptr);
  template <class Operation> void operate_on_nodes()
  {
    for (Node_Iterator itor(*this); itor.has_current(); itor.next())
      Operation () (*this, itor.get_current_node());
  }

  template <class Operation> void operate_on_nodes(void * ptr)
  {
    for (Node_Iterator itor(*this); itor.has_current(); itor.next())
      Operation () (*this, itor.get_current_node(), ptr);
  }
  inline Node * get_src_node(Arc * arc);

  inline Node * get_tgt_node(Arc * arc);
  inline Node * get_connected_node(Arc * arc, Node * node);
  inline bool node_belong_to_arc(Arc * arc, Node * node) const;
  inline Arc * insert_arc(Node *                src_node, 
                          Node *                tgt_node, 
                          const typename Arc::Arc_Type & arc_info);
  inline void remove_arc(Arc * arc);
  inline Arc * get_first_arc();
  template <class Compare> inline void sort_arcs();
  inline const size_t & get_num_arcs() const;
  inline const size_t & get_num_arcs(Node * node) const;
        template <class Equal>
  Arc * search_arc(const Arc_Type & arc_info);

  Arc * search_arc(const Arc_Type & arc_info);
  bool arc_belong_to_graph(Arc * arc);
  Arc * search_arc(Node * src_node, Node * tgt_node);
      template <class Equal>
  Arc * search_arc(void * ptr);
  template <class Operation> void operate_on_arcs()
  {
    for (Arc_Iterator itor(*this); itor.has_current(); itor.next())
      Operation () (*this, itor.get_current_arc());
  }

  template <class Operation> void operate_on_arcs(void * ptr)
  {
    for (Arc_Iterator itor(*this); itor.has_current(); itor.next())
      Operation () (*this, itor.get_current_arc(), ptr);
  }

  template <class Operation> void operate_on_arcs(Node * node)
  {
    for (Node_Arc_Iterator it(node); it.has_current(); it.next())
      Operation () (*this, it.get_current_arc());
  }

  template <class Operation> void operate_on_arcs(Node * node, void * ptr)
  {
    for (Node_Arc_Iterator it(node); it.has_current(); it.next())
      Operation () (*this, it.get_current_arc(), ptr);
  }

  inline Bit_Fields & get_control_bits(Node * node);
  inline void reset_bit(Node * node, const int & bit);
  inline void set_bit(Node * node, const int & bit, const int & value);
  inline Bit_Fields & get_control_bits(Arc * arc);
  inline void reset_bit(Arc * arc, const int & bit);
  inline void set_bit(Arc * arc, const int & bit, const int & value);
  void reset_bit_nodes(const int & bit)
  {
    for (Node_Iterator itor(*this); itor.has_current(); itor.next())
      reset_bit(itor.get_current_node(), bit);
  }
  void reset_bit_arcs(const int & bit)
  {
    for (Arc_Iterator itor(*this); itor.has_current(); itor.next())
      reset_bit(itor.get_current_arc(), bit);
  }
  inline long & get_counter(Node * node);
  inline void reset_counter(Node * node);
  inline long & get_counter(Arc * arc);
  inline void reset_counter(Arc * arc);
  void reset_counter_nodes()
  {
    for (Node_Iterator itor(*this); itor.has_current(); itor.next())
      reset_counter(itor.get_current_node());
  }
  void reset_counter_arcs()
  {
    for (Arc_Iterator itor(*this); itor.has_current(); itor.next())
      reset_counter(itor.get_current_arc());
  }
  inline void *& get_cookie(Node * node);
  inline void *& get_cookie(Arc * arc);
  void reset_cookie_nodes()
  {
    for (Node_Iterator itor(*this); itor.has_current(); itor.next())
      itor.get_current_node().cookie = NULL;
  }
  void reset_cookie_arcs()
  {
    for (Arc_Iterator itor(*this); itor.has_current(); itor.next())
      itor.get_current_arc().cookie = NULL;
  }
  static void map_nodes(Node * p, Node * q);

  static void map_arcs(Arc * p, Arc * q);
  inline void reset_node(Node * node);

  inline void reset_arc(Arc * arc);
  void reset_nodes()
  {
    operate_on_nodes <Reset_Node> ();
  }
  void reset_arcs()
  {
    operate_on_arcs <Reset_Arc> ();
  }
  inline List_Graph();
  inline List_Graph(const List_Graph & g);
  inline List_Graph& operator = (List_Graph & g);
  inline virtual ~List_Graph();
  inline List_Graph(List_Digraph<Node, Arc> & g);
  inline List_Graph & operator = (List_Digraph<Node, Arc> & g);
  void copy_graph(List_Graph & src_graph, const bool cookie_map = false);
  inline void clear_graph();
  class Node_Iterator : public Dlink::Iterator
  {

  public:

    Node_Iterator() { /* empty */ }
    Node_Iterator(List_Graph & _g);
    Node_Iterator(const Node_Iterator & it); 
    Node_Iterator & operator = (const Node_Iterator & it);
    Node * get_current_node(); 
  };
  class Node_Arc_Iterator : public Dlink::Iterator
  {
    Node * src_node; 

  public:

    inline Node_Arc_Iterator();
    inline Node_Arc_Iterator(Node * _src_node);
    inline Node_Arc_Iterator(const Node_Arc_Iterator & it);
    inline Node_Arc_Iterator & operator = (const Node_Arc_Iterator & it);
    inline Arc * get_current_arc();
    inline Node * get_tgt_node();
    Arc_Node * get_current_arc_node() 
    {
      return dlink_to_arc_node(get_current());
    }
  };
  class Arc_Iterator : public Dlink::Iterator
  {

  public:

    Arc_Iterator() { /* empty */ }
    Arc_Iterator(List_Graph & _g);
    Arc_Iterator(const Arc_Iterator & it);
    Arc_Iterator & operator = (const Arc_Iterator & it);
    Arc * get_current_arc();
  };
};
    template <typename Node_Info, typename Arc_Info>
class List_Digraph : public List_Graph<Node_Info, Arc_Info>
{

public:

  List_Digraph();
  List_Digraph(const List_Digraph & dg);
  List_Digraph & operator = (List_Digraph & dg);
};
    template <class GT>
void invert_digraph(GT & sg, GT & rg)
{

  if (not sg.is_digraph())
    throw std::domain_error("sg is not a digraph");

  if (not rg.is_digraph())
    throw std::domain_error("rg is not a digraph");

  rg.clear_graph();
  sg.reset_nodes();

      // recorrer todos los arcos del digrafo sg
  for (typename GT::Arc_Iterator it(sg); it.has_current(); it.next())
    {
      typename GT::Arc * arc = it.get_current();

      typename GT::Node * ssrc = sg.get_src_node(arc); // procesar nodo origen
      typename GT::Node * rsrc = NODE_COOKIE(ssrc);
      if (rsrc == NULL) // ¿ya está creado ssrc en rg?
        {     // no == crearlo, insertarlo y mapearlo
           auto_ptr<typename GT::Node> rsrc_auto(new typename GT::Node(ssrc));

          sg.insert_node(rsrc_auto.get());
          GT::map_nodes(ssrc, rsrc_auto.get());
          rsrc = rsrc_auto.release(); 
        }

      typename GT::Node * stgt = sg.get_tgt_node(arc); // procesar nodo destino
      typename GT::Node * rtgt = NODE_COOKIE(stgt);
      if (rtgt == NULL) // ¿ya está creado ssrc en rg?
        {     // no == crearlo, insertarlo y mapearlo
           auto_ptr<typename GT::Node> rtgt_auto(new typename GT::Node(stgt));

          sg.insert_node(rtgt_auto.get());
          GT::map_nodes(stgt, rtgt_auto.get());
          rtgt = rtgt_auto.release(); 
        }

      rg.insert_arc(rtgt, rsrc, arc->get_info());
    }
}
   template <typename Node, typename Arc>
const size_t & List_Graph<Node, Arc>::get_num_nodes() const 
{
  return num_nodes; 
}
   template <typename Node, typename Arc>
const size_t & List_Graph<Node, Arc>::get_num_arcs() const 
{
  return num_arcs; 
}
   template <typename Node, typename Arc>
Node * List_Graph<Node, Arc>::get_first_node() 
{

  if (num_nodes == 0)
    throw std::range_error("Graph has not nodes");

  return dlink_to_node(node_list.get_next());
}

   template <typename Node, typename Arc>
Arc * List_Graph<Node, Arc>::get_first_arc() 
{

  if (get_num_arcs() == 0)
    throw std::range_error("Graph has not arcs");

  return dlink_to_arc(arc_list.get_next());
}
   template <typename Node, typename Arc>
List_Graph<Node, Arc>::Node_Iterator::Node_Iterator(List_Graph<Node, Arc> & _g)
  : Dlink::Iterator(&_g.node_list)
{
  // empty
}

   template <typename Node, typename Arc>
List_Graph<Node, Arc>::Node_Iterator::Node_Iterator
   (const List_Graph<Node, Arc>::Node_Iterator & it)
     : Dlink::Iterator(it)
{
  // empty
}

   template <typename Node, typename Arc>
typename List_Graph<Node, Arc>::Node_Iterator & 
List_Graph<Node, Arc>::Node_Iterator::operator = 
   (const typename List_Graph<Node, Arc>::Node_Iterator & it) 
{
  Dlink::Iterator::operator = (it);
      
  return *this;
}

    template <typename Node, typename Arc>
Node * List_Graph<Node, Arc>::Node_Iterator::get_current_node() 
{
  return dlink_to_node(get_current()); 
}
   template <typename Node, typename Arc>
List_Graph<Node, Arc>::Arc_Iterator::Arc_Iterator(List_Graph<Node, Arc> & _g) 
  : Dlink::Iterator(&_g.arc_list)
{
  // empty
}

   template <typename Node, typename Arc>
List_Graph<Node, Arc>::Arc_Iterator::Arc_Iterator
   (const List_Graph<Node, Arc>::Arc_Iterator::Arc_Iterator & it) 
     : Dlink::Iterator(it)
{
  // empty
}

       template <typename Node, typename Arc>
   typename List_Graph<Node, Arc>::Arc_Iterator & 
List_Graph<Node, Arc>::Arc_Iterator::operator = 
       (const List_Graph<Node, Arc>::Arc_Iterator & it) 
{
  Dlink::Iterator::operator = (it);

  return *this;
}

   template <typename Node, typename Arc>
Arc * List_Graph<Node, Arc>::Arc_Iterator::get_current_arc() 
{
  return dlink_to_arc(get_current()); 
}
    template <typename Node, typename Arc>
    template <class Equal>
Node * List_Graph<Node, Arc>::search_node
      (const typename Node::Node_Type & node_info)
{
  for (Node_Iterator itor(*this); itor.has_current(); itor.next())
    {
      Node * current_node = itor.get_current_node();
        
      if (Equal() (current_node->get_info(), node_info))
        return current_node;
    }
  return NULL;
}
    template <typename Node, typename Arc>
Node * List_Graph<Node, Arc>::search_node
  (const typename Node::Node_Type & node_info)
{
  return search_node<Aleph::equal_to<typename Node::Node_Type> >(node_info);
}

    template <typename Node, typename Arc>
bool List_Graph<Node, Arc>::node_belong_to_graph(Node * node)
{
  for (Node_Iterator itor(*this); itor.has_current(); itor.next())
    {
      Node * current_node = itor.get_current_node();
        
      if (current_node == node)
        return true;
    }

  return false;
}

    template <typename Node, typename Arc>
    template <class Equal>
Node * List_Graph<Node, Arc>::search_node(void * ptr)
{
  for (Node_Iterator itor(*this); itor.has_current(); itor.next())
    {
      Node * curr_node = itor.get_current_node();
        
      if (Equal () (curr_node, ptr))
        return curr_node;
    }

  return NULL;
}
    template <typename Node, typename Arc>
    template <class Equal>
    Arc *
 List_Graph<Node, Arc>::search_arc(const typename Arc::Arc_Type & arc_info)
{
  for (Arc_Iterator it(*this); it.has_current(); it.next())
    {
      Arc * current_arc = it.get_current_arc();
        
      if (Equal() (current_arc->get_info(), arc_info))
        return current_arc;
    }    
  return NULL; 
}

   template <typename Node, typename Arc>
bool List_Graph<Node, Arc>::arc_belong_to_graph(Arc * arc) 
{
  for (Arc_Iterator it(*this); it.has_current(); it.next())
    if (it.get_current_arc() == arc)
      return true;

  return false;
}

   template <typename Node, typename Arc> 
   Arc * 
List_Graph<Node, Arc>::search_arc(const typename Arc::Arc_Type & arc_info)
{
  return search_arc<Aleph::equal_to<Arc_Type> >(arc_info);
}

    template <typename Node, typename Arc>
    template <class Equal>
Arc * List_Graph<Node, Arc>::search_arc(void * ptr)
{
  for (Arc_Iterator itor(*this); itor.has_current(); itor.next())
    {
      Arc * curr_arc = itor.get_current_node();
        
      if (Equal () (curr_arc, ptr))
        return curr_arc;
    }

  return NULL;
}
   template <typename Node, typename Arc>
Node * List_Graph<Node, Arc>::get_src_node(Arc * arc) 
{
  return static_cast<Node*>(arc->src_node); 
}
   template <typename Node, typename Arc>
Node * List_Graph<Node, Arc>::get_tgt_node(Arc * arc) 
{ 
  return static_cast<Node*>(arc->tgt_node); 
}
   template <typename Node, typename Arc>
bool List_Graph<Node, Arc>::node_belong_to_arc(Arc *  arc, 
                                               Node * node) const
{
  return node == arc->src_node or node == arc->tgt_node;
}
   template <typename Node, typename Arc>
Node * List_Graph<Node, Arc>::get_connected_node(Arc * arc, Node * node) 
{
  return static_cast<Node*>(arc->get_connected_node(node));
}
   template <typename Node, typename Arc>
void List_Graph<Node, Arc>::verify_graphs(List_Graph<Node, Arc> & g)
{
  if (digraph and not g.digraph)
    throw std::domain_error("List_Graph and List_Digraph combined");
}
   template <typename Node, typename Arc>
bool List_Graph<Node, Arc>::is_digraph() const { return digraph; }
   template <typename Node, typename Arc>
List_Graph<Node, Arc>::Node_Arc_Iterator::Node_Arc_Iterator() : src_node(NULL) 
{
  /* empty */ 
}

   template <typename Node, typename Arc>
List_Graph<Node, Arc>::Node_Arc_Iterator::Node_Arc_Iterator(Node * _src_node) 
  : Dlink::Iterator(&(_src_node->arc_list)), src_node(_src_node)
{
  // empty
}

   template <typename Node, typename Arc>
List_Graph<Node, Arc>::Node_Arc_Iterator::Node_Arc_Iterator
   (const List_Graph<Node, Arc>::Node_Arc_Iterator& it) 
     : Dlink::Iterator(it), src_node(it.src_node) 
{ 
  // empty 
}
            
    template <typename Node, typename Arc>
  typename List_Graph<Node, Arc>::Node_Arc_Iterator & 
List_Graph<Node, Arc>::Node_Arc_Iterator::operator = 
   (const Node_Arc_Iterator& it) 
{
  Dlink::Iterator::operator = (it);

  src_node = it.src_node;

  return *this;
}

   template <typename Node, typename Arc>
Arc * List_Graph<Node, Arc>::Node_Arc_Iterator::get_current_arc() 
{
  return static_cast<Arc*>(get_current_arc_node()->arc);
}

   template <typename Node, typename Arc>
Node * List_Graph<Node, Arc>::Node_Arc_Iterator::get_tgt_node() 
{ 
  return static_cast<Node*>(get_current_arc()->get_connected_node(src_node));
}
   template <typename Node, typename Arc>
Arc * List_Graph<Node, Arc>::search_arc(Node * src_node, Node * tgt_node) 
{

  I(src_node != NULL and tgt_node != NULL);

  Node_Arc_Iterator itor;
    
  Node * searched_node;

      // Seleccionar el nodo que contenga menor cantidad de arcos
  if (digraph or src_node->num_arcs < tgt_node->num_arcs)
    {
      searched_node = tgt_node;
      itor = Node_Arc_Iterator(src_node);
    }
  else
    {
      searched_node = src_node;
      itor = Node_Arc_Iterator(tgt_node);
    }

      // recorrer lista de arcos del nodo en búsqueda de searched_node 
  for (/* nada */; itor.has_current(); itor.next())
    if (itor.get_tgt_node() == searched_node)
      return itor.get_current_arc();

  return NULL; 
}
    template <typename Node, typename Arc>
Node * List_Graph<Node, Arc>::insert_node(Node * node)
{
  ++num_nodes;
  node_list.append(node);

  return node;
}
    template <typename Node, typename Arc>
Node * List_Graph<Node, Arc>::insert_node
  (const typename Node::Node_Type & node_info)
{
  return insert_node( new Node (node_info) );
}
   template <typename Node, typename Arc> Arc * 
List_Graph<Node, Arc>::insert_arc(Node *                         src_node, 
                                  Node *                         tgt_node, 
                                  const typename Arc::Arc_Type & arc_info)
{
      // paso (1): apartar memoria para Arc e iniciar
  auto_ptr<Arc> arc ( new Arc  ); // apartar memoria para arco 
  arc->src_node   = src_node;     // Iniciar sus campos
  arc->tgt_node   = tgt_node;
  arc->get_info() = arc_info;
          
      // paso (3) (parcial): apartar memoria para el Arc_Node del nodo
      // origen src_node  
  auto_ptr<Arc_Node> src_arc_node ( new Arc_Node (arc.get()) );
      
      // Paso (2): si es un grafo ==> apartar memoria para el Arc_Node
      // del nodo destino tgt_node
  if (not digraph) // si es digrafo ==> no hay que insertar en el otro nodo
    {     // inserción en nodo destino 
      if (src_node == tgt_node) // verificar si se trata de un ciclo
        arc->tgt_arc_node = src_arc_node.get(); /* este es un ciclo */
      else
        {     // apartar arco nodo para tgt_node 
          auto_ptr<Arc_Node> tgt_arc_node ( new Arc_Node (arc.get()) ); 

              // inserción en lista de adyacencia de nodo destino tgt_node
          arc->tgt_arc_node = tgt_arc_node.get();    
          tgt_node->arc_list.append(tgt_arc_node.get());
          tgt_node->num_arcs++;
          tgt_arc_node.release(); // desbloquear auto-puntero tgt_arc_node
        }
    }
      // paso (3) (resto) inserción en lista de adyacencia de nodo
      // origen src_node 
  arc->src_arc_node = src_arc_node.get();
  src_node->arc_list.append(src_arc_node.get());
  src_node->num_arcs++;

      // Paso (4) insertar arco en lista de arcos del grafo 
  arc_list.append(arc.get());
  ++num_arcs;

      // desbloquear auto-punteros y terminar
  src_arc_node.release(); // desbloquear tgt_arc_node

  return arc.release();   // desbloquear arc
}
   template <typename Node, typename Arc>
void List_Graph<Node, Arc>::remove_arc(Arc * arc)
{
      // paso (1): eliminación del Arc_node del nodo origen src_node
  Node * src_node = get_src_node(arc); 
  Arc_Node * src_arc_node = arc->src_arc_node;
  src_arc_node->del();   // desenlaza src_node de la lista de nodos
  src_node->num_arcs--;  // decrementa contador de arcos de src_node
  delete src_arc_node;   // entrega memoria

  if (not digraph) 
    {     // eliminación arco en nodo destino 
      Node * tgt_node = get_tgt_node(arc); 

      if (src_node != tgt_node) // verificar eliminación de ciclo 
        {  // paso (2): eliminación del Arc_node del nodo destino tgt_node
          Arc_Node * tgt_arc_node = arc->tgt_arc_node;
          tgt_arc_node->del(); 
          tgt_node->num_arcs--;
          delete tgt_arc_node;
        }
    }
      // eliminación de arco del grafo 
  arc->del(); // desenlazar arc de la lista de arcos del grafo
  --num_arcs;
  delete arc;
}
   template <typename Node, typename Arc>
void List_Graph<Node, Arc>::remove_node(Node * node)
{
      // Eliminar todos los arcos adyacentes a node
  while (not node->arc_list.is_empty()) // repita mientras aún hayan arcos
    {     // obtener el Arc_Node
      Arc_Node * arc_node = dlink_to_arc_node(node->arc_list.get_next());

      Arc * arc = void_to_arc(arc_node); // obtener el arco

      remove_arc(arc); // eliminarlo del grafo
    }
      // en este punto el nodo ya no tiene arcos

  node->del(); // desenlazar nodo de lista de nodos del grafo
  --num_nodes;

  delete node; 
}
   template <typename Node, typename Arc>
void List_Graph<Node, Arc>::clear_graph()
{
      // recorrer cada nodo del grafo a través de la lista de nodos
  for (Dlink::Iterator node_itor(&node_list); node_itor.has_current(); )
    {     // obtener nodo a borrar
      Node * p = dlink_to_node(node_itor.get_current()); 

          // avanzar antes de borrar para que iterador permanezca consistente
      node_itor.next();

      remove_node(p); // eliminarlo del grafo
    }

  I(num_nodes == 0 and num_arcs == 0);

}
   template <typename Node, typename Arc>
void List_Graph<Node, Arc>::map_nodes(Node * p, Node * q)
{

  I(p != NULL and q != NULL);

  if (NODE_COOKIE(p) == NULL)
    {
      NODE_COOKIE(p) = q;
      NODE_COOKIE(q) = p;
      return;
    }

  NODE_COOKIE(q) = NODE_COOKIE(p);
  NODE_COOKIE(p) = q;
}

   template <typename Node, typename Arc>
void List_Graph<Node, Arc>::map_arcs(Arc * p, Arc * q)
{

  I(p != NULL and q != NULL);

  if (ARC_COOKIE(p) == NULL)
    {
      ARC_COOKIE(p) = q;
      ARC_COOKIE(q) = p;
      return;
    }

  ARC_COOKIE(q) = ARC_COOKIE(p);
  ARC_COOKIE(p) = q;
}
   template <typename Node, typename Arc>
void List_Graph<Node, Arc>::copy_graph(List_Graph<Node, Arc> & src_graph,
                                       const bool              cookie_map)
{

  IG(not is_digraph() and src_graph.is_digraph(), 
     is_digraph() != src_graph.is_digraph());

  verify_graphs(src_graph);

  try
    {

      clear_graph(); // limpiar this antes de copiar

      DynMapAvlTree<Node*, Node*> mapping_table;  

          // Fase (1): recorrer nodos de grafo src_graph e insertar copia en this
      for (Node_Iterator it(src_graph); it.has_current(); it.next())
        {
          Node * src_node = it.get_current_node(); 

          auto_ptr<Node> tgt_node(new Node(src_node)); // hacer una copia

          mapping_table.insert(src_node, tgt_node.get()); // insertar en mapeo

          Node * tgt = tgt_node.release();

          insert_node(tgt); // insertarla en grafo destino

          if (cookie_map)
            map_nodes(src_node, tgt);
        }

      I(get_num_nodes() == src_graph.get_num_nodes());

          // fase (2): para cada arco de src_graph, crear en this un
          // arco que conecte a los nodos mapeados de mapping_table
          // insertados en la fase anterior 
      for (Arc_Iterator it(src_graph); it.has_current(); it.next())
        {
          Arc * src_arc = it.get_current_arc();

              // obtener imágenes de nodos en el grafo destino 
          Node * src_node = mapping_table[src_graph.get_src_node(src_arc)]; 
          Node * tgt_node = mapping_table[src_graph.get_tgt_node(src_arc)];

              // insertar arco en grafo destino
          Arc * tgt_arc = insert_arc(src_node, tgt_node, src_arc->get_info()); 
          
          if (cookie_map)
            map_arcs(src_arc, tgt_arc);
        }

      I(get_num_arcs() == src_graph.get_num_arcs());
    }
  catch (...)
    {     // Si ocurre excepción se limpia this 
      clear_graph(); 
      throw;
    }

}
   template <typename Node, typename Arc>
List_Graph<Node, Arc>::List_Graph() : num_nodes(0), num_arcs(0), digraph(false)
{
  /* empty */ 
}
    template <typename Node, typename Arc>
List_Digraph<Node, Arc>::List_Digraph() 
{
  List_Graph<Node, Arc>::digraph = true;
}
   template <typename Node, typename Arc>
List_Graph<Node, Arc>::List_Graph(const List_Graph<Node, Arc> & g) 
  : num_nodes(0), num_arcs(0), digraph(false)
{
  copy_graph(const_cast<List_Graph<Node, Arc> &>(g));
}
   template <typename Node, typename Arc>
List_Digraph<Node, Arc>::List_Digraph
   (const List_Digraph<Node, Arc>::List_Digraph & dg) 
     : List_Graph<Node, Arc>(dg)
{
  List_Graph<Node, Arc>::digraph = true; 
}

   template <typename Node, typename Arc>
List_Graph<Node, Arc> & List_Graph<Node, Arc>::operator = 
  (List_Graph<Node, Arc> & g)
{
  if (this == &g)
    return *this;

  copy_graph(const_cast<List_Graph<Node, Arc> &>(g));

  return *this;
}

   template <typename Node, typename Arc>
List_Digraph<Node, Arc> & List_Digraph<Node, Arc>::operator = 
   (List_Digraph<Node, Arc>::List_Digraph & dg)
{
  return List_Graph<Node, Arc>::operator = (dg);
}
   template <typename Node, typename Arc>
List_Graph<Node, Arc>::~List_Graph() 
{
  clear_graph(); 
}
   template <typename Node, typename Arc>
   template <class Compare>
void List_Graph<Node, Arc>::sort_arcs()
{
  mergesort < Cmp_Arc <Compare> > (arc_list);
}
   template <typename Node, typename Arc>
const size_t & List_Graph<Node, Arc>::get_num_arcs(Node * node) const 
{
  return node->num_arcs; 
}

   template <typename Node, typename Arc>
void List_Graph<Node, Arc>::reset_bit(Node * node, const int & bit) 
{
  node->control_bits.reset(bit); 
}

   template <typename Node, typename Arc>
Bit_Fields & List_Graph<Node, Arc>::get_control_bits(Node * node)
{
  return node->control_bits; 
}

   template <typename Node, typename Arc>
void List_Graph<Node, Arc>::set_bit(Node *      node,
                                    const int & bit, 
                                    const int & value) 
{
  node->control_bits.set_bit(bit, value);
}

   template <typename Node, typename Arc>
long & List_Graph<Node, Arc>::get_counter(Node * node) 
{
  return node->counter; 
}

   template <typename Node, typename Arc>
void List_Graph<Node, Arc>::reset_counter(Node * node)
{
  node->counter = No_Visited; 
}

   template <typename Node, typename Arc>
void *& List_Graph<Node, Arc>::get_cookie(Node * node) 
{
  return node->cookie; 
}

   template <typename Node, typename Arc>
void List_Graph<Node, Arc>::reset_node(Node * node)
{
  node->control_bits.reset(); 
  node->counter = 0;
  node->cookie  = NULL;
}
   template <typename Node, typename Arc>
void List_Graph<Node, Arc>::reset_bit(Arc * arc, const int & bit) 
{
  arc->control_bits.reset(bit); 
}

   template <typename Node, typename Arc>
Bit_Fields & List_Graph<Node, Arc>::get_control_bits(Arc * arc) 
{
  return arc->control_bits; 
}

   template <typename Node, typename Arc>
void List_Graph<Node, Arc>::set_bit(Arc *       arc, 
                                    const int & bit, 
                                    const int & value) 
{
  arc->control_bits.set_bit(bit, value);
}

   template <typename Node, typename Arc>
long & List_Graph<Node, Arc>::get_counter(Arc * arc) 
{
  return arc->counter; 
}

   template <typename Node, typename Arc>
void List_Graph<Node, Arc>::reset_counter(Arc * arc) 
{
  arc->counter = No_Visited; 
}

   template <typename Node, typename Arc>
void *& List_Graph<Node, Arc>::get_cookie(Arc * arc) 
{
  return arc->cookie; 
}

   template <typename Node, typename Arc>
void List_Graph<Node, Arc>::reset_arc(Arc * arc)
{
  arc->control_bits.reset(); 
  arc->counter = 0;
  arc->cookie  = NULL;
}

} // end namespace Aleph

# endif /* TPL_GRAPH_H */

---