tpl_graph_try.H

# 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>
# include <tpl_aleph_graph.H>
# include <filter_iterator.H>

    
using namespace Aleph;

namespace Aleph {

template <typename Node_Info> class Graph_Node; 

template <typename Arc_Info> class Graph_Arc; 

class Arc_Node;

    template <class GT> 
class Path;

    template <typename __Graph_Node, typename __Graph_Arc> 
class List_Graph;

    template <typename __Graph_Node, typename __Graph_Arc> 
class List_Digraph;

    template <class GT> 
class Mat_Graph;

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


    template <typename __Node_Info = Empty_Class> 
class Graph_Node : public Dlink, Aleph_Graph_Node<__Node_Info>
{
  friend class Arc_Node;

  typedef Aleph_Graph_Node<__Node_Info> Base_Node;

public:

  typedef __Node_Info Node_Info;

  Graph_Node()
    : Base_Node()
  {
    // Empty
  }

  Graph_Node(const Graph_Node & node)
    : Base_Node(node)
  {
    // Empty
  }

  Graph_Node(Graph_Node && node)
    : Base_Node(std::move(node))
  {
    // Empty
  }

  Graph_Node(const Node_Info & info)
    : Base_Node(info)
  { 
    // Empty
  }

  Graph_Node(Node_Info && info)
    : Base_Node(std::move(info))
  { 
    // Empty
  }

  Graph_Node(Graph_Node * node)
    : Base_Node(node)
  { 
    // Empty
  }

  Dlink arc_list; 
};

    template <typename __Arc_Info = Empty_Class> 
class Graph_Arc : public Dlink, Aleph_Graph_Arc<__Arc_Info> 
{
  typedef Aleph_Graph_Arc<__Arc_Info> Base_Arc;

public:
  typedef __Arc_Info Arc_Info;

  Arc_Node * src_arc_node; // puntero al Arc_Node del nodo fuente
  Arc_Node * tgt_arc_node; // puntero al Arc_Node del nodo destino

  Graph_Arc() 
    : src_arc_node(NULL), tgt_arc_node(NULL)
  { 
    // Empty
  }

  Graph_Arc(const Arc_Info & info) 
    : Base_Arc(info), src_arc_node(NULL), tgt_arc_node(NULL)
  { 
    // Empty
  }

  Graph_Arc(Arc_Info && info) 
    : Base_Arc(std::move(info)), src_arc_node(NULL), tgt_arc_node(NULL)
  { 
    // Empty
  }

  Graph_Arc(void * src, void * tgt, const Arc_Info & info) 
    : Base_Arc(src, tgt, info), src_arc_node(NULL), tgt_arc_node(NULL)
  { 
    // Empty
  }

  Graph_Arc(void * src, void * tgt, Arc_Info && info) 
    : Base_Arc(src, tgt, std::move(info)),
      src_arc_node(NULL), tgt_arc_node(NULL)
  { 
    // Empty
  }

  Graph_Arc(void * src, void * tgt) 
    : Base_Arc(src, tgt), src_arc_node(NULL), tgt_arc_node(NULL)
  { 
    // Empty
  }
};

struct Arc_Node : public Dlink
{
  void * arc;
  Arc_Node() : arc(NULL) {}
  Arc_Node(void * __arc) : arc(__arc) {}
}; 

  template <typename __Graph_Node = Graph_Node<int>,
            typename __Graph_Arc  = Graph_Arc<int>>
class List_Graph : public Aleph_Graph <__Graph_Node, __Graph_Arc>
{
public:
  typedef __Graph_Node Node;
  typedef __Graph_Arc Arc;
  typedef typename Node::Node_Info Node_Type;
  typedef typename Arc::Arc_Info Arc_Type;

private:
  typedef Aleph_Graph <__Graph_Node, __Graph_Arc> Base_Graph;

  Dlink  node_list; // lista de nodos
  Dlink  arc_list;  // lista de arcos

  static Node * dlink_to_node(Dlink * p) { return (Node*) p; }

  static Arc * dlink_to_arc(Dlink * p) { return (Arc*) p; }

  static Arc_Node * dlink_to_arc_node(Dlink * p) { return (Arc_Node*) p; }

  static Arc * void_to_arc(Arc_Node * arc_node) 
  {
    return (Arc*) arc_node->arc; 
  }


      template <class Cmp>
  struct Cmp_Arc
  {
    Cmp & cmp;

    Cmp_Arc(Cmp && __cmp = Cmp()) : cmp(__cmp) { /* empty */ }

    Cmp_Arc(Cmp & __cmp) : cmp(__cmp) { /* empty */ }

    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
      return cmp(arc1, arc2); // al tener dos arcos invocamos a Cmp
    }
  };

public:
  
  inline virtual Node * insert_node(Node * node);

