word-graph.hpp

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2019-2025 Finn Smith + James D. Mitchell
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.
//
 
// This file contains declarations related to word graphs (which are basically
// deterministic automata without initial or accept states).
 
#ifndef LIBSEMIGROUPS_WORD_GRAPH_HPP_
#define LIBSEMIGROUPS_WORD_GRAPH_HPP_
 
#include <algorithm>      // for uniform_int_distribution
#include <cstddef>        // for size_t
#include <cstdint>        // for uint32_t
#include <ostream>        // for operator<<
#include <queue>          // for queue
#include <random>         // for mt19937
#include <stack>          // for stack
#include <string>         // for to_string
#include <tuple>          // for tie
#include <type_traits>    // for is_integral, is_unsigned
#include <unordered_set>  // for unordered_set
#include <utility>        // for pair
#include <vector>         // for vector
 
#include "config.hpp"                // for LIBSEMIGROUPS_EIGEN_EN...
#include "constants.hpp"             // for UNDEFINED
#include "debug.hpp"                 // for LIBSEMIGROUPS_ASSERT
#include "dot.hpp"                   // for Dot
#include "exception.hpp"             // for LIBSEMIGROUPS_EXCEPTION
#include "forest.hpp"                // for Forest
#include "is_specialization_of.hpp"  // for is_specialization_of_v
#include "order.hpp"                 // for Order
#include "ranges.hpp"                // for ??
#include "types.hpp"                 // for word_type, enable_if_is_same
 
#include "detail/containers.hpp"  // for DynamicArray2
#include "detail/int-range.hpp"   // for IntRange
#include "detail/stl.hpp"         // for IsIterator
#include "detail/uf.hpp"          // for Duf
 
#ifdef LIBSEMIGROUPS_EIGEN_ENABLED
#include "detail/eigen.hpp"
#else
#include "matrix.hpp"
#endif
 
namespace libsemigroups {


  template <typename Node>
  class WordGraph {
    static_assert(std::is_integral<Node>(),
                  "the template parameter Node must be an integral type!");
    static_assert(
        std::is_unsigned<Node>(),
        "the template parameter Node must be an unsigned integral type!");
 
    template <typename N>
    friend class WordGraph;
 
   public:
    // WordGraph - typedefs - public

    using node_type = Node;

    using label_type = Node;

    using size_type = std::size_t;
 
#ifdef LIBSEMIGROUPS_EIGEN_ENABLED
    using adjacency_matrix_type
        = Eigen::Matrix<double, Eigen::Dynamic, Eigen::Dynamic>;
#else
    using adjacency_matrix_type = IntMat<0, 0, int64_t>;
#endif

    using const_iterator_nodes =
        typename detail::IntRange<Node>::const_iterator;

    using const_reverse_iterator_nodes =
        typename detail::IntRange<Node>::const_reverse_iterator;

    using const_iterator_targets =
        typename detail::DynamicArray2<Node>::const_iterator;
 
   protected:
    // WordGraph - data members - protected
 
    mutable detail::DynamicArray2<Node> _dynamic_array_2;
 
   private:
    // WordGraph - data members - private
 
    size_type _degree;
    size_type _nr_nodes;
    // TODO(1) remove when WordGraphView is implemented
    size_type _num_active_nodes;
 
   public:
    // WordGraph - constructors + destructor - public

    // Not noexcept
    explicit WordGraph(size_type m = 0, size_type n = 0);

    WordGraph& init(size_type m = 0, size_type n = 0);

    WordGraph(WordGraph const&);

    template <typename OtherNode>
    WordGraph(WordGraph<OtherNode> const& that);

    template <typename OtherNode>
    WordGraph& init(WordGraph<OtherNode> const& that);

    WordGraph(WordGraph&&);

    WordGraph& operator=(WordGraph const&);

    WordGraph& operator=(WordGraph&&);
 
    ~WordGraph();

    static WordGraph random(size_type    number_of_nodes,
                            size_type    out_degree,
                            std::mt19937 mt
                            = std::mt19937(std::random_device()()));

    // Not noexcept because DynamicArray2::add_cols isn't.
    WordGraph& reserve(size_type m, size_type n);

    // WordGraph - modifiers - public

    // Not noexcept because DynamicArray2::add_rows isn't.
    WordGraph& add_nodes(size_type nr);

    // Not noexcept because DynamicArray2::add_cols isn't.
    WordGraph& add_to_out_degree(size_type nr);

    // Not noexcept because throw_if_node_out_of_bounds/label aren't
    // return *this by reference.
    WordGraph& target(node_type s, label_type a, node_type t);

