tpl_graph.H

Go to the documentation of this file.

/*
                          Aleph_w
 
  Data structures & Algorithms
  version 2.0.0b
  https://github.com/lrleon/Aleph-w
 
  This file is part of Aleph-w library
 
  Copyright (c) 2002-2026 Leandro Rabindranath Leon
 
  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:
 
  The above copyright notice and this permission notice shall be included in all
  copies or substantial portions of the Software.
 
  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  SOFTWARE.
*/
 
 
# ifndef TPL_GRAPH_H
# define TPL_GRAPH_H
 
# include <memory>
# include <cassert>
# include <tuple>
# include <utility>
# include <functional>
# 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 <filter_iterator.H>
# include <aleph-graph.H>
# include <graph-dry.H>
# include <ah-errors.H>
 
using namespace Aleph;
 
namespace Aleph
{
  template <typename Node_Info>
  struct Graph_Node;
 
  template <typename Arc_Info>
  struct Graph_Arc;
 
  class Arc_Node;
 
  template <class GT>
  class Path;
 
  template <typename __Graph_Node, typename __Graph_Arc>
  class List_Graph;
 
  // List_Digraph is defined as a type alias later in this file
  // using the generic Digraph<> template wrapper
 
  template <class GT>
  class Mat_Graph;
 
  template <typename MT, typename Entry_Info, typename Copy>
  class Ady_MaT;
 
  template <typename __Node_Info = Empty_Class>
  struct Graph_Node
      : public Dlink,
        public GTNodeCommon<__Node_Info>
  {
    friend class GTNodeCommon<__Node_Info>;
    friend class Arc_Node;
 
    using Base = GTNodeCommon<__Node_Info>;
    using Node_Info = __Node_Info; 
 
    Graph_Node(const Node_Info & info) noexcept : Base(info)
    { /* empty */
    }
 
    Graph_Node(Node_Info && info = Node_Info()) noexcept
      : Base(std::move(info))
    {
      /* empty */
    }
 
    Graph_Node(const Graph_Node & node) noexcept
      : Graph_Node(node.node_info)
    {
      // empty
    }
 
    Graph_Node &operator=(const Graph_Node & node)
    {
      if (&node == this)
        return *this;
      this->node_info = node.node_info;
      return *this;
    }
 
    Graph_Node(Graph_Node *node)
      : Base(node->get_info())
    {
      /* empty */
    }
 
    Dlink arc_list; 
  };
 
  template <typename _Arc_Info = Empty_Class>
  struct Graph_Arc
      : public Dlink,
        public GTArcCommon<_Arc_Info>
  {
    friend class GTArcCommon<_Arc_Info>;
 
    using Base = GTArcCommon<_Arc_Info>;
 
    using Arc_Info = _Arc_Info; 
 
    Arc_Node *src_arc_node = nullptr; // pointer to source node
    Arc_Node *tgt_arc_node = nullptr; // pointer to target node
 
    Graph_Arc(const Arc_Info & info) noexcept
      : Base(info)
    {
      /* empty */
    }
 
    Graph_Arc(Arc_Info && info = Arc_Info()) noexcept
      : Base(std::move(info))
    {
      /* empty */
    }
 
    Graph_Arc(const Graph_Arc & arc)
      : Graph_Arc(arc.arc_info)
    {
      /* empty */
    }
 
    Graph_Arc &operator=(const Graph_Arc & arc)
    {
      if (&arc == this)
        return *this;
      this->arc_info = arc.arc_info;
      return *this;
    }
  };
 
  class Arc_Node : public Dlink
  {
  public:
    void *arc = nullptr;
 
    Arc_Node() noexcept : arc(nullptr) {}
 
    Arc_Node(void *__arc) noexcept : arc(__arc) {}
  };
 