  inline virtual Node * insert_node(const Node_Type & node_info);


  inline virtual Node * insert_node(Node_Type && node_info = Node_Type());

  inline virtual void remove_node(Node * node);

  inline Node * get_first_node();

  inline Arc * get_first_arc(Node *);

      inline virtual Arc * 
  insert_arc(Node * src_node, Node * tgt_node, 
             const typename Arc::Arc_Type & arc_info);

      inline virtual Arc * 
  insert_arc(Node * src_node, Node * tgt_node, 
             typename Arc::Arc_Type && arc_info);

  inline virtual Arc * insert_arc(Node * src_node, Node * tgt_node);

  inline virtual void remove_arc(Arc * arc); 

  inline virtual void disconnect_arc(Arc * arc); 

  inline virtual Arc * connect_arc(Arc * arc);

  inline Arc * get_first_arc();

      template <class Compare> inline 
  void sort_arcs(Compare && cmp = Compare());

      template <class Compare> inline
  void sort_arcs(Compare & cmp);

  GRAPH_SEARCH_METHODS;

  inline List_Graph(const List_Graph & g);

  inline List_Graph(List_Graph && g);

  inline List_Graph & operator = (const List_Graph & g);

  inline List_Graph & operator = (List_Graph && g);

  inline virtual ~List_Graph();

  class Node_Iterator : public Dlink::Iterator
  {
  public:

    typedef Node * Item_Type;

    typedef List_Graph Set_Type;

    Node_Iterator() { /* empty */ }

    inline Node_Iterator(List_Graph & _g);

    inline Node * get_current_node(); 

    Node * get_current() { return get_current_node(); }

    Node * get_curr() { return get_current_node(); }
  };

  class Node_Arc_Iterator : public Dlink::Iterator
  {
    Node * src_node; 
    
  public:

    typedef Arc * Item_Type;

    typedef Node * Set_Type;

    Node_Arc_Iterator() { /* empty */ }

    Node_Arc_Iterator(Node * src) 
      : Dlink::Iterator(&(src->arc_list)), src_node(src)
    {
      // empty 
    }

    inline Arc * get_current_arc();

    Arc * get_current() { return get_current_arc(); }

    Arc * get_curr() { return get_current_arc(); }

    inline Node * get_tgt_node();

    Arc_Node * get_current_arc_node() 
    {
      return dlink_to_arc_node(Dlink::Iterator::get_current()); 
    }
  };

  class Arc_Iterator : public Dlink::Iterator
  {
  public:

    typedef Arc * Item_Type;

    typedef List_Graph Set_Type;

    Arc_Iterator() { /* empty */ }

    inline Arc_Iterator(List_Graph & _g);

    Arc * get_current_arc();

    Arc * get_current() { return get_current_arc(); }  

    Arc * get_curr() { return get_current_arc(); }  

    Node * get_src_node() { return (Node*) get_current_arc()->src_node; }

    Node * get_tgt_node() { return (Node*) get_current_arc()->tgt_node; }
  };

  GRAPH_ITERATIVE_METHODS;
  
  List_Graph()
    : Base_Graph(false)
  { 
    // Empty
  }

  void swap(List_Graph & g)
  {
    common_swap(g);
    node_list.swap(&g.node_list);
    arc_list.swap(&g.arc_list);
  }
};


    template <class GT>
struct Dft_Show_Arc
{
  bool operator () (typename GT::Arc * /* arc */) const
  { 
    return true; 
  }
};


    template <class GT, class SA1, class SA2>
class Double_SA
{
  SA1 & sa1;
  SA2 & sa2;
  typename GT::Node * s;

public:

  Double_SA(SA1 && __sa1 = SA1(), SA2 && __sa2 = SA2()) 
    : sa1(__sa1) , sa2(__sa2) 
  {
    /* empty */ 
  }

  Double_SA(SA1 & __sa1, SA2 & __sa2) 
    : sa1(__sa1) , sa2(__sa2) 
  {
    /* empty */ 
  }

  Double_SA(SA1 & __sa1, SA2 && __sa2 = SA2()) 
    : sa1(__sa1) , sa2(__sa2) 
  {
    /* empty */ 
  }

  Double_SA(SA1 && __sa1, SA2 & __sa2) 
    : sa1(__sa1) , sa2(__sa2) 
  {
    /* empty */ 
  }

  bool operator () (typename GT::Arc * a)
  {
    return sa1(a) and sa2(a);
  }
};

    template <class GT, class Show_Arc = Dft_Show_Arc<GT>>