    //! No checks whatsoever on the validity of the arguments are performed.
    inline WordGraph& target_no_checks(node_type s, label_type a, node_type t) {
      _dynamic_array_2.set(s, a, t);
      return *this;
    }

    //! No checks whatsoever on the validity of the arguments are performed.
    inline WordGraph& remove_target_no_checks(node_type s, label_type a) {
      _dynamic_array_2.set(s, a, UNDEFINED);
      return *this;
    }

    WordGraph& remove_target(node_type s, label_type a);

    WordGraph& remove_label(label_type a);

    WordGraph& remove_label_no_checks(label_type a);

    //! out-degree.
    inline WordGraph& remove_all_targets() {
      std::fill(_dynamic_array_2.begin(), _dynamic_array_2.end(), UNDEFINED);
      return *this;
    }

    // swap m - a - > m' and n - a -> n'
    WordGraph& swap_targets_no_checks(node_type m, node_type n, label_type a) {
      _dynamic_array_2.swap(m, a, n, a);
      return *this;
    }

    WordGraph& swap_targets(node_type m, node_type n, label_type a);

    //! is the out-degree of the word graph.
    [[nodiscard]] bool operator==(WordGraph const& that) const {
      return _dynamic_array_2 == that._dynamic_array_2;
    }

    //! is the out-degree of the word graph.
    [[nodiscard]] bool operator!=(WordGraph const& that) const {
      return !operator==(that);
    }

    //! is the out-degree of the word graph.
    [[nodiscard]] bool operator<(WordGraph const& that) const {
      return _dynamic_array_2 < that._dynamic_array_2;
    }

    //! is the out-degree of the word graph.
    [[nodiscard]] bool operator<=(WordGraph const& that) const {
      return _dynamic_array_2 <= that._dynamic_array_2;
    }

    //! is the out-degree of the word graph.
    [[nodiscard]] bool operator>(WordGraph const& that) const {
      return _dynamic_array_2 > that._dynamic_array_2;
    }

    //! is the out-degree of the word graph.
    [[nodiscard]] bool operator>=(WordGraph const& that) const {
      return _dynamic_array_2 > that._dynamic_array_2;
    }

    // not noexcept because Hash<T>::operator() isn't
    [[nodiscard]] size_t hash_value() const {
      return std::hash<decltype(_dynamic_array_2)>()(_dynamic_array_2);
    }

    // WordGraph - nodes, targets, etc - public

    // Not noexcept because throw_if_node_out_of_bounds/label aren't
    [[nodiscard]] node_type target(node_type source, label_type a) const;

    // Not noexcept because DynamicArray2::get is not
    [[nodiscard]] node_type inline target_no_checks(node_type  s,
                                                    label_type a) const {
      return _dynamic_array_2.get(s, a);
    }

    // Not noexcept because DynamicArray2::get is not
    [[nodiscard]] std::pair<label_type, node_type>
    next_label_and_target_no_checks(node_type s, label_type a) const;

    // Not noexcept because next_label_and_target_no_checks is not
    [[nodiscard]] std::pair<label_type, node_type>
    next_label_and_target(node_type s, label_type a) const;

    //! Constant.
    [[nodiscard]] size_type inline number_of_nodes() const noexcept {
      return _nr_nodes;
    }
 
#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
    WordGraph& number_of_active_nodes(size_type val) {
      _num_active_nodes = val;
      return *this;
    }
 
    [[nodiscard]] size_type inline number_of_active_nodes() const noexcept {
      return _num_active_nodes;
    }
#endif

    // Not noexcept because std::count isn't
    [[nodiscard]] size_type number_of_edges() const;

    [[nodiscard]] size_type number_of_edges(node_type s) const;

    [[nodiscard]] size_type number_of_edges_no_checks(node_type s) const;

    //! Constant.
    [[nodiscard]] size_type out_degree() const noexcept {
      return _degree;
    }

    //! Constant.
    const_iterator_nodes cbegin_nodes() const noexcept {
      return detail::IntRange<node_type>(0, number_of_nodes()).cbegin();
    }

    //! Constant.
    [[nodiscard]] const_iterator_nodes cend_nodes() const noexcept {
      return detail::IntRange<node_type>(0, number_of_nodes()).cend();
    }

    // Not noexcept because throw_if_node_out_of_bounds isn't
    [[nodiscard]] const_iterator_targets cbegin_targets(node_type source) const;

    [[nodiscard]] const_iterator_targets
    cbegin_targets_no_checks(node_type source) const noexcept {
      return _dynamic_array_2.cbegin_row(source);
    }