  template <typename _Graph_Node = Graph_Node<unsigned long>,
            typename _Graph_Arc = Graph_Arc<unsigned long>>
  class List_Graph
      : public GraphCommon<List_Graph<_Graph_Node, _Graph_Arc>,
                           _Graph_Node, _Graph_Arc>
  {
  public:
    using GT = List_Graph; 
 
    using Node = _Graph_Node; 
    using Arc = _Graph_Arc; 
 
    using Node_Type = typename Node::Node_Type;
 
    using Arc_Type = typename Arc::Arc_Type;
 
    friend class GraphCommon<List_Graph<_Graph_Node, _Graph_Arc>,
                             _Graph_Node, _Graph_Arc>;
 
    using CommonBase = GraphCommon<List_Graph<_Graph_Node, _Graph_Arc>,
                                   _Graph_Node, _Graph_Arc>;
 
    using CommonBase::insert_node;
    using CommonBase::insert_arc;
 
  private:
    Dlink node_list;
    Dlink arc_list;
 
    static Node * dlink_to_node(Dlink *p) noexcept
    {
      return static_cast<Node *>(p);
    }
 
    static Arc * dlink_to_arc(Dlink *p) noexcept
    {
      return static_cast<Arc *>(p);
    }
 
    static Arc_Node * dlink_to_arc_node(Dlink *p) noexcept
    {
      return static_cast<Arc_Node *>(p);
    }
 
    static Arc * void_to_arc(Arc_Node *arc_node) noexcept
    {
      return static_cast<Arc *>(arc_node->arc);
    }
 
  public:
    Dlink &get_node_dlink() noexcept { return node_list; }
 
    Dlink &get_arc_dlink() noexcept { return arc_list; }
    virtual Node * insert_node(Node *node) noexcept
    {
      ++this->num_nodes;
      node_list.append(node);
      return node;
    }
 
    virtual void remove_node(Node *node) noexcept
    {
      assert(node != nullptr);
      if (not this->digraph)
        while (not node->arc_list.is_empty()) // remove each arc related to node
          {
            Arc_Node *arc_node = dlink_to_arc_node(node->arc_list.get_next());
            Arc *arc = void_to_arc(arc_node);
            remove_arc(arc);
          }
      else // Scan all the arcs and remove those related to node
        this->remove_arcs_if([node, this](auto a)
                               {
                                 return this->get_src_node(a) == node or this->get_tgt_node(a) == node;
                               });
 
      // At this point the node has not more arcs
      node->del(); // unlink it from arc_list
      --this->num_nodes;
      delete node;
    }
 
    Node * get_first_node() const
    {
      ah_range_error_if(this->num_nodes == 0) << "Graph has not nodes";
 
      return dlink_to_node(const_cast<Dlink &>(node_list).get_next());
    }
 
    Arc * get_first_arc(Node *node) const
    {
      ah_range_error_if(get_num_arcs (node) == 0) << "node has not arcs";
 
      void *arc = dlink_to_arc_node(node->arc_list.get_next())->arc;
      return reinterpret_cast<Arc *>(arc);
    }
 
  private:
    Arc * insert_arc(Node *src_node, Node *tgt_node, void *a)
    {
      assert(src_node != nullptr and tgt_node != nullptr and a != nullptr);
      Arc *arc = static_cast<Arc *>(a);
      arc->src_node = src_node;
      arc->tgt_node = tgt_node;
 
      // step 3 (partial): allocate Arc_Node for src_node
      std::unique_ptr<Arc_Node> src_arc_node = std::make_unique<Arc_Node>(arc);
 
      // step 2: if graph ==> allocate Arc_Node for tgt_node
      if (not this->digraph) // if digraph ==> do not insert in another node
        { // insertion in the target node
          if (src_node == tgt_node) // is it a loop?
            arc->tgt_arc_node = src_arc_node.get();
          else
            { // allocate arc node for tgt_node
              std::unique_ptr<Arc_Node> tgt_arc_node = std::make_unique<Arc_Node>(arc);
 
              // insertion in an adjacency list of 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();
            }
        }
 
      // step 3 (remainder): insertion in the adjacency list of 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); // step 4: insert in graph arc list
      ++this->num_arcs;
      src_arc_node.release();
 
      return arc;
    }
 
  public:
    virtual void remove_arc(Arc *arc) noexcept
    {
      assert(arc != nullptr);
      // step 1: remove Arc_node from src_node
      Node *src_node = this->get_src_node(arc);
      Arc_Node *src_arc_node = arc->src_arc_node;
 
      src_arc_node->del(); // unlink src_node from node list
      --src_node->num_arcs; // decrement arc counter of src_node
      delete src_arc_node; // free memory
 
      if (not this->digraph)
        { // arc removal in target node
          Node *tgt_node = this->get_tgt_node(arc);
          if (src_node != tgt_node) // check for loop removal
            { // step 2: remove Arc_node from tgt_node
              Arc_Node *tgt_arc_node = arc->tgt_arc_node;
              tgt_arc_node->del();
              --tgt_node->num_arcs;
              delete tgt_arc_node;
            }
        }
 
      // arc removal from graph
      arc->del(); // unlink arc from the graph arc list
      --this->num_arcs;
      delete arc;
    }
 
    virtual void disconnect_arc(Arc *arc) noexcept
    {
      assert(arc != nullptr);
      Node *src_node = this->get_src_node(arc);
      Arc_Node *src_arc_node = arc->src_arc_node;
      src_arc_node->del(); // unlink src_node from node list
      --src_node->num_arcs; // decrement arc counter of src_node
 
      if (not this->digraph)
        { // arc removal in target node
          Node *tgt_node = this->get_tgt_node(arc);
          if (src_node != tgt_node) // check for loop removal
            { // step 2: remove Arc_node from target node tgt_node
              Arc_Node *tgt_arc_node = arc->tgt_arc_node;
              tgt_arc_node->del();
              --tgt_node->num_arcs;
            }
        }
 
      // arc removal from graph
      arc->del(); // unlink arc from graph arc list
      --this->num_arcs;
    }
 
    virtual Arc * connect_arc(Arc *arc) noexcept
    {
      assert(arc != nullptr);
      Node *src_node = this->get_src_node(arc);
      Node *tgt_node = this->get_tgt_node(arc);
      Arc_Node *src_arc_node = arc->src_arc_node;
      Arc_Node *tgt_arc_node = arc->tgt_arc_node;
 
      if (not this->digraph) // if digraph ==> no need to insert in other node
        { // insertion in target node
          if (src_node != tgt_node) // check if it is a loop
            { // insertion in adjacency list of 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);
      ++this->num_arcs;
 
      return arc;
    }
 
    Arc * get_first_arc() const
    {
      ah_range_error_if(this->get_num_arcs() == 0) << "Graph has not arcs";
 
      return dlink_to_arc(const_cast<Dlink &>(arc_list).get_next());
    }
 
    // sort_nodes() and sort_arcs() are inherited from GraphCommon via CRTP
    // They use the get_node_dlink() and get_arc_dlink() accessors defined above
 
    ALEPH_GRAPH_COPY_MOVE_CTORS(List_Graph)
 
    
    virtual ~List_Graph()
    {
      clear_graph(*this);
    }
 
    struct Node_Iterator : public GTNodeIterator<List_Graph>
    {
      using Base = GTNodeIterator<List_Graph>;
 
      Node_Iterator(const List_Graph & g)
        : Base(const_cast<Dlink &>(g.node_list))
      {
        // empty
      }
    };
 
    class Node_Arc_Iterator : public Dlink::Iterator
    {
      Node *src_node;
 
    public:
      using Item_Type = Arc *; 
 
      using Set_Type = Node *; 
 
      Node_Arc_Iterator() = default;
 
      Node_Arc_Iterator(Node *src) noexcept
        : Dlink::Iterator(&(src->arc_list)), src_node(src)
      {
        // empty
      }
 
      Arc_Node * get_current_arc_node() const
      {
        return dlink_to_arc_node(Dlink::Iterator::get_curr());
      }
 
      Arc_Node * get_current_arc_node_ne() const noexcept
      {
        return dlink_to_arc_node(Dlink::Iterator::get_curr_ne());
      }
 
      Arc * get_curr() const
      {
        return static_cast<Arc *>(get_current_arc_node()->arc);
      }
 
      Arc * get_curr_ne() const noexcept
      {
        return static_cast<Arc *>(get_current_arc_node_ne()->arc);
      }
 
      Arc * get_current_arc() const
      {
        return get_curr();
      }
 
      Arc * get_current_arc_ne() const noexcept
      {
        return get_curr_ne();
      }
 
      Node * get_tgt_node() const
      {
        return static_cast<Node *>(get_current_arc()->get_connected_node(src_node));
      }
 
      Node * get_tgt_node_ne() const noexcept
      {
        return static_cast<Node *>(get_current_arc_ne()->get_connected_node(src_node));
      }
 
      Node * get_node() const
      {
        return get_tgt_node();
      }
 
      Node * get_node_ne() const noexcept
      {
        return get_tgt_node_ne();
      }
    };
 
    struct Arc_Iterator : public Dlink::Iterator
    {
      using Item_Type = Arc *; 
 
      using Set_Type = List_Graph; 
 
      Arc_Iterator() = default;
 
      Arc_Iterator(const List_Graph & g) noexcept
        : Dlink::Iterator(&const_cast<Dlink &>(g.arc_list))
      {
        // empty
      }
 
      Arc * get_current_arc_ne() const noexcept
      {
        return dlink_to_arc(const_cast<Dlink *>(Dlink::Iterator::get_curr_ne()));
      }
 
      Arc * get_current_arc() const
      {
        return dlink_to_arc(const_cast<Dlink *>(Dlink::Iterator::get_curr()));
      }
 
      Arc * get_curr() const
      {
        return get_current_arc();
      }
 
      Arc * get_curr_ne() const noexcept
      {
        return get_current_arc_ne();
      }
 
      Node * get_src_node() const
      {
        return static_cast<Node *>(get_current_arc()->src_node);
      }
 
      Node * get_src_node_ne() const
      {
        return static_cast<Node *>(get_current_arc_ne()->src_node);
      }
 
      Node * get_tgt_node() const
      {
        return static_cast<Node *>(get_current_arc()->tgt_node);
      }
 
      Node * get_tgt_node_ne() const
      {
        return static_cast<Node *>(get_current_arc_ne()->tgt_node);
      }
    };
 
    List_Graph() = default;
 
    void swap(List_Graph & g) noexcept
    {
      this->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 noexcept
    {
      return true;
    }
 
    void set_cookie(void *) noexcept
    { /* empty */
    }
  };
 
  template <class GT, class Show_Arc = Dft_Show_Arc<GT>>
  struct Node_Arc_Iterator :
      public Filter_Iterator<typename GT::Node *,
                             typename GT::Node_Arc_Iterator,
                             Show_Arc>
  {
    using Filter_Itor = Filter_Iterator<typename GT::Node *,
                                        typename GT::Node_Arc_Iterator,
                                        Show_Arc>;
 
    using Itor = Filter_Iterator<typename GT::Node *,
                                 typename GT::Node_Arc_Iterator,
                                 Show_Arc>;
 
    using Item_Type = typename Itor::Item_Type; 
    using Set_Type = typename Itor::Set_Type; 
 
    Node_Arc_Iterator() = default;
 
    Node_Arc_Iterator(typename GT::Node *p, Show_Arc sa = Show_Arc())
      : Itor(p, sa)
    {
      // empty
    }
  };
 
  template <class GT, class Show_Arc = Dft_Show_Arc<GT>>
  struct Arc_Iterator :
      public Filter_Iterator<GT, typename GT::Arc_Iterator, Show_Arc>
  {
    using Itor = Filter_Iterator<GT, typename GT::Arc_Iterator, Show_Arc>;
 
    using Item_Type = typename Itor::Item_Type; 
    using Set_Type = typename Itor::Set_Type; 
 
    Arc_Iterator() = default;
 
    Arc_Iterator(const GT & g, Show_Arc sa = Show_Arc())
      : Itor(g, sa)
    {
      // empty
    }
  };
 
  template <class GT>
  struct Dft_Show_Node
  {
    bool operator()(typename GT::Node *) const noexcept
    {
      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:
    using Itor = Filter_Iterator<GT, typename GT::Node_Iterator, Show_Node>;
 
    using Item_Type = typename Itor::Item_Type; 
 
    using Set_Type = typename Itor::Set_Type; 
 
    Node_Iterator() = default;
 
    Node_Iterator(const GT & g, Show_Node sn = Show_Node())
      : Itor(g, sn)
    {
      /* empty */
    }
  };
 
  template <class GT, class SN = Dft_Show_Node<GT>>
  void for_each_node(const GT & g,
                     std::function<void (typename GT::Node *)> operation,
                     SN sn = SN())
  {
    for (Node_Iterator<GT, SN> it(g, sn); it.has_curr(); it.next_ne())
      operation(it.get_curr());
  }
 
  template <class GT, class SA = Dft_Show_Arc<GT>>
  void for_each_arc(const GT & g,
                    std::function<void (typename GT::Arc *)> operation,
                    SA sa = SA())
  {
    for (Arc_Iterator<GT, SA> it(g, sa); it.has_curr(); it.next_ne())
      operation(it.get_curr());
  }
 
  template <class GT, class SA = Dft_Show_Arc<GT>>
  void for_each_arc(const GT & g,
                    typename GT::Node *p,
                    std::function<void (typename GT::Arc *)> operation,
                    SA sa = SA())
  {
    (void) g;
    for (Node_Arc_Iterator<GT, SA> it(p, sa); it.has_curr(); it.next_ne())
      operation(it.get_curr());
  }
 
  template <class GT, class SN = Dft_Show_Node<GT>>
  bool forall_node(const GT & g,
                   std::function<bool (typename GT::Node *)> cond,
                   SN sn = SN())
  {
    for (Node_Iterator<GT, SN> it(g, sn); it.has_curr(); it.next_ne())
      if (not cond(it.get_curr()))
        return false;
    return true;
  }
 
  template <class GT, class SA = Dft_Show_Arc<GT>>
  bool forall_arc(const GT & g,
                  std::function<bool (typename GT::Arc *)> cond,
                  SA sa = SA())
  {
    for (Arc_Iterator<GT, SA> it(g, sa); it.has_curr(); it.next_ne())
      if (not cond(it.get_curr()))
        return false;
    return true;
  }
 
  template <class GT, class SA = Dft_Show_Arc<GT>>
  bool forall_arc(typename GT::Node *p,
                  std::function<bool (typename GT::Arc *)> cond,
                  SA sa = SA())
  {
    for (Node_Arc_Iterator<GT, SA> it(p, sa); it.has_curr(); it.next_ne())
      if (not cond(it.get_curr()))
        return false;
    return true;
  }
 
  template <class GT, typename T,
            template<typename> class Container = DynList,
            class SN = Dft_Show_Node<GT>>
  Container<T> nodes_map(GT & g,
                         std::function<T (typename GT::Node *)> transformation,
                         SN sn = SN())
  {
    Container<T> ret_val;
    for_each_node<GT, SN>(g, [&ret_val, &transformation](typename GT::Node *p)
                            {
                              ret_val.append(transformation(p));
                            }, sn);
    return ret_val;
  }
 
  template <class GT, typename T,
            template<typename> class Container = DynList,
            class SA = Dft_Show_Arc<GT>>
  Container<T> arcs_map(GT & g,
                        std::function<T (typename GT::Arc *)> transformation,
                        SA sa = SA())
  {
    Container<T> ret_val;
    for_each_arc<GT, SA>(g, [&ret_val, &transformation](typename GT::Arc *p)
                           {
                             ret_val.append(transformation(p));
                           }, sa);
    return ret_val;
  }
 
  template <class GT, typename T,
            template<typename> class Container = DynList,
            class SA = Dft_Show_Arc<GT>>
  Container<T> arcs_map(GT & g,
                        typename GT::Node *p,
                        std::function<T (typename GT::Arc *)> transformation,
                        SA sa = SA())
  {
    Container<T> ret_val;
    for_each_arc<GT, SA>(g, p, [&ret_val, &transformation](typename GT::Arc *p)
                           {
                             ret_val.append(transformation(p));
                           }, sa);
    return ret_val;
  }
 
  template <class GT, typename T, class SN = Dft_Show_Node<GT>>
  T foldl_nodes(GT & g, const T & init,
                std::function<T (const T &, typename GT::Node *)> operation,
                SN sn = SN())
  {
    T ret_val = init;
    for_each_node<GT, SN>(g, [&ret_val, &operation](typename GT::Node *p)
                            {
                              ret_val = operation(ret_val, p);
                            }, sn);
    return ret_val;
  }
 
  template <class GT, typename T, class SA = Dft_Show_Arc<GT>>
  T foldl_arcs(GT & g, const T & init,
               std::function<T (const T &, typename GT::Arc *)> operation,
               SA sa = SA())
  {
    T ret_val = init;
    for_each_arc<GT, SA>(g, [&ret_val, &operation](typename GT::Arc *a)
                           {
                             ret_val = operation(ret_val, a);
                           }, sa);
    return ret_val;
  }
 
  template <class GT, typename T, class SA = Dft_Show_Arc<GT>>
  T foldl_arcs(GT & g, typename GT::Node *p,
               const T & init,
               std::function<T (const T &, typename GT::Arc *)> operation,
               SA sa = SA())
  {
    T ret_val = init;
    for_each_arc<GT, SA>(g, p, [&ret_val, &operation](typename GT::Arc *a)
                           {
                             ret_val = operation(ret_val, a);
                           }, sa);
    return ret_val;
  }
 
  template <typename __Graph_Node = Graph_Node<int>,
            typename __Graph_Arc = Graph_Arc<int>>
  using List_Digraph = Digraph<List_Graph<__Graph_Node, __Graph_Arc>>;
 
 
  template <class GT>
  using ArcPair = std::tuple<typename GT::Arc *, typename GT::Node *>;
 
  template <class GT>
  class __Out_Filt
  {
    typename GT::Node *src = nullptr;
 
  public:
    __Out_Filt(typename GT::Node *__src) noexcept : src(__src)
    { /* empty */
    }
 
    bool operator()(typename GT::Arc *a) const noexcept
    {
      assert(src);
      return a->src_node == src;
    }
 
    typename GT::Node * get_node(typename GT::Arc *a) const noexcept
    {
      assert(src);
      return static_cast<typename GT::Node *>(a->tgt_node);
    }
  };
 
  template <class GT>
  class __In_Filt
  {
    typename GT::Node *tgt = nullptr;
 
  public:
    __In_Filt(typename GT::Node *__tgt) noexcept : tgt(__tgt)
    { /* empty */
    }
 
    bool operator()(typename GT::Arc *a) const noexcept
    {
      assert(tgt);
      return a->tgt_node == tgt;
    }
 
    typename GT::Node * get_node(typename GT::Arc *a) const noexcept
    {
      assert(tgt);
      return static_cast<typename GT::Node *>(a->src_node);
    }
  };
 
  template <class GT, class Filter>
  class Digraph_Iterator
  {
    using Itor = Filter_Iterator<typename GT::Node *,
                                 typename GT::Node_Arc_Iterator, Filter>;
 
    Filter filt;
    Itor it;
 
  public:
    using Item_Type = typename Itor::Item_Type; 
 
    using Iterator_Type = Itor; 
 
    Digraph_Iterator(typename GT::Node *p)
      : filt(p), it(p, filt)
    {
      // empty
    }
 
    void next()
    {
      it.next();
    }
 
    void next_ne() noexcept
    {
      it.next_ne();
    }
 
    void prev() { it.prev(); }
 
    [[nodiscard]] bool has_curr() const noexcept
    {
      return it.has_curr();
    }
 
    typename GT::Arc * get_curr() const
    {
      return it.get_curr();
    }
 
    typename GT::Arc * get_curr_ne() const noexcept
    {
      return it.get_curr_ne();
    }
 
    auto get_current_arc() const
    {
      return get_curr();
    }
 
    typename GT::Node * get_node(typename GT::Arc *a) const noexcept
    {
      return filt.get_node(a);
    }
 
    typename GT::Node * get_node() const
    {
      return this->get_node(this->get_curr());
    }
 
    auto get_tgt_node() const
    {
      return get_node();
    }
 
    typename GT::Node * get_node_ne() const noexcept
    {
      return this->get_node(this->get_curr_ne());
    }
 
    auto get_tgt_node_ne() const noexcept
    {
      return get_node_ne();
    }
 
    void reset_first() noexcept
    {
      it.reset_first();
    }
 
    void reset_last() noexcept
    {
      it.reset_last();
    }
 
    void end() noexcept
    {
      put_itor_at_the_end(*this);
    }
  };
 
 
  template <class GT>
  using _Out_Iterator = Digraph_Iterator<GT, __Out_Filt<GT>>;
 
 
  template <class GT>
  using _In_Iterator = Digraph_Iterator<GT, __In_Filt<GT>>;
 
  template <class GT, class Show_Arc = Dft_Show_Arc<GT>>
  class Out_Iterator : public Digraph_Iterator<GT, __Out_Filt<GT>>
  {
    using Base = Digraph_Iterator<GT, __Out_Filt<GT>>;
    Show_Arc show_arc;
 
    void goto_first_valid()
    {
      while (Base::has_curr() and not show_arc(Base::get_curr_ne()))
        Base::next_ne();
    }
 
  public:
    using Item_Type = typename GT::Arc *;
 
    Out_Iterator() = default;
 
    Out_Iterator(typename GT::Node *p, Show_Arc sa = Show_Arc())
      : Base(p), show_arc(sa)
    {
      goto_first_valid();
    }
 
    void next()
    {
      Base::next();
      goto_first_valid();
    }
 
    void next_ne() noexcept
    {
      Base::next_ne();
      goto_first_valid();
    }
  };
 
  template <class GT, class SA = Dft_Show_Arc<GT>>
  class In_Iterator : public Digraph_Iterator<GT, __In_Filt<GT>>
  {
    using Base = Digraph_Iterator<GT, __In_Filt<GT>>;
    SA show_arc;
 
    void goto_first_valid()
    {
      while (Base::has_curr() and not show_arc(Base::get_curr_ne()))
        Base::next_ne();
    }
 
  public:
    using Item_Type = typename GT::Arc *;
 
    In_Iterator() = default;
 
    In_Iterator(typename GT::Node *p, SA sa = SA())
      : Base(p), show_arc(sa)
    {
      goto_first_valid();
    }
 
    void next()
    {
      Base::next();
      goto_first_valid();
    }
 
    void next_ne() noexcept
    {
      Base::next_ne();
      goto_first_valid();
    }
  };
 
  template <class GT, class SA = Dft_Show_Arc<GT>>
  DynList<typename GT::Node *> out_nodes(typename GT::Node *p, SA sa = SA())
  {
    DynList<typename GT::Node *> ret;
    for (Out_Iterator<GT, SA> it(p, sa); it.has_curr(); it.next_ne())
      ret.append(it.get_node_ne());
    return ret;
  }
 
  template <class GT, class SA = Dft_Show_Arc<GT>>
  DynList<typename GT::Node *> in_nodes(typename GT::Node *p, SA sa = SA())
  {
    DynList<typename GT::Node *> ret;
    for (In_Iterator<GT, SA> it(p, sa); it.has_curr(); it.next_ne())
      ret.append(it.get_node_ne());
    return ret;
  }
 
  template <class GT, class SA = Dft_Show_Arc<GT>>
  DynList<typename GT::Arc *> out_arcs(typename GT::Node *p, SA sa = SA())
  {
    DynList<typename GT::Arc *> ret;
    for (Out_Iterator<GT, SA> it(p, sa); it.has_curr(); it.next_ne())
      ret.append(it.get_curr());
    return ret;
  }
 
  template <class GT, class SA = Dft_Show_Arc<GT>>
  DynList<typename GT::Arc *> in_arcs(typename GT::Node *p, SA sa = SA())
  {
    DynList<typename GT::Arc *> ret;
    for (In_Iterator<GT, SA> it(p, sa); it.has_curr(); it.next_ne())
      ret.append(it.get_curr());
    return ret;
  }
 
  template <class GT, class SA = Dft_Show_Arc<GT>>
  DynList<typename GT::Arc *> arcs(typename GT::Node *p, SA sa = SA())
  {
    DynList<typename GT::Arc *> ret;
    for (Node_Arc_Iterator<GT, SA> it(p, sa); it.has_curr(); it.next_ne())
      ret.append(it.get_curr());
    return ret;
  }
 
  template <class GT, class SA = Dft_Show_Arc<GT>>
  DynList<ArcPair<GT>> in_pairs(typename GT::Node *p, SA sa = SA())
  {
    DynList<ArcPair<GT>> ret;
    for (In_Iterator<GT, SA> it(p, sa); it.has_curr(); it.next_ne())
      {
        typename GT::Arc *a = it.get_curr();
        ret.append(std::make_tuple(a, static_cast<typename GT::Node *>(a->get_connected_node(p))));
      }
    return ret;
  }
 
  template <class GT, class SA = Dft_Show_Arc<GT>>
  DynList<ArcPair<GT>> out_pairs(typename GT::Node *p, SA sa = SA())
  {
    DynList<ArcPair<GT>> ret;
    for (Out_Iterator<GT, SA> it(p, sa); it.has_curr(); it.next_ne())
      {
        typename GT::Arc *a = it.get_curr();
        ret.append(std::make_tuple(a, static_cast<typename GT::Node *>(a->get_connected_node(p))));
      }
    return ret;
  }
 
  template <class GT, class SA = Dft_Show_Arc<GT>>
  size_t in_degree(typename GT::Node *p, SA sa = SA())
  {
    size_t count = 0;
    for (In_Iterator<GT, SA> it(p, sa); it.has_curr(); it.next_ne())
      ++count;
    return count;
  }
 
  template <class GT>
  size_t in_degree(typename GT::Node *p)
  {
    size_t count = 0;
    for (_In_Iterator<GT> it(p); it.has_curr(); it.next_ne())
      ++count;
    return count;
  }
 
  template <class GT, class SA = Dft_Show_Arc<GT>>
  size_t out_degree(typename GT::Node *p, SA sa = SA())
  {
    size_t count = 0;
    for (Out_Iterator<GT, SA> it(p, sa); it.has_curr(); it.next_ne())
      ++count;
    return count;
  }
 
  template <class GT>
  size_t out_degree(typename GT::Node *p)
  {
    size_t count = 0;
    for (_Out_Iterator<GT> it(p); it.has_curr(); it.next_ne())
      ++count;
    return count;
  }
 
  template <class GT, class Itor, class Operation>
  inline
  bool traverse_arcs(typename GT::Node *p, Operation op = Operation())
  {
    for (Itor it(p); it.has_curr(); it.next_ne())
      if (not op(it.get_curr()))
        return false;
    return true;
  }
 
  template <class GT, class Itor, class Operation>
  inline
  void for_each_arc(typename GT::Node *p, Operation op = Operation())
  {
    for (Itor it(p); it.has_curr(); it.next_ne())
      op(it.get_curr());
  }
 
 
  // Functional operations on input arcs
 
  template <class GT, class Op>
  inline
  bool traverse_in_arcs(typename GT::Node *p, Op op = Op())
  {
    return traverse_arcs<GT, _In_Iterator<GT>, Op>(p, op);
  }
 
  template <class GT, class Op>
  inline
  void for_each_in_arc(typename GT::Node *p, Op op = Op())
  {
    for_each_arc<GT, _In_Iterator<GT>, Op>(p, op);
  }
 
  template <class GT, class Op>
  inline
  bool all_in_arc(typename GT::Node *p, Op op = Op())
  {
    return traverse_in_arcs(p, [&op](auto a)
                              {
                                return op(a);
                              });
  }
 
  template <class GT, class Op>
  inline
  bool exists_in_arc(typename GT::Node *p, Op op = Op())
  {
    return not traverse_in_arcs<GT, Op>(p, [&op](auto a)
                                          {
                                            return not op(a);
                                          });
  }
 
  template <class GT, class Op>
  inline
  auto search_in_arc(typename GT::Node *p, Op op = Op())
  {
    typename GT::Arc *ret = nullptr;
    traverse_in_arcs(p, [&op, &ret](auto a)
                       {
                         if (op(a))
                           {
                             ret = a;
                             return false;
                           }
                         return true;
                       });
    return ret;
  }
 
  template <class GT, typename T>
  inline
  auto map_in_arcs(typename GT::Node *p, std::function<T (typename GT::Arc *)> op)
  {
    DynList<T> ret;
    for_each_in_arc(p, [&ret, &op](auto a)
                      {
                        ret.append(op(a));
                      });
    return ret;
  }
 
  template <class GT, typename T>
  inline
  T foldl_in_arcs(typename GT::Node *p, const T & init,
                  std::function<T (const T &, typename GT::Arc *)> op)
  {
    T ret = init;
    for_each_in_arc(p, [&ret, &op](auto a)
                      {
                        ret = op(ret, a);
                      });
    return ret;
  }
 
  template <class GT, class Op>
  inline
  DynList<typename GT::Arc *> filter_in_arcs(typename GT::Node *p, Op cond)
  {
    DynList<typename GT::Arc *> ret;
    for_each_in_arc(p, [&ret, &cond](auto a)
                      {
                        if (cond(a))
                          ret.append(a);
                      });
    return ret;
  }
 
 
  // Functional operation on output arcs
 
  template <class GT, class Op>
  inline
  bool traverse_out_arcs(typename GT::Node *p, Op op = Op())
  {
    return traverse_arcs<GT, _Out_Iterator<GT>, Op>(p, op);
  }
 
  template <class GT, class Op>
  inline
  void for_each_out_arc(typename GT::Node *p, Op op = Op())
  {
    for_each_arc<GT, _Out_Iterator<GT>, Op>(p, op);
  }
 
  template <class GT, class Op>
  inline
  bool all_out_arc(typename GT::Node *p, Op op = Op())
  {
    return traverse_out_arcs(p, [&op](auto a)
                               {
                                 return op(a);
                               });
  }
 
  template <class GT, class Op>
  inline
  bool exists_out_arc(typename GT::Node *p, Op op = Op())
  {
    return not traverse_out_arcs<GT, Op>(p, [&op](auto a)
                                           {
                                             return not op(a);
                                           });
  }
 
  template <class GT, class Op>
  inline
  auto search_out_arc(typename GT::Node *p, Op op = Op())
  {
    typename GT::Arc *ret = nullptr;
    traverse_out_arcs<GT>(p, [&op, &ret](auto a)
                            {
                              if (op(a))
                                {
                                  ret = a;
                                  return false;
                                }
                              return true;
                            });
    return ret;
  }
 
  template <class GT, typename T>
  inline
  auto map_out_arcs(typename GT::Node *p, std::function<T (typename GT::Arc *)> op)
  {
    DynList<T> ret;
    for_each_out_arc(p, [&ret, &op](auto a)
                       {
                         ret.append(op(a));
                       });
    return ret;
  }
 
  template <class GT, typename T>
  inline
  T foldl_out_arcs(typename GT::Node *p, const T & init,
                   std::function<T (const T &, typename GT::Arc *)> op)
  {
    T ret = init;
    for_each_out_arc(p, [&ret, &op](auto a)
                       {
                         ret = op(ret, a);
                       });
    return ret;
  }
 
  template <class GT, class Op>
  inline
  DynList<typename GT::Arc *> filter_out_arcs(typename GT::Node *p, Op cond)
  {
    DynList<typename GT::Arc *> ret;
    for_each_out_arc(p, [&ret, &cond](auto a)
                       {
                         if (cond(a))
                           ret.append(a);
                       });
    return ret;
  }
 
  template <class GT, class SA = Dft_Show_Arc<GT>>
  typename GT::Arc *
  search_arc(const GT & g,
             typename GT::Node *src, typename GT::Node *tgt,
             SA sa = SA()) noexcept
  {
    assert(src != nullptr and tgt != nullptr);
 
    if (not g.is_digraph() and tgt->num_arcs < src->num_arcs)
      std::swap(tgt, src); // select the node with less arcs
 
    for (Node_Arc_Iterator<GT, SA> itor(src, sa); itor.has_curr(); itor.next_ne())
      if (itor.get_tgt_node_ne() == tgt)
        return itor.get_current_arc_ne();
 
    return nullptr;
  }
 
  template <class GT, class SA = Dft_Show_Arc<GT>>
  typename GT::Arc *
  search_directed_arc(const GT & g,
                      typename GT::Node *src, typename GT::Node *tgt,
                      SA sa = SA()) noexcept
  {
    (void) g;
    assert(src != nullptr and tgt != nullptr);
 
    for (Node_Arc_Iterator<GT, SA> it(src, sa); it.has_curr(); it.next_ne())
      if (typename GT::Arc *a = it.get_curr(); a->src_node == src and a->tgt_node == tgt)
        return a;
 
    return nullptr;
  }
 
  template <class GT>
  typename GT::Node * mapped_node(typename GT::Node *p) noexcept
  {
    return static_cast<typename GT::Node *>(NODE_COOKIE(p));
  }
 
  template <class GT>
  typename GT::Arc * mapped_arc(typename GT::Arc *a) noexcept
  {
    return static_cast<typename GT::Arc *>(ARC_COOKIE(a));
  }
 
  template <class GTSRC, class GTTGT>
  typename GTTGT::Node * mapped_node(typename GTSRC::Node *p) noexcept
  {
    return static_cast<typename GTTGT::Node *>(NODE_COOKIE(p));
  }
 
  template <class GTSRC, class GTTGT>
  typename GTTGT::Arc * mapped_arc(typename GTSRC::Arc *a) noexcept
  {
    return static_cast<typename GTTGT::Arc *>(ARC_COOKIE(a));
  }
 
  template <class GT>
  inline
  void copy_graph(GT & gtgt, const GT & gsrc, bool cookie_map = false);
 
  template <class GT>
  inline void clear_graph(GT & g) noexcept;
 
  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(__sn)
    { /* empty */
    }
 
    void operator()(const GT & g, Operation op = Operation())
    {
      for (Node_Iterator<GT, SN> it(g, sn); it.has_curr(); it.next_ne())
        op(g, it.get_curr());
    }
 
    void operator()(GT & g, Operation op = Operation())
    {
      for (Node_Iterator<GT, SN> it(g, sn); it.has_curr(); it.next_ne())
        op(g, it.get_curr());
    }
  };
 
  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(__sa)
    { /* empty */
    }
 
    void operator()(const GT & g, Operation op = Operation()) const
    {
      for (Arc_Iterator<GT, SA> it(g, sa); it.has_curr(); it.next_ne())
        op(g, it.get_curr());
    }
 
    void operator()(GT & g, Operation op = Operation()) const
    {
      for (Arc_Iterator<GT, SA> it(g, sa); it.has_curr(); it.next_ne())
        op(g, it.get_curr());
    }
 
    void operator()(const GT & g, typename GT::Node *p,
                    Operation op = Operation()) const
    {
      for (Node_Arc_Iterator<GT, SA> it(p); it.has_curr(); it.next_ne())
        op(g, it.get_current_arc_ne());
    }
 
    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_ne())
        op(g, it.get_current_arc_ne());
    }
  };
 