class Node_Arc_Iterator : 
      public Filter_Iterator<typename GT::Node*, 
                             typename GT::Node_Arc_Iterator,
                             Show_Arc>
{
  typedef Filter_Iterator<typename GT::Node*, 
                          typename GT::Node_Arc_Iterator,
                          Show_Arc> Filter_Itor;
public:

      typedef Filter_Iterator
  <typename GT::Node*, typename GT::Node_Arc_Iterator, Show_Arc> Itor;

  typedef typename Itor::Item_Type Item_Type;

  typedef typename Itor::Set_Type Set_Type;

  Node_Arc_Iterator() { /* empty */ }

  Node_Arc_Iterator(typename GT::Node * p, Show_Arc && sa = Show_Arc()) 
    : Itor(p, std::move(sa)) 
  {
    // empty
  }

  Node_Arc_Iterator(typename GT::Node * p, Show_Arc & sa) 
    : Itor(p, sa) 
  {
    // empty
  }
};


    template <class GT, class Show_Arc = Dft_Show_Arc<GT>>
class Arc_Iterator : 
      public Filter_Iterator<GT, typename GT::Arc_Iterator, Show_Arc>
{
public:

  typedef Filter_Iterator<GT, typename GT::Arc_Iterator, Show_Arc> Itor;

  typedef typename Itor::Item_Type Item_Type;

  typedef typename Itor::Set_Type Set_Type;

  Arc_Iterator() { /* empty */ }

  Arc_Iterator(GT & g, Show_Arc && sa = Show_Arc()) 
    : Itor(g, std::move(sa))
  {
    // empty
  }

  Arc_Iterator(GT & g, Show_Arc & sa) 
    : Itor(g, sa) 
  {
    // empty
  }
};


     template <class GT>
struct Dft_Show_Node
{
  bool operator () (typename GT::Node *) const 
  { 
    return true; 
  }
};

    template <class GT, class Show_Node = Dft_Show_Node<GT>>
class Node_Iterator : 
  public Filter_Iterator<GT, typename GT::Node_Iterator, Show_Node>
{
public:

  typedef Filter_Iterator<GT, typename GT::Node_Iterator, Show_Node> Itor;

  typedef typename Itor::Item_Type Item_Type;

  typedef typename Itor::Set_Type Set_Type;

  Node_Iterator() { /* empty */ }

  Node_Iterator(GT & g, Show_Node && sn = Show_Node()) 
    : Itor (g, std::move(sn))
  {
    /* empty */ 
  }

  Node_Iterator(GT & g, Show_Node & sn) 
    : Itor (g, sn) 
  {
    /* empty */ 
  }
};


template <typename __Graph_Node = Graph_Node<int>,
          typename __Graph_Arc  = Graph_Arc<int>>
class List_Digraph : public List_Graph<__Graph_Node, __Graph_Arc>
{
  typedef List_Graph<__Graph_Node, __Graph_Arc> GT;

public:

  typedef __Graph_Node Node;

  typedef __Graph_Arc Arc;

  List_Digraph() 
  {
    this->digraph = true; 
  }
  
  List_Digraph(const List_Digraph & dg) : GT()
  {
    this->digraph = true; 
    *this = dg;
  }

  List_Digraph(List_Digraph && dg) : GT()
  {
    this->digraph = true; 
    this->swap(dg);
  }

  List_Digraph & operator = (const List_Digraph<Node, Arc> & g)
  {
    if (this == &g) 
      return *this;

    copy_graph(*this, const_cast<List_Digraph<Node, Arc>&>(g));

    return *this;
  }

  List_Digraph & operator = (List_Digraph<Node, Arc> && g)
  {
    this->swap(g);

    return *this;
  }  
};


    template <class GT, class Show_Arc = Dft_Show_Arc<GT>>
class Out_Iterator : 
  public Filter_Iterator<typename GT::Node*, 
                         typename GT::Out_Iterator,
                         Show_Arc>
{
public:

      typedef Filter_Iterator
  <typename GT::Node*, typename GT::Out_Iterator, Show_Arc> Itor;

  Out_Iterator() { /* empty */ }

  Out_Iterator(typename GT::Node * p, Show_Arc && sa = Show_Arc()) 
    : Itor(p, sa) 
  {
    // empty
  }

  Out_Iterator(typename GT::Node * p, Show_Arc & sa) 
    : Itor(p, sa) 
  {
    // empty
  }
};

    template <class GT, class Show_Arc = Dft_Show_Arc<GT>>
class In_Iterator : 
  public Filter_Iterator<typename GT::Node*, 
                         typename GT::In_Iterator,
                         Show_Arc>
{
public:

      typedef Filter_Iterator
  <typename GT::Node*, typename GT::In_Iterator, Show_Arc> Itor;

  In_Iterator() { /* empty */ }

  In_Iterator(typename GT::Node * p, Show_Arc && sa = Show_Arc()) 
    : Itor(p, sa) 
  {
    // empty
  }

  In_Iterator(typename GT::Node * p, Show_Arc & sa) 
    : Itor(p, sa) 
  {
    // empty
  }
};

    template <class GT, class SA> typename GT::Arc * 
