graph-dry.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 GRAPH_DRY_H
# define GRAPH_DRY_H
 
#include <concepts>
 
// ============================================================================
// C++20 Concepts for Graph Iterators
// ============================================================================
 
template <typename It>
concept BasicGraphIterator = requires(It it, const It cit)
{
  { cit.has_curr() } -> std::convertible_to<bool>;
  { it.next() } -> std::same_as<void>;
  { it.get_curr() };
};
 
template <typename It>
concept ResettableGraphIterator = BasicGraphIterator<It> && requires(It it)
{
  { it.reset_first() } -> std::same_as<void>;
};
 
template <typename It, typename Node>
concept GraphNodeIterator = BasicGraphIterator<It> && requires(const It cit)
{
  { cit.get_curr() } -> std::convertible_to<Node*>;
};
 
template <typename It, typename Arc>
concept GraphArcIterator = BasicGraphIterator<It> && requires(const It cit)
{
  { cit.get_curr() } -> std::convertible_to<Arc*>;
};
 
template <typename It, typename Node, typename Arc>
concept NodeArcIterator = GraphArcIterator<It, Arc> && requires(const It cit)
{
  { cit.get_tgt_node() } -> std::convertible_to<Node*>;
};
 
 
// ============================================================================
// End of C++20 Concepts
// ============================================================================
 
template <class GT>
struct GTNodeIterator : public Dlink::Iterator
{
  using Node = typename GT::Node;
 
  using Item_Type = Node *;
 
  using Set_Type = GT;
 
  GTNodeIterator() noexcept
  { /* empty */
  }
 
  GTNodeIterator(Dlink & head) noexcept : Dlink::Iterator(head)
  { /* empty */
  }
 
  Node * get_curr_ne() const noexcept
  {
    return static_cast<Node *>(Dlink::Iterator::get_curr_ne());
  }
 
  Node * get_curr() const { return static_cast<Node *>(Dlink::Iterator::get_curr()); }
 
  Node * get_current_node() const { return get_curr(); }
 
  Node * get_current_node_ne() const { return get_curr_ne(); }
};
 
 
template <class GT>
struct GTArcIterator : public Dlink::Iterator
{
  using Node = typename GT::Node;
  using Arc = typename GT::Arc;
 
  using Item_Type = Arc *;
 
  using Set_Type = GT;
 
  GTArcIterator() noexcept
  { /* empty */
  }
 
  GTArcIterator(Dlink & head) noexcept
    : Dlink::Iterator(head)
  { /* empty */
  }
 
  Arc * get_curr_ne() const noexcept
  {
    return static_cast<Arc *>(Dlink::Iterator::get_curr_ne());
  }
 
  Arc * get_curr() const { return static_cast<Arc *>(Dlink::Iterator::get_curr()); }
 
  Arc * get_current_arc() const { return get_curr(); }
 
  Arc * get_current_arc_ne() const noexcept { return get_curr_ne(); }
 
  Node * get_src_node_ne() const noexcept
  {
    return static_cast<Node *>(get_curr_ne()->src_node);
  }
 
  Node * get_tgt_node_ne() const noexcept
  {
    return static_cast<Node *>(get_curr_ne()->tgt_node);
  }
 
  Node * get_src_node() const
  {
    return static_cast<Node *>(get_curr()->src_node);
  }
 
  Node * get_tgt_node() const
  {
    return static_cast<Node *>(get_curr()->tgt_node);
  }
};
 
 
template <class GT, class Cmp>
struct Cmp_Dlink_Node
{
  using Node = typename GT::Node;
 
  Cmp & cmp;
 
  Cmp_Dlink_Node(Cmp && __cmp = Cmp()) noexcept : cmp(__cmp)
  { /* empty */
  }
 
  Cmp_Dlink_Node(Cmp & __cmp) noexcept : cmp(__cmp)
  { /* empty */
  }
 
  bool operator ()(Dlink *d1, Dlink *d2) const noexcept
  {
    Node *p1 = static_cast<Node *>(d1);
    Node *p2 = static_cast<Node *>(d2);
    return cmp(p1, p2);
  }
};
 
template <class GT, class Cmp>
struct Cmp_Dlink_Arc
{
  using Arc = typename GT::Arc;
 
  Cmp & cmp;
 
  Cmp_Dlink_Arc(Cmp && __cmp = Cmp()) noexcept : cmp(__cmp)
  { /* empty */
  }
 
  Cmp_Dlink_Arc(Cmp & __cmp) noexcept : cmp(__cmp)
  { /* empty */
  }
 
  bool operator ()(Dlink *d1, Dlink *d2) const noexcept
  {
    Arc *arc1 = static_cast<Arc *>(d1);
    Arc *arc2 = static_cast<Arc *>(d2);
    return cmp(arc1, arc2);
  }
};
 
template <typename NodeInfo>
class GTNodeCommon
{
public:
  Graph_Attr attrs;
 
  NodeInfo node_info; 
 
 
  size_t num_arcs = 0;
 
  using Item_Type = NodeInfo; 
 
  using Node = GTNodeCommon; 
 
  using Node_Type = NodeInfo; 
 
  GTNodeCommon() noexcept = default;
 
  GTNodeCommon(const NodeInfo & info) : node_info(info) {}
 
  GTNodeCommon(NodeInfo && info) : node_info(std::move(info)) {}
 
  GTNodeCommon(const GTNodeCommon & other) : node_info(other.node_info) {}
 
  GTNodeCommon(GTNodeCommon && other) noexcept : node_info(std::move(other.node_info)) {}
 
  GTNodeCommon & operator=(const GTNodeCommon & other)
  {
    if (this != &other)
      node_info = other.node_info;
    return *this;
  }
 