  template <class GT>
  class Path
  {
  public:
    using Node_Type = typename GT::Node_Type;
 
    using Arc_Type = typename GT::Arc_Type;
 
  private:
    const GT *g = nullptr;
 
    using Node = typename GT::Node;
    using Arc = typename GT::Arc;
 
    struct Path_Desc
    {
      Node *node; // source node
      Arc *arc; // adjacent arc
 
      Path_Desc(Node *_node = nullptr, Arc *_arc = nullptr) noexcept
        : node(_node), arc(_arc)
      {}
 
      bool operator==(const Path_Desc & r) const noexcept
      {
        if (not (node->get_info() == r.node->get_info()))
          return false;
 
        if (arc == nullptr)
          return r.arc == nullptr;
 
        if (r.arc == nullptr)
          return false;
 
        return arc->get_info() == r.arc->get_info();
      }
    };
 
    DynDlist<Path_Desc> list;
 
    void check_graph()
    {
      ah_domain_error_if(g == nullptr) << "Path: Graph has not been specified";
    }
 
  public:
    [[nodiscard]] bool check() const
    {
      auto l = list;
      while (not l.is_unitarian_or_empty())
        {
          auto d = l.remove_first();
          auto nxt = l.get_first().node;
          if (nxt == g->get_connected_node(d.arc, d.node))
            return false;
        }
 
      return true;
    }
 
