word-graph-helpers.hpp

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2025 Nadim Searight
//
// 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 helper functions for word graphs and word graph views
 
#ifndef LIBSEMIGROUPS_WORD_GRAPH_HELPERS_HPP_
#define LIBSEMIGROUPS_WORD_GRAPH_HELPERS_HPP_
 
#include <algorithm>         // for max, fill
#include <initializer_list>  // for initializer_list
#include <iosfwd>            // for ostream
#include <iterator>          // for empty
#include <numeric>           // for iota
#include <queue>             // for queue
#include <random>            // for mt19937, random_device
#include <stack>             // for stack
#include <stddef.h>          // for size_t
#include <stdint.h>          // for uint64_t, uint8_t
#include <string>            // for basic_string, allocator
#include <tuple>             // for tie
#include <type_traits>       // for enable_if_t, decay_t
#include <unordered_map>     // for unordered_map
#include <unordered_set>     // for unordered_set
#include <utility>           // for pair, move, make_pair
#include <vector>            // for vector, swap
 
#include "libsemigroups/adapters.hpp"         // for Hash
#include "libsemigroups/config.hpp"           // for LIBSEMIGROUPS_EIGEN_...
#include "libsemigroups/constants.hpp"        // for UNDEFINED
#include "libsemigroups/debug.hpp"            // for LIBSEMIGROUPS_ASSERT
#include "libsemigroups/dot.hpp"              // for Dot
#include "libsemigroups/exception.hpp"        // for LIBSEMIGROUPS_EXCEPTION
#include "libsemigroups/forest.hpp"           // for Forest
#include "libsemigroups/order.hpp"            // for Order
#include "libsemigroups/types.hpp"            // for word_type, letter_type
#include "libsemigroups/word-graph-view.hpp"  // for WordGraphView
#include "libsemigroups/word-graph.hpp"       // for WordGraph
 
#include "libsemigroups/detail/fmt.hpp"     // for fmt::format
#include "libsemigroups/detail/stl.hpp"     // for HasLessEqual
#include "libsemigroups/detail/string.hpp"  // for group_digits
#include "libsemigroups/detail/uf.hpp"      // for Duf
 
#ifdef LIBSEMIGROUPS_EIGEN_ENABLED
#include "detail/eigen.hpp"
#else
#include "matrix.hpp"
#endif
 
namespace libsemigroups {
 
  namespace v4 {
 
    // TODO(v4) Turn this into a doxygen comment once it is moved out of the v4
    // namespace
    // \ingroup word_graph_group
    //
    // \brief Namespace containing helper functions for the \ref WordGraph
    // class.
    //
    // Defined in `word-graph-helpers.hpp`.
    //
    // \brief This namespace contains helper functions for the \ref WordGraph
    // class.
    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(WordGraphView<Node> const& wg);

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

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

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

      template <typename Node>
      [[nodiscard]] bool equal_to_no_checks(WordGraph<Node> const& x,
                                            WordGraph<Node> const& y,
                                            Node                   first,
                                            Node                   last) {
        WordGraphView<Node> x_view = WordGraphView<Node>(x, first, last);
        WordGraphView<Node> y_view = WordGraphView<Node>(y, first, last);
        return x_view == y_view;
      }

      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(WordGraphView<Node1> const& wg,
                                      Node2                       source,
                                      Iterator                    first,
                                      Iterator                    last);

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

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