    // Not noexcept because throw_if_node_out_of_bounds isn't
    [[nodiscard]] const_iterator_targets cend_targets(node_type source) const;

    [[nodiscard]] const_iterator_targets
    cend_targets_no_checks(node_type source) const noexcept {
      return _dynamic_array_2.cbegin_row(source) + _degree;
    }

    //! \noexcept
    [[nodiscard]] auto nodes() const noexcept {
      return rx::seq<node_type>() | rx::take(number_of_nodes());
    }

    //! \noexcept
    [[nodiscard]] auto labels() const noexcept {
      return rx::seq<label_type>() | rx::take(out_degree());
    }

    [[nodiscard]] rx::iterator_range<const_iterator_targets>
    targets_no_checks(node_type source) const noexcept {
      return rx::iterator_range(cbegin_targets_no_checks(source),
                                cend_targets_no_checks(source));
    }

    [[nodiscard]] rx::iterator_range<const_iterator_targets>
    targets(node_type source) const;

    [[nodiscard]] auto
    labels_and_targets_no_checks(node_type source) const noexcept {
      return rx::zip(rx::seq<node_type>(), targets_no_checks(source));
    }

    [[nodiscard]] auto labels_and_targets(node_type source) const;

    WordGraph& induced_subgraph_no_checks(node_type first, node_type last);

    WordGraph& induced_subgraph(node_type first, node_type last);

    template <typename Iterator,
              typename = std::enable_if_t<detail::IsIterator<Iterator>::value>>
    WordGraph& induced_subgraph_no_checks(Iterator first, Iterator last);

    template <typename Iterator,
              typename = std::enable_if_t<detail::IsIterator<Iterator>::value>>
    WordGraph& induced_subgraph(Iterator first, Iterator last);

    WordGraph& disjoint_union_inplace_no_checks(WordGraph<Node> const& that);

    WordGraph& disjoint_union_inplace(WordGraph<Node> const& that);
 
#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
    // These are currently undocumented, because they are hard to use correctly,
    // shouldn't p and q be actual permutation objects?
 
    // requires access to _dynamic_array_2 so can't be helper
    WordGraph& permute_nodes_no_checks(std::vector<node_type> const& p,
                                       std::vector<node_type> const& q,
                                       size_t                        m);
 
    WordGraph& permute_nodes_no_checks(std::vector<node_type> const& p,
                                       std::vector<node_type> const& q) {
      return permute_nodes_no_checks(p, q, p.size());
    }
 
    WordGraph& standardize(std::vector<node_type> const& p,
                           std::vector<node_type> const& q) {
      return permute_nodes_no_checks(p, q, p.size());
    }
#endif
  };  // WordGraph

  namespace word_graph {

    // WordGraph - helper functions - in alphabetical order!!!

    // TODO(1) add add_cycle with checks version.
    template <typename Node, typename Iterator>
    void add_cycle_no_checks(WordGraph<Node>& wg,
                             Iterator         first,
                             Iterator         last);

    template <typename Node>
    void add_cycle(WordGraph<Node>& wg, size_t N) {
      size_t M = wg.number_of_nodes();
      wg.add_nodes(N);
      add_cycle_no_checks(wg, wg.cbegin_nodes() + M, wg.cend_nodes());
    }

    template <typename Node>
    [[nodiscard]] auto adjacency_matrix(WordGraph<Node> const& wg);

    template <typename Node>
    [[nodiscard]] Dot dot(WordGraph<Node> const& wg);

    template <typename Node>
    [[nodiscard]] bool equal_to_no_checks(WordGraph<Node> const& x,
                                          WordGraph<Node> const& y,
                                          Node                   first,
                                          Node                   last);

    template <typename Node>
    [[nodiscard]] bool equal_to(WordGraph<Node> const& x,
                                WordGraph<Node> const& y,
                                Node                   first,
                                Node                   last);

    template <typename Node1, typename Node2, typename Iterator>
    [[nodiscard]] Node1 follow_path(WordGraph<Node1> const& wg,
                                    Node2                   source,
                                    Iterator                first,
                                    Iterator                last);

    // TODO(2) example
    // not noexcept because WordGraph::target isn't
    template <typename Node1, typename Node2>
    [[nodiscard]] Node1 follow_path(WordGraph<Node1> const& wg,
                                    Node2                   from,
                                    word_type const&        path) {
      static_assert(sizeof(Node2) <= sizeof(Node1));
      return follow_path(wg, from, path.cbegin(), path.cend());
    }