    [[nodiscard]] bool check_directed() const
    {
      return list.all([this](auto d)
                        {
                          return g->get_src_node(d.arc) == d.node;
                        })
             and list.get_last().arc == nullptr;
    }
 
    const GT &get_graph() const noexcept
    {
      return *g;
    }
 
    bool inside_graph(const GT & gr) const noexcept
    {
      return g == &gr;
    }
 
    Path(const GT & __g) noexcept : g(&__g)
    {}
 
    Path() noexcept : g(nullptr)
    { /* empty */
    }
 
    void init(Node *start_node)
    {
      assert(start_node != nullptr);
      list.append(Path_Desc(start_node));
    }
 
    Path(const GT & _g, Node *start_node) : g(&_g)
    {
      init(start_node);
    }
 
    void set_graph(const GT & __g, Node *start_node = nullptr)
    {
      empty();
      g = &__g;
      if (start_node == nullptr)
        return;
      init(start_node);
    }
 
    [[nodiscard]] size_t size() const noexcept
    {
      return list.size();
    }
 
    [[nodiscard]] bool is_empty() const noexcept
    {
      return list.is_empty();
    }
 
    void empty()
    {
      check_graph();
      while (not list.is_empty())
        list.remove_first();
    }
 
    void clear() { empty(); }
 