  GTNodeCommon & operator=(GTNodeCommon && other) noexcept
  {
    if (this != &other)
      node_info = std::move(other.node_info);
    return *this;
  }
 
  NodeInfo &get_info() noexcept { return node_info; }
 
  const NodeInfo &get_info() const noexcept { return node_info; }
 
  unsigned int state() const noexcept { return NODE_BITS(this).state; }
 
  void set_state(unsigned int s) noexcept
  {
    NODE_BITS(this).state = s;
  }
};
 
 
template <typename ArcInfo>
class GTArcCommon
{
public:
  using Item_Type = ArcInfo;
  using Arc_Type = ArcInfo;
 
  void *src_node = nullptr; 
  void *tgt_node = nullptr; 
 
  Graph_Attr attrs;
 
  ArcInfo arc_info; 
 
  GTArcCommon() noexcept = default;
 
  GTArcCommon(const ArcInfo & info) : arc_info(info) {}
 
  GTArcCommon(ArcInfo && info) : arc_info(std::move(info)) {}
 
  GTArcCommon(void *src, void *tgt, const ArcInfo & data)
    : src_node(src), tgt_node(tgt), arc_info(data) {}
 
  GTArcCommon(void *src, void *tgt, ArcInfo && data = ArcInfo())
    : src_node(src), tgt_node(tgt), arc_info(std::move(data)) {}
 
  GTArcCommon(const GTArcCommon & other)
    : src_node(other.src_node), tgt_node(other.tgt_node), arc_info(other.arc_info) {}
 
  GTArcCommon(GTArcCommon && other) noexcept
    : src_node(other.src_node), tgt_node(other.tgt_node), arc_info(std::move(other.arc_info)) {}
 
  GTArcCommon & operator=(const GTArcCommon & other)
  {
    if (this != &other)
      arc_info = other.arc_info;
    return *this;
  }
 
  GTArcCommon & operator=(GTArcCommon && other) noexcept
  {
    if (this != &other)
      arc_info = std::move(other.arc_info);
    return *this;
  }
 
  unsigned int state() const noexcept { return ARC_BITS(this).state; }
 
  void set_state(unsigned int s) noexcept
  {
    ARC_BITS(this).state = s;
  }
 
  ArcInfo &get_info() noexcept { return arc_info; }
 
  const ArcInfo &get_info() const noexcept { return arc_info; }
 
  void * get_connected_node(void *node) noexcept
  {
    return src_node == node ? tgt_node : src_node;
  }
 
  void * get_img_node(void *node) noexcept
  {
    return src_node == node ? src_node : tgt_node;
  }
};
 
 
template <class GT, class Node, class Arc>
class GraphCommon
{
  GT * me() { return static_cast<GT *>(this); }
 
  const GT * const_me() const { return static_cast<const GT *>(this); }
 
protected:
  void *cookie = nullptr;
  size_t num_nodes = 0;
  size_t num_arcs = 0;
  bool digraph = false;
 
public:
  using Node_Type = typename Node::Node_Type;
  using Arc_Type = typename Arc::Arc_Type;
 
protected:
  void init() noexcept
  {
    num_nodes = num_arcs = 0;
    cookie = nullptr;
    digraph = false;
  }
 
  void common_swap(GT & g) noexcept
  {
    std::swap(num_nodes, g.num_nodes);
    std::swap(num_arcs, g.num_arcs);
    std::swap(digraph, g.digraph);
    std::swap(cookie, g.cookie);
  }
 
public:
  void *&get_cookie() noexcept { return cookie; }
 
  void * get_cookie() const noexcept { return cookie; }
 
  bool is_digraph() const noexcept { return digraph; }
 
  void set_digraph(bool val) { digraph = val; } // TODO: delete after
 
  [[nodiscard]] constexpr size_t get_num_nodes() const noexcept { return num_nodes; }
 
  [[nodiscard]] constexpr bool is_empty() const noexcept { return num_nodes == 0; }
 
  [[nodiscard]] constexpr size_t vsize() const noexcept { return get_num_nodes(); }
 
  Node * get_node() const { return const_me()->get_first_node(); }
 
  Node * get_arc() const { return const_me()->get_first_arc(); }
 
  Node * get_arc(Node *p) { return const_me()->get_first_arc(p); }
 
  Node * get_src_node(Arc *arc) const noexcept
  {
    return static_cast<Node *>(arc->src_node);
  }
 
  Node * get_tgt_node(Arc *arc) const noexcept
  {
    return static_cast<Node *>(arc->tgt_node);
  }
 
  Node * get_connected_node(Arc *arc, Node *node) const noexcept
  {
    return static_cast<Node *>(arc->get_connected_node(node));
  }
 
  [[nodiscard]] constexpr size_t get_num_arcs() const noexcept { return num_arcs; }
 
  size_t get_num_arcs(Node *node) const noexcept
  {
    return node->num_arcs;
  }
 
  size_t degree(Node *p) const noexcept { return get_num_arcs(p); }
 
  size_t esize() const noexcept { return get_num_arcs(); }
 
  Bit_Fields &get_control_bits(Node *node) const noexcept
  {
    return NODE_BITS(node).reset();
  }
 
  void reset_bit(Node *node, int bit) const noexcept
  {
    NODE_BITS(node).reset(bit);
  }
 
  void reset_bits(Node *node) const noexcept
  {
    NODE_BITS(node).reset();
  }
 
  int get_bit(Node *node, int bit) const noexcept
  {
    return NODE_BITS(node).get_bit(bit);
  }
 