    template <typename Node1, typename Node2, typename Iterator>
    [[nodiscard]] Node1 follow_path_no_checks(WordGraph<Node1> const& wg,
                                              Node2                   from,
                                              Iterator                first,
                                              Iterator last) noexcept;

    template <typename Node1, typename Node2>
    [[nodiscard]] Node1 follow_path_no_checks(WordGraph<Node1> const& wg,
                                              Node2                   from,
                                              word_type const& path) noexcept {
      static_assert(sizeof(Node2) <= sizeof(Node1));
      return follow_path_no_checks(wg, from, path.cbegin(), path.cend());
    }

    // Not noexcept because detail::is_acyclic isn't
    template <typename Node>
    [[nodiscard]] bool is_acyclic(WordGraph<Node> const& wg);

    // Not noexcept because detail::is_acyclic isn't
    template <typename Node1, typename Node2>
    [[nodiscard]] bool is_acyclic(WordGraph<Node1> const& wg, Node2 source);

    // Not noexcept because detail::is_acyclic isn't
    template <typename Node1, typename Node2>
    [[nodiscard]] bool is_acyclic(WordGraph<Node1> const& wg,
                                  Node2                   source,
                                  Node2                   target);

    // TODO(1) add a version of this function with one that returns a float
    // representing the proportion of the nodes in the range that are compatible
    // with the rules. Don't replace the current version because it can return
    // early knowing that it isn't compatible.
    template <typename Node,
              typename Iterator1,
              typename Iterator2,
              typename Iterator3>
    [[nodiscard]] bool is_compatible_no_checks(WordGraph<Node> const& wg,
                                               Iterator1 first_node,
                                               Iterator2 last_node,
                                               Iterator3 first_rule,
                                               Iterator3 last_rule);

    template <
        typename Node,
        typename Iterator1,
        typename Iterator2,
        typename Iterator3,
        std::enable_if_t<!std::is_same_v<std::decay_t<Iterator3>, word_type>>>
    [[nodiscard]] bool is_compatible(WordGraph<Node> const& wg,
                                     Iterator1              first_node,
                                     Iterator2              last_node,
                                     Iterator3              first_rule,
                                     Iterator3              last_rule);

    template <typename Node, typename Iterator1, typename Iterator2>
    bool is_compatible_no_checks(WordGraph<Node> const& wg,
                                 Iterator1              first_node,
                                 Iterator2              last_node,
                                 word_type const&       lhs,
                                 word_type const&       rhs);

    template <typename Node, typename Iterator1, typename Iterator2>
    bool is_compatible(WordGraph<Node> const& wg,
                       Iterator1              first_node,
                       Iterator2              last_node,
                       word_type const&       lhs,
                       word_type const&       rhs);

    template <typename Node, typename Iterator1, typename Iterator2>
    [[nodiscard]] bool is_complete_no_checks(WordGraph<Node> const& wg,
                                             Iterator1              first_node,
                                             Iterator2              last_node);

    template <typename Node, typename Iterator1, typename Iterator2>
    [[nodiscard]] bool is_complete(WordGraph<Node> const& wg,
                                   Iterator1              first_node,
                                   Iterator2              last_node);

    template <typename Node>
    [[nodiscard]] bool is_complete(WordGraph<Node> const& wg) noexcept {
      return wg.number_of_edges() == wg.number_of_nodes() * wg.out_degree();
    }

    template <typename Node>
    [[nodiscard]] bool is_connected(WordGraph<Node> const& wg);

    template <typename Node1, typename Node2>
    [[nodiscard]] bool is_reachable_no_checks(WordGraph<Node1> const& wg,
                                              Node2                   source,
                                              Node2                   target);

    template <typename Node1, typename Node2>
    [[nodiscard]] bool is_reachable(WordGraph<Node1> const& wg,
                                    Node2                   source,
                                    Node2                   target);

    // TODO(1) should have a version that returns the node that everything is
    // reachable from
    template <typename Node>
    [[nodiscard]] bool is_strictly_cyclic(WordGraph<Node> const& wg);

    template <typename Node1, typename Node2, typename Iterator>
    [[nodiscard]] std::pair<Node1, Iterator>
    last_node_on_path_no_checks(WordGraph<Node1> const& wg,
                                Node2                   source,
                                Iterator                first,
                                Iterator                last) noexcept;

    template <typename Node1, typename Node2, typename Iterator>
    [[nodiscard]] std::pair<Node1, Iterator>
    last_node_on_path(WordGraph<Node1> const& wg,
                      Node2                   source,
                      Iterator                first,
                      Iterator                last);