    Path(const Path & path) : g(path.g), list(path.list) {}
 
    Path(Path && path)  noexcept : g(path.g), list(std::move(path.list)) {}
 
    Path &operator=(const Path & path)
    {
      if (this == &path)
        return *this;
 
      empty();
      g = path.g;
      list = path.list;
      return *this;
    }
 
    Path &operator=(Path && path) noexcept
    {
      std::swap(g, path.g);
      list.swap(path.list);
      return *this;
    }
 
    void append(Arc *arc)
    {
      assert(arc != nullptr);
      check_graph();
 
      ah_domain_error_if(list.is_empty()) << "path is empty";
 
      auto & last_path_desc = list.get_last();
      auto last_node = last_path_desc.node;
      ah_invalid_argument_if(arc->src_node != last_node and arc->tgt_node != last_node)
      << "arc has not link to last node of path";
 
      last_path_desc.arc = arc;
      list.append(Path_Desc(g->get_connected_node(arc, last_node)));
    }
 
    void append(Node *node)
    {
      check_graph();
 
      if (list.is_empty())
        {
          init(node);
          return;
        }
 
      Node *last_node = get_last_node();
      Arc *arc = search_arc(*g, last_node, node);
 
      ah_invalid_argument_if(arc == nullptr)
        << "There is no an arc connecting to the node";
 
      append(arc);
    }
 