  void set_bit(Node *node, int bit, int value) const noexcept
  {
    NODE_BITS(node).set_bit(bit, value);
  }
 
  Bit_Fields &get_control_bits(Arc *arc) const noexcept
  {
    return ARC_BITS(arc);
  }
 
  void reset_bit(Arc *arc, int bit) const noexcept
  {
    ARC_BITS(arc).reset(bit);
  }
 
  void reset_bits(Arc *arc) const noexcept
  {
    ARC_BITS(arc).reset();
  }
 
  int get_bit(Arc *arc, int bit) const noexcept
  {
    return ARC_BITS(arc).get_bit(bit);
  }
 
  void set_bit(Arc *arc, int bit, int value) const noexcept
  {
    ARC_BITS(arc).set_bit(bit, value);
  }
 
  void *&get_cookie(Node *node) const noexcept
  {
    return NODE_COOKIE(node);
  }
 
  void *&get_cookie(Arc *arc) const noexcept
  {
    return ARC_COOKIE(arc);
  }
 
  long &get_counter(Node *node) const noexcept
  {
    return NODE_COUNTER(node);
  }
 
  void reset_counter(Node *node) const noexcept
  {
    NODE_COUNTER(node) = 0;
  }
 
  void reset_node_counters() const noexcept
  {
    for_each_node([this](auto p) { this->reset_counter(p); });
  }
 
  void reset_node(Node *p) const noexcept
  {
    p->attrs.reset();
  }
 
  long &get_counter(Arc *arc) const noexcept
  {
    return ARC_COUNTER(arc);
  }
 
  void reset_counter(Arc *arc) const noexcept
  {
    ARC_COUNTER(arc) = No_Visited;
  }
 
  void reset_arc_counters() const noexcept
  {
    for_each_arc([this](auto a) { this->reset_counter(a); });
  }
 
  void reset_arc(Arc *arc) const noexcept
  {
    arc->attrs.reset();
  }
 
  void reset_nodes() const
  {
    for_each_node([](auto p) { p->attrs.reset(); });
  }
 
  void reset_arcs() const
  {
    for_each_arc([](auto a) { a->attrs.reset(); });
  }
 