search_arc(GT & g, typename GT::Node * src_node, 
           typename GT::Node * tgt_node);

    template <class GT> 
typename GT::Node * mapped_node(typename GT::Node * p)
{
 return (typename GT::Node *) NODE_COOKIE(p);
}

    template <class GT> 
typename GT::Arc * mapped_arc(typename GT::Arc * a)
{
  return (typename GT::Arc *) ARC_COOKIE(a);
}

    template <class GTSRC, class GTTGT>
typename GTTGT::Node * mapped_node(typename GTSRC::Node * p)
{
 return (typename GTTGT::Node *) NODE_COOKIE(p);
}
    template <class GTSRC, class GTTGT>
typename GTTGT::Arc * mapped_arc(typename GTSRC::Arc * a)
{
  return (typename GTTGT::Arc *) ARC_COOKIE(a);
}

    template <class GT>
void copy_graph(GT & gtgt, GT & gsrc, const bool cookie_map = false);

template <class GT> inline void clear_graph(GT & g);

    template <class GT, class Operation, class SN = Dft_Show_Node<GT>> 
class Operate_On_Nodes
{
  SN & sn;

public:

  Operate_On_Nodes(SN & __sn) : sn(__sn) { /* empty */ }

  Operate_On_Nodes(SN && __sn = SN()) : sn(__sn) { /* empty */ }

  void operator () (GT & g, Operation op = Operation()) const
  {
    for (Node_Iterator<GT, SN> it(g, sn); it.has_curr(); it.next())
      op (g, it.get_curr());
  }

  void operator () (GT & g, void * ptr, Operation op = Operation()) const
  {
    for (Node_Iterator<GT, SN> it(g, sn); it.has_curr(); it.next())
      op (g, it.get_curr(), ptr);
 }
};

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

public:

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

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

  void operator () (GT & g, Operation op = Operation()) const
  {
    for (Arc_Iterator<GT, SA> it(g, sa); it.has_curr(); it.next())
      op (g, it.get_curr());
  }

  void operator () (GT & g, void * ptr, Operation op = Operation()) const
  {
    for (Arc_Iterator<GT, SA> itor(g, sa); itor.has_curr(); itor.next())
      op (g, itor.get_curr(), ptr);
  }

  void operator () (GT & g, typename GT::Node * p, 
                    Operation op = Operation()) const
  {
    for (Node_Arc_Iterator<GT, SA> it(p); it.has_curr(); it.next())
      op (g, it.get_current_arc());
  }

  void operator () (GT & g, typename GT::Node * node, 
                    void * ptr, Operation op = Operation()) const
  {
    for (Node_Arc_Iterator<GT, SA> it(node); it.has_current(); it.next())
      op (g, it.get_current_arc(), ptr);
  }
};

    template <class GT> 
class Path
{
public:

    typedef typename GT::Node_Type Node_Type;
    typedef typename GT::Arc_Type Arc_Type;

private:

  GT *                g;
  void * cookie;

  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;

public:

  GT & get_graph() { return *g; }

  void *& get_cookie() { return cookie; }

  bool inside_graph(GT & gr) const { return g == &gr; }

  Path(GT & _g, void * __cookie = NULL) : g(&_g), cookie(__cookie) {}

  Path() : g(NULL), cookie(NULL) { /* empty */ }

  void init(Node * start_node) { list.append(Path_Desc(start_node)); }

  Path(GT & _g, Node * start_node, void * __cookie = NULL) 
    : g(&_g), cookie(__cookie) { 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 size_t & size() const { return list.size(); }

  bool is_empty() const { return list.is_empty(); }

  void clear_path()
  {
    while (not list.is_empty())
      list.remove_first();
  }

  void clear() { clear_path(); }

  Path(const Path & path) : g(path.g), list(path.list) {}

  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();

    if (g == NULL)
      throw std::domain_error("Graph has not been specified");

    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;
      }

    if (g == NULL)
      throw std::domain_error("Graph has not been specified");

    Node * last_node = get_last_node();
    Arc * arc        = search_arc(*g, last_node, node); 

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