    void append_directed(Node *p)
    {
      assert(p != nullptr);
      check_graph();
      if (list.is_empty())
        {
          init(p);
          return;
        }
 
      auto & last_path_desc = list.get_last();
      Node *last_node = last_path_desc.node;
      Arc *arc = search_directed_arc(*g, last_node, p);
 
      ah_invalid_argument_if(arc == nullptr) << "There is no an arc connecting to the node";
 
      assert(arc->src_node == last_path_desc.node);
 
      last_path_desc.arc = arc;
      list.append(Path_Desc(static_cast<Node *>(arc->tgt_node)));
    }
 
    void append_directed(Arc *arc)
    {
      assert(arc != nullptr);
      check_graph();
 
      ah_domain_error_if(list.is_empty()) << "path is empty";
 
      auto & last_path_desc = list.get_last();
      Node *last_node = last_path_desc.node;
      ah_invalid_argument_if(arc->src_node != last_node)
        << "The arc does not connect the last node";
 
      last_path_desc.arc = arc;
      list.append(Path_Desc(static_cast<Node *>(arc->tgt_node)));
    }
 
    void insert(Arc *arc)
    {
      assert(arc != nullptr);
      check_graph();
 
      ah_domain_error_if(list.is_empty()) << "path is empty";
 
      auto & first_path_desc = list.get_first();
      auto first_node = first_path_desc.node;
      ah_invalid_argument_if(arc->src_node != first_node and arc->tgt_node != first_node)
        << "arc has not link to first node of path";
 
      Path_Desc item(g->get_connected_node(arc, first_node), arc);
      list.insert(item);
    }
 
    void insert(Node *node)
    {
      check_graph();
 
      if (list.is_empty())
        {
          init(node);
          return;
        }
 
      Node *first_node = get_first_node();
      Arc *arc = search_arc(*g, node, first_node); // search arc first_node-node
      ah_domain_error_if(arc == nullptr) << "There is no arc connecting node";
 
      Path_Desc item(node, arc);
      list.insert(item);
    }
 
    void insert_directed(Node *p)
    {
      assert(p != nullptr);
      check_graph();
 
      if (list.is_empty())
        {
          init(p);
          return;
        }
 
      Node *first_node = get_first_node();
      Arc *arc = search_directed_arc(*g, p, first_node);
      ah_domain_error_if(arc == nullptr) << "There is no an arc connecting to the node";
 
      list.insert(Path_Desc(p, arc));
    }
 
    void insert_directed(Arc *arc)
    {
      assert(arc != nullptr);
      check_graph();
 
      ah_domain_error_if(list.is_empty()) << "path is empty";
 
      auto & first_path_desc = list.get_first();
      Node *first_node = first_path_desc.node;
      ah_invalid_argument_if(arc->tgt_node != first_node)
        << "The arc does not connect the first node";
 
      list.insert(Path_Desc(static_cast<Node *>(arc->src_node), arc));
    }
 
    Node * get_first_node() const
    {
      return list.get_first().node;
    }
 
    Node * get_last_node() const
    {
      auto & last_path_desc = list.get_last();
      assert(last_path_desc.arc == nullptr);
      return last_path_desc.node;
    }
 
    Arc * get_first_arc() const
    {
      return list.get_first().arc;
    }
 
    Arc * get_last_arc() const
    {
      ah_domain_error_if(list.is_unitarian())
        << "Path with only a node (without any arc)";
 
      typename DynDlist<Path_Desc>::Iterator it(list);
      it.reset_last();
      it.prev();
      return it.get_curr().arc;
    }
 
    [[nodiscard]] bool is_cycle() const
    {
      return get_first_node() == get_last_node();
    }
 
    Node * remove_last_node()
    {
      auto d = list.remove_last();
      list.get_last().arc = nullptr;
      return d.node;
    }
 
    Node * remove_first_node()
    {
      auto d = list.remove_first();
      return d.node;
    }
 
    void swap(Path & path) noexcept
    {
      std::swap(g, path.g);
      list.swap(path.list);
    }
 
    class Iterator : public DynDlist<Path_Desc>::Iterator
    {
    public:
      Iterator(const Path & path) noexcept
        : DynDlist<Path_Desc>::Iterator(path.list)
      {}
 
    private:
      Path_Desc &get_curr_path_desc_ne() const noexcept
      {
        return this->DynDlist<Path_Desc>::Iterator::get_curr_ne();
      }
 
      Path_Desc &get_curr_path_desc() const
      {
        return this->DynDlist<Path_Desc>::Iterator::get_curr();
      }
 