    template <typename Node1, typename Node2>
    std::pair<Node1, word_type::const_iterator>
    last_node_on_path_no_checks(WordGraph<Node1> const& wg,
                                Node2                   source,
                                word_type const&        w);

    template <typename Node1, typename Node2>
    std::pair<Node1, word_type::const_iterator>
    last_node_on_path(WordGraph<Node1> const& wg,
                      Node2                   source,
                      word_type const&        w);

    // TODO(1) tests
    // TODO(1) version where std::unordered_set is passed by reference, or make
    // this a class that stores its stack and unordered_set, not clear why we'd
    // single out the unordered_set to be passed by reference.
    // TODO(2) version which is an iterator i.e. returns an iterator or range
    // object that allows use to step through the nodes reachable from a given
    // node
    template <typename Node1, typename Node2>
    [[nodiscard]] std::unordered_set<Node1>
    nodes_reachable_from(WordGraph<Node1> const& wg, Node2 source);

    template <typename Node1, typename Node2>
    [[nodiscard]] std::unordered_set<Node1>
    ancestors_of(WordGraph<Node1> const& wg, Node2 target);

    template <typename Node1, typename Node2>
    [[nodiscard]] std::unordered_set<Node1>
    nodes_reachable_from_no_checks(WordGraph<Node1> const& wg, Node2 source);

    template <typename Node1, typename Node2>
    [[nodiscard]] std::unordered_set<Node1>
    ancestors_of_no_checks(WordGraph<Node1> const& wg, Node2 target);

    template <typename Node1, typename Node2>
    [[nodiscard]] size_t
    number_of_nodes_reachable_from(WordGraph<Node1> const& wg, Node2 source) {
      return nodes_reachable_from(wg, source).size();
    }

    template <typename Node1, typename Node2>
    [[nodiscard]] size_t
    number_of_nodes_reachable_from_no_checks(WordGraph<Node1> const& wg,
                                             Node2                   source) {
      return nodes_reachable_from_no_checks(wg, source).size();
    }

    template <typename Node>
    WordGraph<Node> random_acyclic(size_t       number_of_nodes,
                                   size_t       out_degree,
                                   std::mt19937 mt
                                   = std::mt19937(std::random_device()()));

    template <typename Node1, typename Node2>
    void spanning_tree_no_checks(WordGraph<Node1> const& wg,
                                 Node2                   root,
                                 Forest&                 f);

    template <typename Node1, typename Node2>
    void spanning_tree(WordGraph<Node1> const& wg, Node2 root, Forest& f);

    template <typename Node1, typename Node2>
    [[nodiscard]] Forest spanning_tree_no_checks(WordGraph<Node1> const& wg,
                                                 Node2                   root);

    template <typename Node1, typename Node2>
    [[nodiscard]] Forest spanning_tree(WordGraph<Node1> const& wg, Node2 root);

    // Not nodiscard because sometimes we just don't want the output
    template <typename Graph>
    bool standardize(Graph& wg, Forest& f, Order val);

    // Not nodiscard because sometimes we just don't want the output
    template <typename Graph>
    std::pair<bool, Forest> standardize(Graph& wg, Order val = Order::shortlex);

    template <typename Node>
    bool is_standardized(WordGraph<Node> const& wg,
                         Order                  val = Order::shortlex);

    template <typename Node>
    void throw_if_any_target_out_of_bounds(WordGraph<Node> const& wg);

    template <typename Node, typename Iterator>
    void throw_if_any_target_out_of_bounds(WordGraph<Node> const& wg,
                                           Iterator               first,
                                           Iterator               last);

    // not noexcept because it throws an exception!
    template <typename Node>
    void throw_if_label_out_of_bounds(WordGraph<Node> const&               wg,
                                      typename WordGraph<Node>::label_type a);

    template <typename Node>
    void throw_if_label_out_of_bounds(WordGraph<Node> const& wg,
                                      word_type const&       word);

    template <typename Node, typename Iterator>
    void throw_if_label_out_of_bounds(WordGraph<Node> const& wg,
                                      Iterator               first,
                                      Iterator               last);

    // not noexcept because it throws an exception!
    template <typename Node1, typename Node2>
    void throw_if_node_out_of_bounds(WordGraph<Node1> const& wg, Node2 n);

    // not noexcept because it throws an exception!
    template <typename Node, typename Iterator1, typename Iterator2>
    void throw_if_node_out_of_bounds(WordGraph<Node> const& wg,
                                     Iterator1              first,
                                     Iterator2              last);

    template <typename Node>
    [[nodiscard]] std::vector<Node> topological_sort(WordGraph<Node> const& wg);