    append(arc);
  }

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

    if (g == NULL)
      throw std::domain_error("Graph has not been specified");

    Path_Desc & first_path_desc = list.get_first();

    Path_Desc item(g->get_connected_node(arc, first_path_desc.node), arc);

    list.insert(item);
  }

  void insert(Node * node)
  {
    if (list.is_empty())
      {
        init(node);
        return;
      }

    if (g == NULL)
      throw std::domain_error("Graph has not been specified");

    Node * first_node = get_first_node();
    Arc * arc = search_arc(*g, node, first_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)
  {
    std::swap(g, path.g);
    list.swap(path.list);
  }

  class Iterator : public DynDlist<Path_Desc>::Iterator
  {
  public:

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

  private:

    Path_Desc & get_curr_path_desc() 
    {
      return this->DynDlist<Path_Desc>::Iterator::get_current();
    }

  public:

    Node * get_current_node() { return this->get_curr_path_desc().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_curr_path_desc().arc; 
    }

    Node * get_current() { return get_current_node(); }

    Node * get_curr() { return get_current_node(); }

    bool has_current_arc() const 
    {
      return this->has_current() and not this->is_in_last();
    }

    bool has_current_node() const { return this->has_current(); }
  };

      template <class Operation> 
  void operate_on_nodes(Operation && op = Operation())
  {
    for (Iterator it(*this); it.has_current(); it.next())
      op (it.get_current_node());
  }

      template <class Operation> 
  void operate_on_arcs(Operation && op = Operation())
  {
    for (Iterator it(*this); it.has_current(); it.next())
      op (it.get_current_arc());
  }

      template <class Operation> 
  void operate_on_nodes(void * ptr)
  {
    for (Iterator it(*this); it.has_current_node(); it.next())
      Operation(ptr) (it.get_current_node());
  }

      template <class Operation> 
  void operate_on_arcs(void * ptr)
  {
    for (Iterator it(*this); it.has_current_arc(); it.next())
      Operation(ptr) (it.get_current_arc());
  }

  bool contains_node(Node * node) 
  {
    for (Iterator it(*this); it.has_current_node(); it.next())
      if (it.get_current_node() == node)
        return true;
    return false;
  }

  bool contains_arc(Arc * arc) 
  {
    for (Iterator it(*this); it.has_current_arc(); it.next())
      if (it.get_current_arc() == arc) 
        return true;
    return false;
  }
}; 

    template <class GT, class SA = Dft_Show_Arc<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, class SA> inline 
bool __find_path_depth_first(GT& g, typename GT::Node * curr_node,
                             typename GT::Arc *  curr_arc, 
                             typename GT::Node * end_node, Path<GT> & curr_path)
{
  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)) // ¿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); 

      // buscar recursivamente a través de arcos de curr_node
  for (Node_Arc_Iterator<GT, SA> 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;

      ARC_BITS(next_arc).set_bit(Find_Path, true); 
      typename GT::Node * next_node = i.get_tgt_node(); 
      if (__find_path_depth_first<GT, SA> (g, next_node, next_arc, 
                                           end_node, curr_path))
        {
          I(curr_path.get_last_node() == end_node);

          return true; // se encontró camino
        }
    }

  curr_path.remove_last_node(); 

  return false;
}

    template <class GT, class SA = Dft_Show_Arc<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();         
  path.init(start_node);     
  g.reset_bit_nodes(Find_Path);
  g.reset_bit_arcs(Find_Path); 
  NODE_BITS(start_node).set_bit(Find_Path, true);

      // explorar recursivamente cada arco de start_node
  for (Node_Arc_Iterator<GT, SA> i(start_node); i.has_current(); i.next())
    {
      typename GT::Arc * arc = i.get_current_arc();
      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<GT, SA>(g, next_node, arc, end_node, path)) 
        return true;
    }

  return false;
}

    template <class GTS, class GTT>