      // 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(
            WordGraphView<Node1>(wg), from, path.cbegin(), path.cend());
      }

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

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

      template <typename Node1, typename Node2>
      [[nodiscard]] Node1
      follow_path_no_checks(WordGraphView<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());
      }

      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(
            WordGraphView<Node1>(wg), from, path.cbegin(), path.cend());
      }

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

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

      // Not noexcept because detail::is_acyclic isn't
      template <typename Node1, typename Node2>
      [[nodiscard]] bool is_acyclic(WordGraphView<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) {
        return is_acyclic(WordGraphView<Node1>(wg), source);
      }

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

      // 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) {
        return is_acyclic(WordGraphView<Node1>(wg), source, 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(WordGraphView<Node> const& wg,
                                                 Iterator1 first_node,
                                                 Iterator2 last_node,
                                                 Iterator3 first_rule,
                                                 Iterator3 last_rule);

      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) {
        return is_compatible_no_checks(WordGraphView<Node>(wg),
                                       first_node,
                                       last_node,
                                       first_rule,
                                       last_rule);
      }

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

      template <typename Node,
                typename Iterator1,
                typename Iterator2,
                typename Iterator3,
                typename = 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) {
        WordGraphView<Node> wgv(wg);
        return is_compatible(wgv, first_node, last_node, first_rule, last_rule);
      }

      template <typename Node, typename Iterator1, typename Iterator2>
      bool is_compatible_no_checks(WordGraphView<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_no_checks(WordGraph<Node> const& wg,
                                   Iterator1              first_node,
                                   Iterator2              last_node,
                                   word_type const&       lhs,
                                   word_type const&       rhs) {
        return is_compatible_no_checks(
            WordGraphView<Node>(wg), first_node, last_node, lhs, rhs);
      }

      template <typename Node, typename Iterator1, typename Iterator2>
      bool is_compatible(WordGraphView<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) {
        return is_compatible(
            WordGraphView<Node>(wg), first_node, last_node, lhs, rhs);
      }
 
      /*
      TODO(0): Remove or delete
      template <typename WordGraphType,
                typename Iterator1,
                typename Iterator2,
                typename Iterator3,
                typename = std::enable_if_t<
                    std::is_same_v<WordGraphType,
                                   WordGraph<typename
                                   WordGraphType::node_type>>
                    || std::is_same_v<
                        WordGraphType,
                        WordGraphView<typename WordGraphType::node_type>>>>
      bool is_compatible(WordGraphType const& wg,
                         Iterator1            first_node,
                         Iterator2            last_node,
                         Iterator3            first_rule,
                         Iterator3            last_rule) {
        if constexpr (std::is_same_v<
                          WordGraphType,
                          WordGraph<typename WordGraphType::node_type>>) {
          return is_compatible(
              static_cast<WordGraph<typename WordGraphType::node_type>
              const&>(
                  wg),
              first_node,
              last_node,
              first_rule,
              last_rule);
        } else {
          return is_compatible(
              static_cast<
                  WordGraphView<typename WordGraphType::node_type>
                  const&>(wg),
              first_node,
              last_node,
              first_rule,
              last_rule);
        }
      }
      */

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

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

      template <typename Node, typename Iterator1, typename Iterator2>
      [[nodiscard]] bool is_complete(WordGraphView<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) {
        return is_complete(WordGraphView<Node>(wg), first_node, last_node);
      }

      template <typename Node>
      [[nodiscard]] bool
      is_complete_no_checks(WordGraphView<Node> const& wg) noexcept {
        return wg.number_of_edges_no_checks()
               == wg.number_of_nodes_no_checks() * wg.out_degree_no_checks();
      }
 
      template <typename Node>
      [[nodiscard]] bool is_complete(WordGraphView<Node> const& wg) {
        wg.throw_if_invalid_view();
        return is_complete_no_checks(wg);
      }

      template <typename Node>
      [[nodiscard]] bool is_complete(WordGraph<Node> const& wg) noexcept {
        return is_complete(WordGraphView<Node>(wg));
      }

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

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

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

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

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

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

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

      // 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) {
        return is_strictly_cyclic(WordGraphView<Node>(wg));
      }

      template <typename Node1, typename Node2, typename Iterator>
      [[nodiscard]] std::pair<Node1, Iterator>
      last_node_on_path_no_checks(WordGraphView<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_no_checks(WordGraph<Node1> const& wg,
                                  Node2                   source,
                                  Iterator                first,
                                  Iterator                last) noexcept {
        return last_node_on_path_no_checks(
            WordGraphView<Node1>(wg), source, first, last);
      }

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

      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) {
        return last_node_on_path(WordGraphView<Node1>(wg), source, first, last);
      }

      template <typename Node1, typename Node2>
      std::pair<Node1, word_type::const_iterator>
      last_node_on_path_no_checks(WordGraphView<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_no_checks(WordGraph<Node1> const& wg,
                                  Node2                   source,
                                  word_type const&        w) {
        return last_node_on_path_no_checks(WordGraphView<Node1>(wg), source, w);
      }

      template <typename Node1, typename Node2>
      std::pair<Node1, word_type::const_iterator>
      last_node_on_path(WordGraphView<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) {
        return last_node_on_path(WordGraphView<Node1>(wg), source, 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(WordGraphView<Node1> const& wg, Node2 source);

      // 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) {
        return nodes_reachable_from(WordGraphView<Node1>(wg), source);
      }

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

      template <typename Node1, typename Node2>
      [[nodiscard]] std::unordered_set<Node1>
      ancestors_of(WordGraph<Node1> const& wg, Node2 target) {
        return ancestors_of(WordGraphView<Node1>(wg), 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(WordGraphView<Node1> const& wg, Node2 target);

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

      template <typename Node1, typename Node2>
      [[nodiscard]] size_t
      number_of_nodes_reachable_from(WordGraphView<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(WordGraph<Node1> const& wg, Node2 source) {
        return number_of_nodes_reachable_from(WordGraphView<Node1>(wg), source);
      }

      template <typename Node1, typename Node2>
      [[nodiscard]] size_t
      number_of_nodes_reachable_from_no_checks(WordGraphView<Node1> const& wg,
                                               Node2 source) {
        return nodes_reachable_from_no_checks(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 number_of_nodes_reachable_from_no_checks(
            WordGraphView<Node1>(wg), source);
      }

      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(WordGraphView<Node1> const& wg,
                                   Node2                       root,
                                   Forest&                     f);

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

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

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

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

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

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

      template <typename Node1, typename Node2>
      [[nodiscard]] Forest spanning_tree(WordGraph<Node1> const& wg,
                                         Node2                   root) {
        return spanning_tree(WordGraphView<Node1>(wg), 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(WordGraphView<Node> const& wg,
                           Order                      val = Order::shortlex);

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

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

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

      template <typename Node1, typename Node2>
      [[nodiscard]] std::vector<Node1>
      topological_sort(WordGraphView<Node1> const& wg, Node2 source);

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

    // WordGraph - non-member functions
    // TODO(1) Add equivalents for WordGraphView

    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:
      // TODO(v4) Remove the libsemigroups prefix
      libsemigroups::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 v4
}  // namespace libsemigroups
 
#include "libsemigroups/word-graph-helpers.tpp"
#endif  // LIBSEMIGROUPS_WORD_GRAPH_HELPERS_HPP_