    template <typename Node1, typename Node2>
    [[nodiscard]] std::vector<Node1>
    topological_sort(WordGraph<Node1> const& wg, Node2 source);
 
  }  // namespace word_graph

  // WordGraph - non-member functions

  template <typename Thing>
  static constexpr bool IsWordGraph [[deprecated]]
  = is_specialization_of_v<Thing, WordGraph>;

  template <typename Node>
  std::ostream& operator<<(std::ostream& os, WordGraph<Node> const& wg);


  // Passing the 2nd parameter "targets" by value disambiguates it from the
  // other make<WordGraph>.
  template <typename Return>
  [[nodiscard]] std::enable_if_t<is_specialization_of_v<Return, WordGraph>,
                                 Return>
  make(size_t                                                         num_nodes,
       std::initializer_list<std::vector<typename Return::node_type>> targets);

  // clang-format off
  // NOLINTNEXTLINE(whitespace/line_length)
  // clang-format on
  template <typename Return>
  [[nodiscard]] std::enable_if_t<is_specialization_of_v<Return, WordGraph>,
                                 Return>
  make(size_t                                                      num_nodes,
       std::vector<std::vector<typename Return::node_type>> const& targets);
 
  namespace detail {
    template <typename Subclass>
    class JoinerMeeterCommon {
     private:
      template <typename Node1, typename Node2>
      void throw_if_bad_args(WordGraph<Node1> const& x,
                             Node2                   xroot,
                             WordGraph<Node1> const& y,
                             Node2                   yroot);
 
     public:
      template <typename Node>
      void call_no_checks(WordGraph<Node>&       xy,
                          WordGraph<Node> const& x,
                          Node                   xroot,
                          WordGraph<Node> const& y,
                          Node                   yroot);
 
      template <typename Node>
      void call_no_checks(WordGraph<Node>&       xy,
                          WordGraph<Node> const& x,
                          WordGraph<Node> const& y) {
        return call_no_checks(
            xy, x, static_cast<Node>(0), y, static_cast<Node>(0));
      }
 
      template <typename Node, typename... Args>
      [[nodiscard]] auto call_no_checks(WordGraph<Node> const& x,
                                        Args&&... args)
          -> std::enable_if_t<sizeof...(Args) % 2 == 1, WordGraph<Node>> {
        // The versions of this function changing the 1st argument in-place
        // always have an odd number of arguments, so we check that it's even
        // here (the argument x and an odd number of further arguments).
        WordGraph<Node> xy;
        static_cast<Subclass&>(*this).call_no_checks(
            xy, x, std::forward<Args>(args)...);
        return xy;
      }
 
      // There's no operator() with the number of nodes reachable from the
      // roots as arguments (7 args in total) because we'd have to check that
      // they were valid, and the only way to do this is to recompute them.
 
      template <typename Node>
      void operator()(WordGraph<Node>&       xy,
                      WordGraph<Node> const& x,
                      Node                   xroot,
                      WordGraph<Node> const& y,
                      Node                   yroot) {
        throw_if_bad_args(x, xroot, y, yroot);
        call_no_checks(xy, x, xroot, y, yroot);
      }
 
      template <typename Node>
      void operator()(WordGraph<Node>&       xy,
                      WordGraph<Node> const& x,
                      WordGraph<Node> const& y) {
        return operator()(xy, x, static_cast<Node>(0), y, static_cast<Node>(0));
      }
 
      template <typename Node, typename... Args>
      [[nodiscard]] auto operator()(WordGraph<Node> const& x, Args&&... args)
          -> std::enable_if_t<sizeof...(Args) % 2 == 1, WordGraph<Node>> {
        // The versions of this function changing the 1st argument in-place
        // always have an odd number of arguments, so we check that it's even
        // here (the argument x and an odd number of further arguments).
        WordGraph<Node> xy;
                        operator()(xy, x, std::forward<Args>(args)...);
        return xy;
      }
 
      template <typename Node1, typename Node2>
      bool is_subrelation_no_checks(WordGraph<Node1> const& x,
                                    Node2                   xroot,
                                    WordGraph<Node1> const& y,
                                    Node2                   yroot);
 
      template <typename Node>
      bool is_subrelation_no_checks(WordGraph<Node> const& x,
                                    WordGraph<Node> const& y) {
        return is_subrelation_no_checks(
            x, static_cast<Node>(0), y, static_cast<Node>(0));
      }
 
      // There's no subrelation with the number of nodes reachable from the
      // roots as arguments (6 args in total) because we'd have to check that
      // they were valid, and the only way to do this is to recompute them.
 