    public:
      Node * get_current_node() const
      {
        return this->get_curr_path_desc().node;
      }
 
      Node * get_current_node_ne() const noexcept
      {
        return this->get_curr_path_desc_ne().node;
      }
 
      Arc * get_current_arc() const
      {
        ah_overflow_error_if(this->is_in_last()) << "Path iterator is in last node of path";
 
        return this->get_curr_path_desc().arc;
      }
 
      Arc * get_current_arc_ne() const noexcept
      {
        return this->get_curr_path_desc_ne().arc;
      }
 
      Node * get_curr_ne() const noexcept
      {
        return get_current_node_ne();
      }
 
      Node * get_curr() const
      {
        return get_current_node();
      }
 
      std::pair<Node *, Arc *> get_pair() const
      {
        return std::make_pair(get_current_node(), get_current_arc());
      }
 
      std::tuple<Node *, Arc *> get_tuple() const
      {
        return std::make_tuple(get_current_node(), get_current_arc());
      }
 
      std::tuple<Node *, Arc *> get_tuple_ne() const noexcept
      {
        return std::make_tuple(get_current_node_ne(), get_current_arc_ne());
      }
 
      [[nodiscard]] bool has_current_arc() const noexcept
      {
        return this->has_curr() and not this->is_in_last();
      }
 
      [[nodiscard]] bool has_current_node() const noexcept
      {
        return this->has_curr();
      }
    };
 
    Iterator get_it() const
    {
      return Iterator(*this);
    }
 
    template <class Operation>
    void for_each_node(Operation op = Operation()) const
    {
      for (Iterator it(*this); it.has_current_node(); it.next_ne())
        op(it.get_current_node_ne());
    }
 
    template <class Operation>
    void for_each_arc(Operation op = Operation()) const
    {
      for (Iterator it(*this); it.has_current_arc(); it.next_ne())
        op(it.get_current_arc_ne());
    }
 
    bool contains_node(Node *node) const noexcept
    {
      for (Iterator it(*this); it.has_current_node(); it.next_ne())
        if (it.get_current_node_ne() == node)
          return true;
      return false;
    }
 
    bool contains_arc(Arc *arc) const noexcept
    {
      for (Iterator it(*this); it.has_current_arc(); it.next_ne())
        if (it.get_current_arc_ne() == arc)
          return true;
      return false;
    }
 
    DynList<Node *> nodes() const
    {
      DynList<Node *> ret_val;
      for_each_node([&ret_val](Node *p)
                      {
                        ret_val.append(p);
                      });
      return ret_val;
    }
 
    DynList<Arc *> arcs() const
    {
      DynList<Arc *> ret_val;
      for_each_arc([&ret_val](Arc *a)
                     {
                       ret_val.append(a);
                     });
      return ret_val;
    }
 
    bool operator==(const Path & p) const noexcept
    {
      return eq(this->list, p.list);
    }
 
    bool operator!=(const Path & p) const noexcept
    {
      return not eq(this->list, p.list);
    }
  };
 
  template <class GT>
  inline
  Path<GT> find_path_depth_first(const GT & g, typename GT::Node *start_node,
                                 typename GT::Node *end_node);
 
  template <class GT>
  static inline
  bool __find_path_depth_first(const GT & g, typename GT::Node *curr_node,
                               typename GT::Arc *curr_arc,
                               typename GT::Node *end_node, Path<GT> & path)
  {
    if (curr_node == end_node) // this test must be first in order to find cycles
      {
        path.append(curr_arc);
        return true;
      }
 
    if (IS_NODE_VISITED(curr_node, Find_Path))
      return false;
 
    path.append(curr_arc);
    NODE_BITS(curr_node).set_bit(Find_Path, true);
 
    for (auto it = g.get_arc_it(curr_node); it.has_curr(); it.next_ne())
      {
        auto next_arc = it.get_curr();
        if (IS_ARC_VISITED(next_arc, Find_Path))
          continue;
 
        ARC_BITS(next_arc).set_bit(Find_Path, true);
        if (auto next_node = it.get_tgt_node(); __find_path_depth_first<GT>(g, next_node, next_arc, end_node, path))
          {
            assert(path.get_last_node () == end_node);
            return true;
          }
      }
 
    path.remove_last_node();
 
    return false;
  }
 
  template <class GT>
  inline
  Path<GT> find_path_depth_first(const GT & g, typename GT::Node *start_node,
                                 typename GT::Node *end_node)
  {
    Path<GT> path(g, start_node);
 
    g.reset_bit_nodes(Find_Path);
    g.reset_bit_arcs(Find_Path);
    NODE_BITS(start_node).set_bit(Find_Path, true);
 
    for (auto it = g.get_arc_it(start_node); it.has_curr(); it.next_ne())
      {
        auto arc = it.get_current_arc_ne();
        ARC_BITS(arc).set_bit(Find_Path, true);
        auto next_node = it.get_tgt_node();
        if (IS_NODE_VISITED(next_node, Find_Path))
          continue;
 
        if (__find_path_depth_first<GT>(g, next_node, arc, end_node, path))
          return path;
      }
 
    path.empty();
 
    return path;
  }
 
  template <class GTS, class GTT>
  void map_nodes(typename GTS::Node *p, typename GTT::Node *q) noexcept
  {
    assert(p != nullptr and q != nullptr);
 
    // Use reinterpret_cast to preserve an exact pointer value without any
    // implicit base class pointer adjustment from multiple inheritance
    if (NODE_COOKIE(p) == nullptr)
      {
        NODE_COOKIE(p) = reinterpret_cast<void *>(q);
        NODE_COOKIE(q) = reinterpret_cast<void *>(p);
        return;
      }
 
    NODE_COOKIE(q) = NODE_COOKIE(p);
    NODE_COOKIE(p) = reinterpret_cast<void *>(q);
  }
 
  template <class GTS, class GTT>
  void map_arcs(typename GTS::Arc *p, typename GTT::Arc *q) noexcept
  {
    assert(p != nullptr and q != nullptr);
 
    if (ARC_COOKIE(p) == nullptr)
      {
        ARC_COOKIE(p) = q;
        ARC_COOKIE(q) = p;
 
        return;
      }
 
    ARC_COOKIE(q) = ARC_COOKIE(p);
    ARC_COOKIE(p) = q;
  }
 
  template <class GT>
  void clear_graph(GT & g) noexcept
  {
    for (typename GT::Arc_Iterator it(g); it.has_curr();) // remove arcs
      {
        typename GT::Arc *arc = it.get_curr_ne();
        it.next_ne();
        g.remove_arc(arc);
      }
 
    for (typename GT::Node_Iterator it(g); it.has_curr();) // remove nodes
      {
        typename GT::Node *p = it.get_curr_ne();
        it.next_ne(); // advance before deletion (iterator consistency)
        g.remove_node(p); // remove it from the graph
      }
  }
 
  template <class GT>
  void copy_graph(GT & gtgt, const GT & gsrc, const bool cookie_map)
  {
    try
      {
        clear_graph(gtgt); // clear this before copying
        DynMapAvlTree<typename GT::Node *, typename GT::Node *> map;
 
        // phase 1: traverse nodes of src_graph and insert copy in this
        for (typename GT::Node_Iterator it(gsrc); it.has_curr(); it.next_ne())
          {
            typename GT::Node *src_node = it.get_current_node_ne();
            std::unique_ptr<typename GT::Node>
                tgt_node(new typename GT::Node(src_node->get_info()));
            map.insert(src_node, tgt_node.get());
 
            typename GT::Node *tgt = tgt_node.release();
            assert(tgt->get_info () == src_node->get_info ());
            gtgt.insert_node(tgt); // insert in the target graph
 
            if (cookie_map)
              GT::map_nodes(src_node, tgt);
          }
 
        assert(gtgt.get_num_nodes() == gsrc.get_num_nodes());
 
        // phase 2: for each arc of src_graph, create in this an
        // arc connecting the mapped nodes from map
        for (typename GT::Arc_Iterator it(gsrc); it.has_curr(); it.next_ne())
          {
            typename GT::Arc *src_arc = it.get_current_arc_ne();
 
            // get node images in target graph and create arc
            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();
            *tgt_arc = *src_arc;
            if (cookie_map)
              GT::map_arcs(src_arc, tgt_arc);
          }
 
        assert(gtgt.get_num_arcs() == gsrc.get_num_arcs());
      }
    catch (...)
      { // If an exception occurs, clean this
        clear_graph(gtgt);
        throw;
      }
  }
 