void map_nodes(typename GTS::Node * p, typename GTT::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 <class GTS, class GTT>
void map_arcs(typename GTS::Arc * p, typename GTT::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;                                                    
}

//
// Implementaciones de métodos de List_Graph
//

   template <typename Node, typename Arc>
Node * List_Graph<Node, Arc>::get_first_node() 
{
  if (Base_Graph::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 (Base_Graph::num_arcs == 0)
    throw std::range_error("Graph has not arcs");

  return dlink_to_arc(arc_list.get_next());
}

   template <typename Node, typename Arc>
Arc * List_Graph<Node, Arc>::get_first_arc(Node * node) 
{
  if (get_num_arcs(node) == 0)
    throw std::range_error("node has not arcs");

  void * arc = dlink_to_arc_node(node->arc_list.get_next())->arc;
  return reinterpret_cast <Arc *> (arc);
}
   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>
Node * List_Graph<Node, Arc>::Node_Iterator::get_current_node() 
{
  return dlink_to_node(Dlink::Iterator::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>
Arc * List_Graph<Node, Arc>::Arc_Iterator::get_current_arc() 
{
  return dlink_to_arc(Dlink::Iterator::get_current()); 
}

   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>
Node * List_Graph<Node, Arc>::insert_node(Node * node)
{
  ++Base_Graph::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 List_Graph<Node, Arc>::insert_node( new Node (node_info) );
}

    template <typename Node, typename Arc> Node * 
List_Graph<Node, Arc>::insert_node(typename Node::Node_Type && node_info)
{
  return List_Graph<Node, Arc>::insert_node
    (new Node (std::move(node_info)) );
}

   template <typename Node, typename Arc> Arc * 
List_Graph<Node, Arc>::insert_arc(Node * src_node, Node * tgt_node)
{  
       // paso 1: apartar memoria para Arc e iniciar
  unique_ptr<Arc> arc ( new Arc ); // apartar memoria para arco 
  arc->src_node   = src_node;      // Iniciar sus campos
  arc->tgt_node   = tgt_node;

      // paso 3: (parcial): apartar Arc_Node de src_node  
  unique_ptr<Arc_Node> src_arc_node (new Arc_Node (arc.get()));

      // paso 2: si es grafo ==> apartar Arc_Node de tgt_node
  if (not Base_Graph::digraph) // si es digrafo ==> no insertar en otro nodo
    {     // inserción en nodo destino 
      if (src_node == tgt_node) // ¿es un lazo?
        arc->tgt_arc_node = src_arc_node.get(); 
      else
        {     // apartar arco nodo para tgt_node 
          unique_ptr<Arc_Node> tgt_arc_node(new Arc_Node(arc.get())); 

              // inserción en lista de adyacencia de 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(); 
        }
    }

      // paso 3 (resto): inserción en lista adyacencia src_node 
  arc->src_arc_node = src_arc_node.get();
  src_node->arc_list.append(src_arc_node.get());
  src_node->num_arcs++;

  arc_list.append(arc.get()); //paso 4:insertar en lista arcos grafo 
  ++Base_Graph::num_arcs;
  src_arc_node.release();

  return arc.release();  
}


    template <typename Node, typename Arc> 
Arc * List_Graph<Node, Arc>::connect_arc(Arc * arc)
{      
  Node * src_node         = get_src_node(arc); 
  Node * tgt_node         = get_tgt_node(arc); 
  Arc_Node * src_arc_node = arc->src_arc_node;
  Arc_Node * tgt_arc_node = arc->tgt_arc_node;

  if (not Base_Graph::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
        {     // inserción en lista de adyacencia de tgt_node
          tgt_node->arc_list.append(tgt_arc_node);
          tgt_node->num_arcs++;
        }
    }

  src_node->arc_list.append(src_arc_node);
  src_node->num_arcs++;
  arc_list.append(arc);
  ++Base_Graph::num_arcs;

  return arc;
}

   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)
{
  Arc * arc = List_Graph<Node, Arc>::insert_arc(src_node, tgt_node);
  arc->get_info() = arc_info;

  return arc;
}

   template <typename Node, typename Arc> Arc * 
List_Graph<Node, Arc>::insert_arc(Node * src_node, Node * tgt_node, 
                                  typename Arc::Arc_Type && arc_info)
{
  Arc * arc = List_Graph<Node, Arc>::insert_arc(src_node, tgt_node);
  arc->get_info() = std::move(arc_info);

  return arc;
}


   template <typename Node, typename Arc> 
void List_Graph<Node, Arc>::remove_arc(Arc * arc) 
{      // paso 1: eliminar Arc_node de 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 Base_Graph::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: eliminar Arc_node de 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 lista de arcos de grafo
  --Base_Graph::num_arcs;
  delete arc;
}

   template <typename Node, typename Arc> 
void List_Graph<Node, Arc>::disconnect_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

  if (not Base_Graph::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--;
        }
    }

      // eliminación de arco del grafo 
  arc->del(); // desenlazar arc de la lista de arcos del grafo
  --Base_Graph::num_arcs;
}

   template <typename Node, typename Arc> 
void List_Graph<Node, Arc>::remove_node(Node * node)
{
  if (not Base_Graph::digraph)
        // Eliminar arcos adyacentes a node
    while (not node->arc_list.is_empty()) // mientras queden arcos
      {     // obtener 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
      }
  else
    for (Arc_Iterator it(*this); it.has_current();)
      {
        Arc * arc = it.get_current();
        if (get_src_node(arc) == node or get_tgt_node(arc) == node)
          {
            it.next();
            remove_arc(arc);
          }
        else
          it.next();
      }

      // en este punto el nodo ya no tiene arcos
  node->del(); // desenlazar nodo de lista de nodos del grafo
  --Base_Graph::num_nodes;
  delete node; 
}

   template <typename Node, typename Arc>
List_Graph<Node, Arc>::List_Graph(const List_Graph<Node, Arc> & g) 
{
  Base_Graph::init();
  copy_graph(*this, const_cast<List_Graph<Node, Arc> &>(g));
}

   template <typename Node, typename Arc>
List_Graph<Node, Arc>::List_Graph(List_Graph<Node, Arc> && g) 
{
  Base_Graph::init();
  swap(g);
}

   template <typename Node, typename Arc>
List_Graph<Node, Arc> & List_Graph<Node, Arc>::operator = 
   (const List_Graph<Node, Arc> & g) 
{
  copy_graph(*this, const_cast<List_Graph<Node, Arc> &>(g));

  return *this;
}


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

   template <typename Node, typename Arc>
List_Graph<Node, Arc>::~List_Graph() 
{ 
  clear_graph(*this); 
}

   template <typename Node, typename Arc>
   template <class Compare>
void List_Graph<Node, Arc>::sort_arcs(Compare && cmp) 
{
  mergesort<Dlink, Cmp_Arc<Compare>>(arc_list, Cmp_Arc<Compare>(cmp)); 
}

   template <typename Node, typename Arc>
   template <class Compare>
void List_Graph<Node, Arc>::sort_arcs(Compare & cmp) 
{
  Cmp_Arc<Compare> comp(cmp);
  mergesort<Dlink, Cmp_Arc<Compare>>(arc_list, comp); 
}

GRAPH_METHODS_IMPLS(List_Graph);

   template <class GT, class SA>
typename GT::Arc * search_arc(GT & g, 
                              typename GT::Node * src, typename GT::Node * tgt) 
{
  I(src != NULL and tgt != NULL);

      // escoger nodo con menos arcos
  if (not g.is_digraph() and tgt->num_arcs < src->num_arcs)
    std::swap(tgt, src);

  for (Node_Arc_Iterator<GT, SA> itor(src); itor.has_curr(); itor.next())  
    if (itor.get_tgt_node() == tgt)
      return itor.get_current_arc();

  return NULL; 
}


   template <class GT>
typename GT::Arc * search_arc(GT & g, typename GT::Node * src_node, 
                              typename GT::Node * tgt_node)
{
  return search_arc<GT, Dft_Show_Arc<GT>>(g, src_node, tgt_node);
}

    template <class GT> 
void clear_graph(GT & g)
{     
  for (typename GT::Arc_Iterator it(g); it.has_current(); ) // eliminar arcos
    {
      typename GT::Arc * arc = it.get_current();
      it.next();
      g.remove_arc(arc);
    }

  for (typename GT::Node_Iterator it(g); it.has_current(); ) // eliminar nodos
    {     
      typename GT::Node * p = it.get_current(); 
      it.next(); // avanzar antes de borrar (consistencia iterador)
      g.remove_node(p); // eliminarlo del grafo
    }
}


    template <class GT> 
void copy_graph(GT & gtgt, GT & gsrc, const bool cookie_map)
{
  IG(not gtgt.is_digraph() and gsrc.is_digraph(), 
     gtgt.is_digraph() != gsrc.is_digraph());

  try
    {
      clear_graph(gtgt); // limpiar this antes de copiar
      DynMapAvlTree<typename GT::Node*, typename GT::Node*> map;  

          // fase 1: recorrer nodos de src_graph e insertar copia en this
      for (typename GT::Node_Iterator it(gsrc); it.has_curr(); it.next())
        {
          typename GT::Node * src_node = it.get_current_node(); 
          unique_ptr<typename GT::Node> 
            tgt_node(new typename GT::Node(src_node));
          map.insert(src_node, tgt_node.get()); 

          typename GT::Node * tgt = tgt_node.release();
          gtgt.insert_node(tgt); // insertar en grafo destino

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

      I(gtgt.get_num_nodes() == gsrc.get_num_nodes());

          // fase 2: por cada arco de src_graph, crear en this un
          // arco que conecte a los nodos mapeados de map
      for (typename GT::Arc_Iterator it(gsrc); it.has_current(); it.next())
        {
          typename GT::Arc * src_arc = it.get_current_arc();

              // obtener imágenes de nodos en el grafo destino y crear arco
          typename GT::Node * src_node = map(gsrc.get_src_node(src_arc)); 
          typename GT::Node * tgt_node = map(gsrc.get_tgt_node(src_arc));
          typename GT::Arc * tgt_arc   = gtgt.insert_arc(src_node, tgt_node); 
          tgt_arc->get_info() = src_arc->get_info();
          if (cookie_map)
            GT::map_arcs(src_arc, tgt_arc);
        }

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

    template <class GTT, class GTS>
struct Dft_Copy_Node
{
  void operator () (typename GTT::Node * tgt, typename GTS::Node * src)
  {
    tgt->get_info() = src->get_info();
  }
};


    template <class GTT, class GTS>
struct Dft_Copy_Arc
{
  void operator () (typename GTT::Arc * tgt, typename GTS::Arc * src)
  {
    tgt->get_info() = src->get_info();
  }
};

    template <class GTT, class GTS, 
              class Copy_Node = Dft_Copy_Node<GTT, GTS>, 
              class Copy_Arc = Dft_Copy_Arc<GTT, GTS>> 
void inter_copy_graph(GTT & gtgt, GTS & gsrc, const bool cookie_map = false)
{
  IG(not gtgt.is_digraph() and gsrc.is_digraph(), 
     gtgt.is_digraph() != gsrc.is_digraph());

  try
    {
      clear_graph(gtgt); // limpiar this antes de copiar
      DynMapAvlTree<typename GTS::Node*, typename GTT::Node*> map;  

          // fase 1: recorrer nodos de src_graph e insertar copia en this
      for (typename GTS::Node_Iterator it(gsrc); it.has_current(); it.next())
        {
          typename GTS::Node * src_node = it.get_current_node(); 
          unique_ptr<typename GTT::Node> tgt_node(new typename GTT::Node);
          Copy_Node () (tgt_node.get(), src_node);
          map.insert(src_node, tgt_node.get()); 

          typename GTT::Node * tgt = tgt_node.release();
          gtgt.insert_node(tgt); // insertar en grafo destino

          if (cookie_map)
            map_nodes<GTS, GTT>(src_node, tgt);
        }

      I(gtgt.get_num_nodes() == gsrc.get_num_nodes());

          // fase 2: por cada arco de src_graph, crear en this un
          // arco que conecte a los nodos mapeados de map
      for (typename GTS::Arc_Iterator it(gsrc); it.has_current(); it.next())
        {
          typename GTS::Arc * src_arc = it.get_current_arc();

              // obtener imágenes de nodos en el grafo destino y crear arco
          typename GTT::Node * src_node = map[gsrc.get_src_node(src_arc)]; 
          typename GTT::Node * tgt_node = map[gsrc.get_tgt_node(src_arc)];
          typename GTT::Arc * tgt_arc   = gtgt.insert_arc(src_node, tgt_node);
          Copy_Arc () (tgt_arc, src_arc);
          if (cookie_map)
            map_arcs<GTS, GTT>(src_arc, tgt_arc);
        }

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


template <class GT,
          class SN = Dft_Show_Node<GT>,
          class SA = Dft_Show_Arc<GT>
          >
class Copy_Graph
{
  SN & sn;
  SA & sa;

public:

  Copy_Graph(SA & __sa, SN & __sn)
    : sn(__sn), sa(__sa)
  {
    // empty
  }

  Copy_Graph(SA && __sa = SA(), SN && __sn = SN())
    : sn(__sn), sa(__sa)
  {
    // empty
  }

  Copy_Graph(SA & __sa, SN && __sn = SN())
    : sn(__sn), sa(__sa)
  {
    // empty
  }

private:

  void copy(GT & gtgt, GT & gsrc, const bool cookie_map)
  {
    IG(not gtgt.is_digraph() and gsrc.is_digraph(), 
       gtgt.is_digraph() != gsrc.is_digraph());

    try
      {
        clear_graph(gtgt); // limpiar this antes de copiar
        DynMapAvlTree<typename GT::Node*, typename GT::Node*> map;  

          // fase 1: recorrer nodos de src_graph e insertar copia en this
        for (Node_Iterator<GT, SN> it(gsrc, sn); it.has_curr(); it.next())
          {
            typename GT::Node * src_node = it.get_curr(); 
            unique_ptr<typename GT::Node> 
              tgt_node(new typename GT::Node(src_node));
            map.insert(src_node, tgt_node.get()); 
            
            typename GT::Node * tgt = tgt_node.release();
            gtgt.insert_node(tgt); // insertar en grafo destino

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

          // fase 2: por cada arco de src_graph, crear en this un
          // arco que conecte a los nodos mapeados de map
        for (Arc_Iterator<GT, SA> it(gsrc, sa); it.has_curr(); it.next())
          {
            typename GT::Arc * src_arc = it.get_curr();

              // obtener imágenes de nodos en el grafo destino y crear arco
            typename GT::Node * src_node = map[gsrc.get_src_node(src_arc)]; 
            typename GT::Node * tgt_node = map[gsrc.get_tgt_node(src_arc)];
            typename GT::Arc * tgt_arc   = 
              gtgt.insert_arc(src_node, tgt_node, src_arc->get_info()); 

            if (cookie_map)
              GT::map_arcs(src_arc, tgt_arc);
          }
      }
    catch (...)
      {     // Si ocurre excepción se limpia this 
        clear_graph(gtgt); 
        throw;
      }
  }

public:

  void operator () (GT & gtgt, GT & gsrc, const bool cookie_map = true)
  {
    copy(gtgt, gsrc, cookie_map);
  }
};

} // end namespace Aleph

# endif /* TPL_GRAPH_H */