      template <typename Node1, typename Node2>
      bool is_subrelation(WordGraph<Node1> const& x,
                          Node2                   xroot,
                          WordGraph<Node1> const& y,
                          Node2                   yroot) {
        throw_if_bad_args(x, xroot, y, yroot);
        return is_subrelation_no_checks(x, xroot, y, yroot);
      }
 
      template <typename Node>
      bool is_subrelation(WordGraph<Node> const& x, WordGraph<Node> const& y) {
        return is_subrelation(x, static_cast<Node>(0), y, static_cast<Node>(0));
      }
    };  // JoinerMeeterCommon
  }     // namespace detail

  // This class is intentionally not a template so that we don't have to
  // specify the types of the nodes when constructing one of these objects.
  // Instead every member function has a template parameter Node, which is
  // deduced from the argument.
  class Joiner : public detail::JoinerMeeterCommon<Joiner> {
   private:
    detail::Duf<>                             _uf;
    std::stack<std::pair<uint64_t, uint64_t>> _stck;
    std::vector<uint64_t>                     _lookup;
 
    template <typename Node>
    [[nodiscard]] Node find(WordGraph<Node> const& x,
                            size_t xnum_nodes_reachable_from_root,
                            WordGraph<Node> const&               y,
                            uint64_t                             n,
                            typename WordGraph<Node>::label_type a) const;
 
    template <typename Node>
    void run(WordGraph<Node> const& x,
             size_t                 xnum_nodes_reachable_from_root,
             Node                   xroot,
             WordGraph<Node> const& y,
             size_t                 ynum_nodes_reachable_from_root,
             Node                   yroot);
 
   public:
    Joiner();

    Joiner(Joiner const&);

    Joiner(Joiner&&);

    Joiner& operator=(Joiner const&);

    Joiner& operator=(Joiner&&);
 
    ~Joiner();

    template <typename Node>
    void call_no_checks(WordGraph<Node>&       xy,
                        WordGraph<Node> const& x,
                        size_t                 xnum_nodes_reachable_from_root,
                        Node                   xroot,
                        WordGraph<Node> const& y,
                        size_t                 ynum_nodes_reachable_from_root,
                        Node                   yroot);

    // Is x a subrelation of y?
    template <typename Node1, typename Node2>
    [[nodiscard]] bool
    is_subrelation_no_checks(WordGraph<Node1> const& x,
                             size_t xnum_nodes_reachable_from_root,
                             Node2  xroot,
                             WordGraph<Node1> const& y,
                             size_t ynum_nodes_reachable_from_root,
                             Node2  yroot);
#ifdef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
    template <typename Node>
    void call_no_checks(WordGraph<Node>&       xy,
                        WordGraph<Node> const& x,
                        Node                   xroot,
                        WordGraph<Node> const& y,
                        Node                   yroot);

    template <typename Node>
    void call_no_checks(WordGraph<Node>&       xy,
                        WordGraph<Node> const& x,
                        WordGraph<Node> const& y);

    template <typename Node, typename... Args>
    [[nodiscard]] auto call_no_checks(WordGraph<Node> const& x, Args&&... args);

    template <typename Node>
    void operator()(WordGraph<Node>&       xy,
                    WordGraph<Node> const& x,
                    Node                   xroot,
                    WordGraph<Node> const& y,
                    Node                   yroot);

    template <typename Node>
    void operator()(WordGraph<Node>&       xy,
                    WordGraph<Node> const& x,
                    WordGraph<Node> const& y);

    template <typename Node, typename... Args>
    [[nodiscard]] auto operator()(WordGraph<Node> const& x, Args&&... args);

    // Is x a subrelation of y?
    template <typename Node1, typename Node2>
    bool is_subrelation_no_checks(WordGraph<Node1> const& x,
                                  Node2                   xroot,
                                  WordGraph<Node1> const& y,
                                  Node2                   yroot);

    template <typename Node>
    bool is_subrelation_no_checks(WordGraph<Node> const& x,
                                  WordGraph<Node> const& y);
 
    // There's no subrelation with the number of nodes reachable from the
    // roots as arguments (6 args in total) because we'd have to check that
    // they were valid, and the only way to do this is to recompute them.

    template <typename Node1, typename Node2>
    bool is_subrelation(WordGraph<Node1> const& x,
                        Node2                   xroot,
                        WordGraph<Node1> const& y,
                        Node2                   yroot);