  template <class N1, class N2 = N1>
  static
  void map_nodes(N1 *p, N2 *q) noexcept
  {
    assert(p != nullptr and q != nullptr);
    // Use reinterpret_cast to preserve exact pointer values 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 A1, class A2 = A1>
  static
  void map_arcs(A1 *p, A2 *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;
  }
 
  void reset_bit_nodes(int bit) const noexcept
  {
    for_each_node([bit, this](auto p) { this->reset_bit(p, bit); });
  }
 
  void reset_bit_arcs(int bit) const noexcept
  {
    for_each_arc([bit, this](auto a) { this->reset_bit(a, bit); });
  }
 
  void reset_bit_nodes() const noexcept
  {
    for_each_node([this](auto p) { this->reset_bits(p); });
  }
 
  void reset_bit_arcs() const noexcept
  {
    for_each_arc([this](auto a) { this->reset_bits(a); });
  }
 
  void reset_counter_nodes() const noexcept
  {
    for_each_node([this](auto p) { this->reset_counter(p); });
  }
 
  void reset_counter_arcs() const noexcept
  {
    for_each_arc([this](auto a) { this->reset_counter(a); });
  }
 
  void reset_cookie_nodes() const noexcept
  {
    for_each_node([](auto p) { NODE_COOKIE(p) = nullptr; });
  }
 
  void reset_cookie_arcs() const noexcept
  {
    for_each_arc([](auto a) { ARC_COOKIE(a) = nullptr; });
  }
 
  Node * insert_node(const Node_Type & node_info)
  {
    return me()->insert_node(new Node(node_info));
  }
 
  Node * insert_node(Node_Type && node_info = Node_Type())
  {
    return me()->insert_node(new Node(std::forward<Node_Type>(node_info)));
  }
 
  template <typename... Args>
  Node * emplace_node(Args &&... args)
  {
    return me()->insert_node(Node_Type(args...));
  }
 
  Arc * insert_arc(Node *src, Node *tgt, const Arc_Type & arc_info)
  {
    std::unique_ptr<Arc> arc(new Arc(arc_info));
    me()->insert_arc(src, tgt, arc.get());
    return arc.release();
  }
 
  Arc * insert_arc(Node *src, Node *tgt, Arc_Type && arc_info = Arc_Type())
  {
    std::unique_ptr<Arc> arc(new Arc(std::forward<Arc_Type>(arc_info)));
    me()->insert_arc(src, tgt, arc.get());
    return arc.release();
  }
 
  template <typename... Args>
  Arc * emplace_arc(Node *src, Node *tgt, Args &&... args)
  {
    return me()->insert_arc(src, tgt, Arc_Type(args...));
  }
 
  template <class Operation>
  bool traverse_nodes(Operation & op) const
  {
    for (typename GT::Node_Iterator it(*const_me()); it.has_curr(); it.next_ne())
      if (not op(it.get_curr()))
        return false;
    return true;
  }
 
  template <class Operation>
  bool traverse_nodes(Operation && op = Operation()) const
  {
    return traverse_nodes(op);
  }
 
  template <class Operation>
  bool traverse_arcs(Operation & op) const
  {
    for (typename GT::Arc_Iterator it(*const_me()); it.has_curr(); it.next_ne())
      if (not op(it.get_curr()))
        return false;
    return true;
  }
 
  template <class Operation>
  bool traverse_arcs(Operation && op = Operation()) const
  {
    return traverse_arcs(op);
  }
 
  template <class Operation>
  bool traverse_arcs(Node *p, Operation & op) const
  {
    for (typename GT::Node_Arc_Iterator it(p); it.has_curr(); it.next_ne())
      if (not op(it.get_curr()))
        return false;
    return true;
  }
 
  template <class Operation>
  bool traverse_arcs(Node *p, Operation && op = Operation()) const
  {
    return traverse_arcs(p, op);
  }
 
  template <class Operation>
  void for_each_node(Operation & operation) const
  {
    for (typename GT::Node_Iterator it(*const_me()); it.has_curr(); it.next_ne())
      operation(it.get_curr());
  }
 
  template <class Operation>
  void for_each_node(Operation && operation = Operation()) const
  {
    for_each_node(operation);
  }
 
  template <class Operation>
  void for_each_arc(Operation & op) const
  {
    for (typename GT::Arc_Iterator it(*const_me()); it.has_curr(); it.next_ne())
      op(it.get_curr());
  }
 
  template <class Operation>
  void for_each_arc(Operation && operation = Operation()) const
  {
    for_each_arc(operation);
  }
 
  template <class Operation>
  void for_each_arc(Node *p, Operation & op) const
  {
    for (typename GT::Node_Arc_Iterator it(p); it.has_curr(); it.next_ne())
      op(it.get_curr());
  }
 
  template <class Operation>
  void for_each_arc(Node *p, Operation && op = Operation()) const
  {
    for_each_arc(p, op);
  }
 
  template <class Operation>
  bool all_nodes(Operation & op) const
  {
    return traverse_nodes(op);
  }
 
  template <class Operation>
  bool all_nodes(Operation && op = Operation()) const
  {
    return all_nodes(op);
  }
 
  template <class Operation>
  bool all_arcs(Operation & op) const
  {
    return traverse_arcs(op);
  }
 
  template <class Operation>
  bool all_arcs(Operation && op = Operation()) const
  {
    return all_arcs(op);
  }
 
  template <class Operation>
  bool all_arcs(Node *p, Operation & op) const
  {
    return traverse_arcs(p, op);
  }
 
  template <class Operation>
  bool all_arcs(Node *p, Operation && op = Operation()) const
  {
    return all_arcs(p, op);
  }
 
  template <typename T = Node_Type>
  auto nodes_map(std::function<T(Node *)> op) const
  {
    DynList<T> ret_val;
    for_each_node([&ret_val, &op](Node *p) { ret_val.append(op(p)); });
    return ret_val;
  }
 
  template <typename T = Arc_Type>
  auto arcs_map(std::function<T(Arc *)> operation) const
  {
    DynList<T> ret_val;
    for_each_arc([&ret_val, &operation](Arc *p)
                   {
                     ret_val.append(operation(p));
                   });
    return ret_val;
  }
 
  template <typename T = Arc_Type>
  auto arcs_map(Node *p, std::function<T(Arc *)> operation) const
  {
    DynList<T> ret_val;
    for_each_arc(p, [&ret_val, &operation](Arc *a)
                   {
                     ret_val.append(operation(a));
                   });
    return ret_val;
  }
 
  template <typename T = Node_Type>
  T foldl_nodes(const T & init,
                std::function<T(const T &, Node *)> op) const
  {
    T ret = init;
    for_each_node([&ret, &op](Node *p) { ret = op(ret, p); });
    return ret;
  }
 
  template <typename T = Arc_Type>
  T foldl_arcs(const T & init,
               std::function<T(const T &, Arc *)> op) const
  {
    T ret = init;
    for_each_arc([&ret, &op](Arc *p) { ret = op(ret, p); });
    return ret;
  }
 
  template <typename T = Arc_Type>
  T foldl_arcs(Node *p, const T & init,
               std::function<T(const T &, Arc *)> op) const
  {
    T ret = init;
    for_each_arc(p, [&ret, &op](Arc *a) { ret = op(ret, a); });
    return ret;
  }
 
  template <class Op>
  auto filter_nodes(Op & op) const
  {
    DynList<Node *> ret;
    for_each_node([&ret, &op](Node *p)
                    {
                      if (op(p))
                        ret.append(p);
                    });
    return ret;
  }
 
  template <class Op>
  auto filter_nodes(Op && op) const
  {
    return filter_nodes(op);
  }
 
  template <class Op>
  auto filter_arcs(Op & op) const
  {
    DynList<Arc *> ret;
    for_each_arc([&ret, &op](Arc *a)
                   {
                     if (op(a))
                       ret.append(a);
                   });
    return ret;
  }
 
  template <class Op>
  auto filter_arcs(Op && op) const
  {
    return filter_arcs(op);
  }
 
  template <class Op>
  auto filter_arcs(Node *p, Op & op) const
  {
    DynList<Arc *> ret;
    for_each_arc(p, [&ret, &op](Arc *a)
                   {
                     if (op(a))
                       ret.append(a);
                   });
    return ret;
  }
 
  template <class Op>
  auto filter_arcs(Node *p, Op && op) const
  {
    return filter_arcs(p, op);
  }
 
  template <class Operation>
  bool exists_node(Operation & op) const
  {
    return not traverse_nodes([&op](Node *p) { return not op(p); });
  }
 
  template <class Operation>
  bool exists_node(Operation && op = Operation()) const
  {
    return exists_node(op);
  }
 
  template <class Operation>
  bool exists_arc(Operation & op) const
  {
    return not traverse_arcs([&op](Arc *a) { return not op(a); });
  }
 
  template <class Operation>
  bool exists_arc(Operation && op = Operation()) const
  {
    return exists_arc(op);
  }
 
  template <class Operation>
  bool exists_arc(Node *p, Operation & op) const
  {
    return not traverse_arcs(p, [&op](Arc *a) { return not op(a); });
  }
 
  template <class Operation>
  bool exists_arc(Node *p, Operation && op = Operation()) const
  {
    return exists_arc(p, op);
  }
 
  template <class Operation>
  bool none_node(Operation & op) const
  {
    return not exists_node(op);
  }
 
  template <class Operation>
  bool none_node(Operation && op) const
  {
    return none_node(op);
  }
 
  template <class Operation>
  bool none_arc(Operation & op) const
  {
    return not exists_arc(op);
  }
 
  template <class Operation>
  bool none_arc(Operation && op) const
  {
    return none_arc(op);
  }
 
  template <class Operation>
  bool none_arc(Node *p, Operation & op) const
  {
    return not exists_arc(p, op);
  }
 
  template <class Operation>
  bool none_arc(Node *p, Operation && op) const
  {
    return none_arc(p, op);
  }
 
  template <class Operation = std::function<bool(Node*)>>
  size_t count_nodes(Operation op = [](Node*) { return true; }) const
  {
    size_t count = 0;
    for_each_node([&count, &op](Node *p) { if (op(p)) ++count; });
    return count;
  }
 
  template <class Operation = std::function<bool(Arc*)>>
  size_t count_arcs(Operation op = [](Arc*) { return true; }) const
  {
    size_t count = 0;
    for_each_arc([&count, &op](Arc *a) { if (op(a)) ++count; });
    return count;
  }
 
  template <class Operation = std::function<bool(Arc*)>>
  size_t count_arcs(Node *p, Operation op = [](Arc*) { return true; }) const
  {
    size_t count = 0;
    for_each_arc(p, [&count, &op](Arc *a) { if (op(a)) ++count; });
    return count;
  }
 
  template <typename T = double, class Extract>
  T sum_arcs(Node *p, Extract extract) const
  {
    T sum = T{0};
    for_each_arc(p, [&sum, &extract](Arc *a) { sum += extract(a); });
    return sum;
  }
  
  template <typename T = double>
  T sum_arcs(Node *p) const
  {
    T sum = T{0};
    for_each_arc(p, [&sum](Arc *a) { sum += static_cast<T>(a->get_info()); });
    return sum;
  }
 
  template <class Compare = std::function<bool(Arc*, Arc*)>>
  Arc* min_arc(Node *p, Compare cmp = [](Arc *a, Arc *b) { 
    return a->get_info() < b->get_info(); 
  }) const
  {
    Arc* result = nullptr;
    for_each_arc(p, [&result, &cmp](Arc *a) {
      if (result == nullptr or cmp(a, result))
        result = a;
    });
    return result;
  }
 
  template <class Compare = std::function<bool(Arc*, Arc*)>>
  Arc* max_arc(Node *p, Compare cmp = [](Arc *a, Arc *b) { 
    return a->get_info() < b->get_info(); 
  }) const
  {
    Arc* result = nullptr;
    for_each_arc(p, [&result, &cmp](Arc *a) {
      if (result == nullptr or cmp(result, a))
        result = a;
    });
    return result;
  }
 
  template <class Compare = std::function<bool(Arc*, Arc*)>>
  Arc* min_arc(Compare cmp = [](Arc *a, Arc *b) { 
    return a->get_info() < b->get_info(); 
  }) const
  {
    Arc* result = nullptr;
    for_each_arc([&result, &cmp](Arc *a) {
      if (result == nullptr or cmp(a, result))
        result = a;
    });
    return result;
  }
 
  template <class Compare = std::function<bool(Arc*, Arc*)>>
  Arc* max_arc(Compare cmp = [](Arc *a, Arc *b) { 
    return a->get_info() < b->get_info(); 
  }) const
  {
    Arc* result = nullptr;
    for_each_arc([&result, &cmp](Arc *a) {
      if (result == nullptr or cmp(result, a))
        result = a;
    });
    return result;
  }
 
  template <class Operation>
  std::pair<DynList<Node*>, DynList<Node*>> partition_nodes(Operation op) const
  {
    DynList<Node*> yes, no;
    for_each_node([&yes, &no, &op](Node *p) {
      if (op(p))
        yes.append(p);
      else
        no.append(p);
    });
    return {std::move(yes), std::move(no)};
  }
 
  template <class Operation>
  std::pair<DynList<Arc*>, DynList<Arc*>> partition_arcs(Operation op) const
  {
    DynList<Arc*> yes, no;
    for_each_arc([&yes, &no, &op](Arc *a) {
      if (op(a))
        yes.append(a);
      else
        no.append(a);
    });
    return {std::move(yes), std::move(no)};
  }
 
  DynList<Node*> adjacent_nodes(Node *p) const
  {
    DynList<Node*> result;
    for_each_arc(p, [this, p, &result](Arc *a) {
      result.append(get_connected_node(a, p));
    });
    return result;
  }
 
  template <class Op>
  Node * search_node(Op & op) const
  {
    for (typename GT::Node_Iterator it(*const_me()); it.has_curr(); it.next_ne())
      {
        auto p = it.get_curr();
        if (op(p))
          return p;
      }
    return nullptr;
  }
 
  template <class Op>
  Node * search_node(Op && op) const
  {
    return search_node(op);
  }
 
  Node * find_node(const Node_Type & info) const noexcept
  {
    return search_node([&info](auto p) { return p->get_info() == info; });
  }
 
  template <class Op>
  Arc * search_arc(Op & op) const
  {
    for (typename GT::Arc_Iterator it(*const_me()); it.has_curr(); it.next_ne())
      {
        auto a = it.get_curr();
        if (op(a))
          return a;
      }
    return nullptr;
  }
 
  template <class Op>
  Arc * search_arc(Op && op) const
  {
    return search_arc(op);
  }
 
  Arc * find_arc(const Arc_Type & info) const noexcept
  {
    return search_arc([&info](auto a) { return a->get_info() == info; });
  }
 
  template <class Operation>
  Arc * search_arc(Node *p, Operation & op) const
  {
    for (typename GT::Node_Arc_Iterator it(p); it.has_curr(); it.next_ne())
      {
        Arc *arc = it.get_curr();
        if (op(arc))
          return arc;
      }
    return nullptr;
  }
 
  template <class Operation>
  Arc * search_arc(Node *p, Operation && op = Operation()) const
  {
    return search_arc(p, op);
  }
 
  Arc * search_arc(Node *src, Node *tgt) const noexcept
  {
    for (typename GT::Node_Arc_Iterator it(src); it.has_curr(); it.next_ne())
      if (it.get_tgt_node_ne() == tgt)
        return it.get_curr();
    return nullptr;
  }
 
  template <template <typename> class Container = Aleph::DynList>
  Container<Node *> nodes() const
  {
    Container<Node *> ret;
    for_each_node([&ret](Node *p) { ret.append(p); });
    return ret;
  }
 
  template <template <typename> class Container = Aleph::DynList>
  Container<Arc *> arcs() const
  {
    Container<Arc *> ret;
    for_each_arc([&ret](Arc *a) { ret.append(a); });
    return ret;
  }
 
  template <template <typename> class Container = Aleph::DynList>
  Container<Arc *> arcs(Node *p) const
  {
    Container<Arc *> ret;
    this->for_each_arc(p, [&ret](Arc *a) { ret.append(a); });
    return ret;
  }
 
  auto get_node_it() const noexcept
  {
    return typename GT::Node_Iterator(*const_me());
  }
 
  auto get_arc_it() const noexcept
  {
    return typename GT::Arc_Iterator(*const_me());
  }
 
  auto get_arc_it(Node *p) const noexcept
  {
    return typename GT::Node_Arc_Iterator(p);
  }
 
  struct In_Filt
  {
    Node *tgt = nullptr; 
 
    In_Filt(Node *__tgt = nullptr) noexcept : tgt(__tgt)
    { /* empty */
    }
 
    bool operator ()(Arc *a) const noexcept
    {
      assert(tgt);
      return a->tgt_node == tgt;
    }
 
    Node * get_node(Arc *a) const noexcept
    {
      assert(tgt);
      return (typename GT::Node *) a->src_node;
    }
  };
 
  struct Out_Filt
  {
    Node *src = nullptr; 
 
    Out_Filt(Node *__src) noexcept : src(__src)
    { /* empty */
    }
 
    bool operator ()(Arc *a) const noexcept
    {
      assert(src);
      return a->src_node == src;
    }
 
    Node * get_node(Arc *a) const noexcept
    {
      assert(src);
      return (Node *) a->tgt_node;
    }
  };
 
  template <class Filter>
  class Digraph_Iterator
  {
    using Itor = Filter_Iterator<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(Node *p) : filt(p), it(p, filt)
    {
      // empty
    }
 
    void next_ne() noexcept { it.next_ne(); }
 
    void next() { it.next(); }
 
    void prev() { it.prev(); }
 
    void prev_ne() { it.prev_ne(); }
 
    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(); }
 
    auto get_current_arc_ne() const noexcept { return get_curr_ne(); }
 
    typename GT::Node * get_node(typename GT::Arc *a) const noexcept
    {
      return filt.get_node(a);
    }
 
    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(); }
 