  template <class GTT, class GTS>
  struct Dft_Copy_Node
  {
    void operator()(typename GTT::Node *tgt, typename GTS::Node *src) noexcept
    {
      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, const GTS & gsrc,
                        const bool cookie_map = false)
  {
    try
      {
        clear_graph(gtgt); // clear this before copying
        DynMapAvlTree<typename GTS::Node *, typename GTT::Node *> map;
        // phase 1: traverse nodes of src_graph and insert a copy in this
        for (typename GTS::Node_Iterator it(gsrc); it.has_curr(); it.next_ne())
          {
            typename GTS::Node *src_node = it.get_current_node_ne();
            std::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); // insert in the target graph
 
            if (cookie_map)
              map_nodes<GTS, GTT>(src_node, tgt);
          }
 
        assert(gtgt.get_num_nodes() == gsrc.get_num_nodes());
 
        // phase 2: for each arc of src_graph, create in this an
        // arc connecting the mapped nodes from the map
        for (typename GTS::Arc_Iterator it(gsrc); it.has_curr(); it.next_ne())
          {
            typename GTS::Arc *src_arc = it.get_current_arc_ne();
 
            // get node images in target graph and create arc
            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);
          }
 
        assert(gtgt.get_num_arcs() == gsrc.get_num_arcs());
      }
    catch (...)
      { // If an exception occurs, clean 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 = SA(), SN __sn = SN()) : sn(__sn), sa(__sa)
    {
      // empty
    }
 
  private:
    void copy(GT & gtgt, const GT & gsrc, const bool cookie_map)
    {
      try
        {
          clear_graph(gtgt); // clear this before copying
          DynMapAvlTree<typename GT::Node *, typename GT::Node *> map;
 
          // phase 1: traverse nodes of src_graph and insert a copy in this
          for (Node_Iterator<GT, SN> it(gsrc, sn); it.has_curr(); it.next_ne())
            {
              typename GT::Node *src_node = it.get_curr();
              std::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); // insert in target graph
 
              if (cookie_map)
                GT::map_nodes(src_node, tgt);
            }
 
          // phase 2: for each arc of src_graph, create in this an
          // arc connecting the mapped nodes from a map
          for (Arc_Iterator<GT, SA> it(gsrc, sa); it.has_curr(); it.next_ne())
            {
              typename GT::Arc *src_arc = it.get_curr();
 
              // get node images in target graph and create arc
              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 (...)
        { // If an exception occurs, it is cleaned this
          clear_graph(gtgt);
          throw;
        }
    }
 
  public:
    void operator()(GT & gtgt, GT & gsrc, const bool cookie_map = true)
    {
      copy(gtgt, gsrc, cookie_map);
    }
  };
 
  template <class GT, class Distance>
  struct Painted_Min_Spanning_Tree
  {
    typename Distance::Distance_Type dist;
 
    Painted_Min_Spanning_Tree() noexcept : dist(0)
    { /* empty */
    }
 
    bool operator()(typename GT::Arc *a) noexcept
    {
      if (not IS_ARC_VISITED(a, Aleph::Spanning_Tree))
        return false;
 
      dist = dist + Distance()(a);
 
      return true;
    }
  };
 
  template <class GT>
  inline
  bool are_equal(const GT & g1, const GT & g2);
 
  template <class GT,
            template <class, class> class Tree = Treap>
  class GraphCopyWithMapping
  {
  public:
    using Node = typename GT::Node;
    using Arc = typename GT::Arc;
    using Node_Type = typename GT::Node_Type;
    using Arc_Type = typename GT::Arc_Type;
 
  private:
    GT copied_graph;
    DynMapTree<Node *, Node *, Tree> node_map; // original -> copy
 
    void build_copy(const GT & src)
    {
      // Phase 1: Copy all nodes and build mapping
      for (typename GT::Node_Iterator it(src); it.has_curr(); it.next_ne())
        {
          Node *src_node = it.get_curr();
          Node *tgt_node = copied_graph.insert_node(src_node->get_info());
          node_map.insert(src_node, tgt_node);
        }
 
      // Phase 2: Copy all arcs using the node mapping
      for (typename GT::Arc_Iterator it(src); it.has_curr(); it.next_ne())
        {
          Arc *src_arc = it.get_curr();
          Node *src_src = src.get_src_node(src_arc);
          Node *src_tgt = src.get_tgt_node(src_arc);
 
          Node *tgt_src = node_map.find(src_src);
          Node *tgt_tgt = node_map.find(src_tgt);
 
          copied_graph.insert_arc(tgt_src, tgt_tgt, src_arc->get_info());
        }
    }
 
  public:
    explicit GraphCopyWithMapping(const GT & src)
    {
      build_copy(src);
    }
 
    GraphCopyWithMapping() = default;
 
    GraphCopyWithMapping(GraphCopyWithMapping && other) noexcept = default;
 
    GraphCopyWithMapping &operator=(GraphCopyWithMapping && other) noexcept = default;
 
    // Disable copy (graphs can be large)
    GraphCopyWithMapping(const GraphCopyWithMapping &) = delete;
 
    GraphCopyWithMapping &operator=(const GraphCopyWithMapping &) = delete;
 
    GT &get_graph() noexcept { return copied_graph; }
 
    const GT &get_graph() const noexcept { return copied_graph; }
 
    Node * get_copy(Node *orig) const
    {
      auto *ptr = node_map.search(orig);
      ah_domain_error_if(ptr == nullptr)
      << "Node not found in mapping (not from original graph?)";
      return ptr->second;
    }
 
    Node * search_copy(Node *orig) const noexcept
    {
      auto *ptr = node_map.search(orig);
      return ptr ? ptr->second : nullptr;
    }
 
    bool has_copy(Node *orig) const noexcept
    {
      return node_map.search(orig) != nullptr;
    }
 
    [[nodiscard]] size_t num_nodes() const noexcept { return node_map.size(); }
 
    [[nodiscard]] size_t num_arcs() const noexcept { return copied_graph.get_num_arcs(); }
 
    template <typename Op>
    void for_each_mapping(Op op) const
    {
      node_map.for_each([&op](const auto & pair)
                          {
                            op(pair.first, pair.second);
                          });
    }
 
    Node * insert_unmapped_node(const Node_Type & info = Node_Type())
    {
      return copied_graph.insert_node(info);
    }
 
    Node * insert_unmapped_node(Node_Type && info)
    {
      return copied_graph.insert_node(std::forward<Node_Type>(info));
    }
 
    void remove_node(Node *node)
    {
      // Maintain node_map consistency when a copied node is removed:
      // perform a reverse lookup (value -> key) and erase the corresponding entry.
      // This is O(N) because DynMapTree is keyed by original node, not by copy.
      Node *original_node = nullptr;
      node_map.for_each([&](const auto & pair)
                          {
                            if (pair.second == node)
                              {
                                original_node = pair.first;
                              }
                          });
 
      if (original_node)
          node_map.remove(original_node);
 
      copied_graph.remove_node(node);
    }
 
    Arc * insert_arc(Node *src, Node *tgt, const Arc_Type & info = Arc_Type())
    {
      return copied_graph.insert_arc(src, tgt, info);
    }
 
    void remove_arc(Arc *arc)
    {
      copied_graph.remove_arc(arc);
    }
 
    void clear()
    {
      node_map.empty();
      Aleph::clear_graph(copied_graph);
    }
  };
} // end namespace Aleph
 
# endif /* TPL_GRAPH_H */