    template <typename Node>
    bool is_subrelation(WordGraph<Node> const& x, WordGraph<Node> const& y);
 
#else
    using detail::JoinerMeeterCommon<Joiner>::call_no_checks;
    using detail::JoinerMeeterCommon<Joiner>::operator();
    using detail::JoinerMeeterCommon<Joiner>::is_subrelation_no_checks;
    using detail::JoinerMeeterCommon<Joiner>::is_subrelation;
#endif
  };  // Joiner

  // Class for forming the meet of two word graphs
  class Meeter : public detail::JoinerMeeterCommon<Meeter> {
   private:
    using node_type = std::pair<uint64_t, uint64_t>;
 
    std::unordered_map<node_type, uint64_t, Hash<node_type>> _lookup;
    std::vector<node_type>                                   _todo;
    std::vector<node_type>                                   _todo_new;
 
   public:
    Meeter();

    Meeter(Meeter const&);

    Meeter(Meeter&&);

    Meeter& operator=(Meeter const&);

    Meeter& operator=(Meeter&&);
 
    ~Meeter();

    template <typename Node>
    void call_no_checks(WordGraph<Node>&       xy,
                        WordGraph<Node> const& x,
                        size_t                 xnum_nodes_reachable_from_root,
                        Node                   xroot,
                        WordGraph<Node> const& y,
                        size_t                 ynum_nodes_reachable_from_root,
                        Node                   yroot);

    // is x a subrelation of y
    template <typename Node1, typename Node2>
    [[nodiscard]] bool
    is_subrelation_no_checks(WordGraph<Node1> const& x,
                             size_t xnum_nodes_reachable_from_root,
                             Node2  xroot,
                             WordGraph<Node1> const& y,
                             size_t ynum_nodes_reachable_from_root,
                             Node2  yroot);
 
#ifdef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
    template <typename Node>
    void call_no_checks(WordGraph<Node>&       xy,
                        WordGraph<Node> const& x,
                        Node                   xroot,
                        WordGraph<Node> const& y,
                        Node                   yroot);

    template <typename Node>
    void call_no_checks(WordGraph<Node>&       xy,
                        WordGraph<Node> const& x,
                        WordGraph<Node> const& y);

    template <typename Node, typename... Args>
    [[nodiscard]] auto call_no_checks(WordGraph<Node> const& x, Args&&... args);

    template <typename Node>
    void operator()(WordGraph<Node>&       xy,
                    WordGraph<Node> const& x,
                    Node                   xroot,
                    WordGraph<Node> const& y,
                    Node                   yroot);

    template <typename Node>
    void operator()(WordGraph<Node>&       xy,
                    WordGraph<Node> const& x,
                    WordGraph<Node> const& y);

    template <typename Node, typename... Args>
    [[nodiscard]] auto operator()(WordGraph<Node> const& x, Args&&... args);

    template <typename Node1, typename Node2>
    bool is_subrelation_no_checks(WordGraph<Node1> const& x,
                                  Node2                   xroot,
                                  WordGraph<Node1> const& y,
                                  Node2                   yroot);

    template <typename Node>
    bool is_subrelation_no_checks(WordGraph<Node> const& x,
                                  WordGraph<Node> const& y);

    template <typename Node1, typename Node2>
    bool is_subrelation(WordGraph<Node1> const& x,
                        Node2                   xroot,
                        WordGraph<Node1> const& y,
                        Node2                   yroot);

    template <typename Node>
    bool is_subrelation(WordGraph<Node> const& x, WordGraph<Node> const& y);
#else
    using detail::JoinerMeeterCommon<Meeter>::call_no_checks;
    using detail::JoinerMeeterCommon<Meeter>::operator();
    using detail::JoinerMeeterCommon<Meeter>::is_subrelation_no_checks;
    using detail::JoinerMeeterCommon<Meeter>::is_subrelation;
#endif
  };  // class Meeter

  template <typename Node>
  [[nodiscard]] std::string to_human_readable_repr(WordGraph<Node> const& wg);

  [[nodiscard]] static inline std::string
  to_human_readable_repr(Meeter const& meet) {
    (void) meet;
    return "<Meeter of word graphs>";
  }

  [[nodiscard]] static inline std::string
  to_human_readable_repr(Joiner const& join) {
    (void) join;
    return "<Joiner of word graphs>";
  }

  template <typename Node>
  [[nodiscard]] std::string to_input_string(WordGraph<Node> const& wg,
                                            std::string const&     prefix = "",
                                            std::string const& braces = "{}",
                                            std::string const& suffix = "");
}  // namespace libsemigroups
 
#include "word-graph.tpp"
 
#endif  // LIBSEMIGROUPS_WORD_GRAPH_HPP_