    typename GT::Node * get_node() const
    {
      return this->get_node(this->get_curr());
    }
 
    auto get_tgt_node() const { return get_node(); }
 
    void reset_first() noexcept { it.reset_first(); }
 
    void reset_last() noexcept { it.reset_last(); }
  };
 
  // template <class Filt> using Filter_Iterator = Digraph_Iterator<Filt>;
 
  // /** Iterator on incoming arcs of node */
  struct In_Iterator : Digraph_Iterator<In_Filt>
  {
    using Digraph_Iterator<In_Filt>::Digraph_Iterator;
  };
 
  // /** Iterator on incoming arcs of node */
  struct Out_Iterator : Digraph_Iterator<Out_Filt>
  {
    using Digraph_Iterator<Out_Filt>::Digraph_Iterator;
  };
 
  In_Iterator get_in_it(Node *p) const noexcept { return In_Iterator(p); }
 
  Out_Iterator get_out_it(Node *p) const noexcept { return Out_Iterator(p); }
 
  Arc * search_directed_arc(Node *src, Node *tgt) const noexcept
  {
    for (typename GT::Out_Iterator it(src); it.has_curr(); it.next_ne())
      if (it.get_tgt_node() == tgt)
        return it.get_curr();
    return nullptr;
  }
 
  DynList<Node *> in_nodes(Node *p) const
  {
    DynList<Node *> ret;
    for (In_Iterator it(p); it.has_curr(); it.next_ne())
      ret.append(it.get_node());
    return ret;
  }
 
  DynList<Node *> out_nodes(Node *p) const
  {
    DynList<Node *> ret;
    for (Out_Iterator it(p); it.has_curr(); it.next_ne())
      ret.append(it.get_node_ne());
    return ret;
  }
 
  DynList<Arc *> out_arcs(Node *p) const
  {
    DynList<Arc *> ret;
    for (Out_Iterator it(p); it.has_curr(); it.next_ne())
      ret.append(it.get_curr());
    return ret;
  }
 
  DynList<Arc *> in_arcs(Node *p) const
  {
    DynList<Arc *> ret;
    for (In_Iterator it(p); it.has_curr(); it.next_ne())
      ret.append(it.get_curr());
    return ret;
  }
 
  using ArcPair = std::tuple<Arc *, Node *>;
 
  auto in_pairs(Node *p) const
  {
    DynList<ArcPair> ret;
    for (In_Iterator it(p); it.has_curr(); it.next_ne())
      {
        auto a = it.get_curr();
        ret.append(std::make_tuple(a, (Node *) a->get_connected_node(p)));
      }
    return ret;
  }
 
  auto out_pairs(Node *p) const
  {
    DynList<ArcPair> ret;
    for (Out_Iterator it(p); it.has_curr(); it.next_ne())
      {
        auto a = it.get_curr();
        ret.append(std::make_tuple(a, (Node *) a->get_connected_node(p)));
      }
    return ret;
  }
 
  size_t in_degree(Node *p) const noexcept
  {
    size_t count = 0;
    for (In_Iterator it(p); it.has_curr(); it.next_ne())
      ++count;
    return count;
  }
 
  size_t out_degree(Node *p) const noexcept
  {
    size_t count = 0;
    for (Out_Iterator it(p); it.has_curr(); it.next_ne())
      ++count;
    return count;
  }
 
  template <class Itor, class Operation>
  bool traverse_arcs(Node *p, Operation & op) const
  {
    for (Itor it(p); it.has_curr(); it.next_ne())
      if (not op(it.get_curr()))
        return false;
    return true;
  }
 
  template <class Itor, class Operation>
  void for_each_arc(Node *p, Operation & op) const
  {
    for (Itor it(p); it.has_curr(); it.next_ne())
      op(it.get_curr());
  }
 
  template <class Op>
  bool traverse_in_arcs(Node *p, Op & op) const
  {
    return traverse_arcs<In_Iterator, Op>(p, op);
  }
 
  template <class Op>
  bool traverse_in_arcs(Node *p, Op && op = Op()) const
  {
    return traverse_in_arcs(p, op);
  }
 
  template <class Op>
  void for_each_in_arc(Node *p, Op & op) const
  {
    for_each_arc<In_Iterator>(p, op);
  }
 
  template <class Op>
  void for_each_in_arc(Node *p, Op && op = Op()) const
  {
    for_each_in_arc(p, op);
  }
 
  template <class Op>
  bool all_in_arcs(Node *p, Op & op) const
  {
    return traverse_in_arcs(p, [&op](auto a) { return op(a); });
  }
 
  template <class Op>
  bool all_in_arcs(Node *p, Op && op = Op()) const
  {
    return all_in_arcs(p, op);
  }
 
  template <class Op>
  bool exists_in_arc(Node *p, Op & op) const
  {
    return not traverse_in_arcs(p, [&op](auto a) { return not op(a); });
  }
 
  template <class Op>
  bool exists_in_arc(Node *p, Op && op = Op()) const
  {
    return exists_in_arc(p, op);
  }
 
  template <class Op>
  auto search_in_arc(Node *p, Op & op) const
  {
    Arc *ret = nullptr;
    traverse_in_arcs(p, [&op, &ret](auto a)
                       {
                         if (op(a))
                           {
                             ret = a;
                             return false;
                           }
                         return true;
                       });
    return ret;
  }
 
  template <class Op>
  auto search_in_arc(Node *p, Op && op = Op()) const
  {
    return search_in_arc(p, op);
  }
 
  template <typename T>
  auto in_arcs_map(Node *p, std::function<T(Arc *)> op) const
  {
    DynList<T> ret;
    for_each_in_arc(p, [&ret, &op](auto a) { ret.append(op(a)); });
    return ret;
  }
 
  template <typename T = Arc_Type>
  T foldl_in_arcs(Node *p, const T & init,
                  std::function<T(const T &, Arc *)> op) const
  {
    T ret = init;
    for_each_in_arc(p, [&ret, &op](auto a) { ret = op(ret, a); });
    return ret;
  }
 
  template <class Op>
  DynList<Arc *> filter_in_arcs(Node *p, Op & op) const
  {
    DynList<Arc *> ret;
    for_each_in_arc(p, [&ret, &op](auto a)
                      {
                        if (op(a))
                          ret.append(a);
                      });
    return ret;
  }
 
  template <class Op>
  auto filter_in_arcs(Node *p, Op && op = Op()) const
  {
    return filter_in_arcs(p, op);
  }
 
  template <class Op>
  bool traverse_out_arcs(Node *p, Op & op) const
  {
    return traverse_arcs<Out_Iterator>(p, op);
  }
 
  template <class Op>
  bool traverse_out_arcs(Node *p, Op && op = Op()) const
  {
    return traverse_out_arcs(p, op);
  }
 
  template <class Op>
  void for_each_out_arc(Node *p, Op & op) const
  {
    for_each_arc<Out_Iterator>(p, op);
  }
 
  template <class Op>
  void for_each_out_arc(Node *p, Op && op = Op()) const
  {
    for_each_out_arc(p, op);
  }
 
  template <class Op>
  bool all_out_arcs(Node *p, Op & op) const
  {
    return traverse_out_arcs(p, [&op](auto a) { return op(a); });
  }
 
  template <class Op>
  bool all_out_arcs(Node *p, Op && op = Op()) const
  {
    return all_out_arcs(p, op);
  }
 
  template <class Op>
  bool exists_out_arc(Node *p, Op & op) const
  {
    return not traverse_out_arcs(p, [&op](auto a) { return not op(a); });
  }
 
  template <class Op>
  bool exists_out_arc(Node *p, Op && op = Op()) const
  {
    return exists_out_arc(p, op);
  }
 
  template <class Op>
  auto search_out_arc(Node *p, Op & op) const
  {
    typename GT::Arc *ret = nullptr;
    traverse_out_arcs(p, [&op, &ret](auto a)
                        {
                          if (op(a))
                            {
                              ret = a;
                              return false;
                            }
                          return true;
                        });
    return ret;
  }
 
  template <class Op>
  auto search_out_arc(Node *p, Op && op = Op()) const
  {
    return search_out_arc(p, op);
  }
 
  template <typename T = Arc_Type>
  auto out_arcs_map(Node *p, std::function<T(Arc *)> op) const
  {
    DynList<T> ret;
    for_each_out_arc(p, [&ret, &op](auto a) { ret.append(op(a)); });
    return ret;
  }
 
  template <typename T = Arc_Type>
  T foldl_out_arcs(Node *p, const T & init,
                   std::function<T(const T &, Arc *)> op) const
  {
    T ret = init;
    for_each_out_arc(p, [&ret, &op](auto a) { ret = op(ret, a); });
    return ret;
  }
 
  template <class Op>
  DynList<Arc *> filter_out_arcs(Node *p, Op & op) const
  {
    DynList<Arc *> ret;
    for_each_out_arc(p, [&ret, &op](auto a)
                       {
                         if (op(a))
                           ret.append(a);
                       });
    return ret;
  }
 
  template <class Op>
  auto filter_out_arcs(Node *p, Op && op = Op()) const
  {
    return filter_out_arcs(p, op);
  }
 
  // ===========================================================================
  // Arc Removal Helpers (protected, for use in remove_node implementations)
  // ===========================================================================
 
protected:
  template <class Predicate>
  DynList<Arc*> collect_arcs_if(Predicate pred) const
  {
    DynList<Arc*> result;
    for (typename GT::Arc_Iterator it(*const_me()); it.has_curr(); it.next_ne())
      if (pred(it.get_curr_ne()))
        result.append(it.get_curr_ne());
    return result;
  }
 
  template <class Predicate>
  void remove_arcs_if(Predicate pred)
  {
    collect_arcs_if(pred).for_each([this](auto a) { me()->remove_arc(a); });
  }
 
public:
  // ===========================================================================
  // Sorting Methods (for Dlink-based graphs)
  // ===========================================================================
 
  template <class U>
  static constexpr bool has_node_dlink_v =
    requires(U & u) { { u.get_node_dlink() } -> std::same_as<Dlink&>; };
 
  template <class U>
  static constexpr bool has_arc_dlink_v =
    requires(U & u) { { u.get_arc_dlink() } -> std::same_as<Dlink&>; };
 
  template <class Compare>
  void sort_nodes(Compare & cmp) noexcept
    requires(has_node_dlink_v<GT>)
  {
    Cmp_Dlink_Node<GT, Compare> c = cmp;
    mergesort(me()->get_node_dlink(), c);
  }
 
  template <class Compare>
  void sort_nodes(Compare && cmp = Compare()) noexcept
    requires(has_node_dlink_v<GT>)
  {
    sort_nodes(cmp);
  }
 
  template <class Compare>
  void sort_arcs(Compare & cmp) noexcept
    requires(has_arc_dlink_v<GT>)
  {
    Cmp_Dlink_Arc<GT, Compare> c = cmp;
    mergesort(me()->get_arc_dlink(), c);
  }
 
  template <class Compare>
  void sort_arcs(Compare && cmp = Compare()) noexcept
    requires(has_arc_dlink_v<GT>)
  {
    sort_arcs(cmp);
  }
};
 
 
// ============================================================================
// Macro for Copy/Move/Swap Pattern
// ============================================================================
 
#define ALEPH_GRAPH_COPY_MOVE_CTORS(GraphClass)                              \
                 \
  GraphClass(const GraphClass & g)                                           \
  {                                                                          \
    copy_graph(*this, g);                                                    \
  }                                                                          \
                                                                             \
                       \
  GraphClass(GraphClass && g) noexcept                                       \
  {                                                                          \
    swap(g);                                                                 \
  }                                                                          \
                                                                             \
           \
  GraphClass & operator=(const GraphClass & g)                               \
  {                                                                          \
    if (this == &g)                                                          \
      return *this;                                                          \
    copy_graph(*this, g);                                                    \
    return *this;                                                            \
  }                                                                          \
                                                                             \
                        \
  GraphClass & operator=(GraphClass && g) noexcept                           \
  {                                                                          \
    swap(g);                                                                 \
    return *this;                                                            \
  }
 
 
namespace Aleph
{
 
template <class BaseGraph>
class Digraph : public BaseGraph
{
public:
  using GT = BaseGraph;
  using Node = typename BaseGraph::Node;
  using Arc = typename BaseGraph::Arc;
 
  Digraph() noexcept
  {
    this->digraph = true;
  }
 
  Digraph(const Digraph & dg) : GT()
  {
    this->digraph = true;
    copy_graph(*this, dg, false);
  }
 
  Digraph(Digraph && dg) noexcept : GT()
  {
    this->digraph = true;
    this->swap(dg);
  }
 
  Digraph & operator = (const Digraph & g)
  {
    if (this == &g)
      return *this;
 
    this->digraph = true;
    copy_graph(*this, g, false);
 
    return *this;
  }
 
  Digraph & operator = (Digraph && g) noexcept
  {
    this->digraph = true;
    this->swap(g);
 
    return *this;
  }
};
 
} // namespace Aleph
 
 
# endif // GRAPH_DRY_H