paths.hpp

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2023-2025 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 iterating through paths in an
// WordGraph.
 
// TODO(2) check code coverage
 
#ifndef LIBSEMIGROUPS_PATHS_HPP_
#define LIBSEMIGROUPS_PATHS_HPP_
 
#include <algorithm>    // for any_of, for_each, max_element
#include <cstddef>      // for size_t, ptrdiff_t
#include <cstdint>      // for uint64_t
#include <iterator>     // for distance, forward_iterator_tag
#include <numeric>      // for accumulate
#include <string>       // for std::string
#include <type_traits>  // for true_type
#include <variant>      // for visit, variant
#include <vector>       // for vector, allocator
 
#include "config.hpp"      // for LIBSEMIGROUPS_EIGEN_ENA...
#include "constants.hpp"   // for Max, UNDEFINED, Positive...
#include "debug.hpp"       // for LIBSEMIGROUPS_ASSERT
#include "exception.hpp"   // for LIBSEMIGROUPS_EXCEPTION
#include "order.hpp"       // for order
#include "ranges.hpp"      // for is_input_range
#include "types.hpp"       // for word_type
#include "word-graph.hpp"  // for WordGraph
#include "word-range.hpp"  // for number_of_words
 
#include "detail/containers.hpp"      // for DynamicArray2
#include "detail/path-iterators.hpp"  // for default_postfix_increment
 
namespace libsemigroups {
  namespace paths {
    enum class algorithm {
      dfs = 0,
      matrix,
      acyclic,
      trivial,
      automatic
    };
  }  // namespace paths

  // not noexcept because constructors of const_pilo_iterator aren't
  template <typename Node1, typename Node2>
  [[nodiscard]] auto cbegin_pilo(WordGraph<Node1> const& wg,
                                 Node2                   source,
                                 size_t                  min = 0,
                                 size_t max = POSITIVE_INFINITY) {
    word_graph::throw_if_node_out_of_bounds(wg, static_cast<Node1>(source));
    return detail::const_pilo_iterator<Node1>(&wg, source, min, max);
  }

  // not noexcept because constructors of const_pilo_iterator aren't
  template <typename Node>
  [[nodiscard]] auto cend_pilo(WordGraph<Node> const& wg) {
    return detail::const_pilo_iterator<Node>(&wg, 0, 0, 0);
  }

  // TODO(2) example and what is the complexity?
  // not noexcept because detail::const_pislo_iterator constructors aren't
  template <typename Node1, typename Node2>
  [[nodiscard]] auto cbegin_pislo(WordGraph<Node1> const& wg,
                                  Node2                   source,
                                  size_t                  min = 0,
                                  size_t max = POSITIVE_INFINITY) {
    word_graph::throw_if_node_out_of_bounds(wg, static_cast<Node1>(source));
    return detail::const_pislo_iterator<Node1>(&wg, source, min, max);
  }

  // not noexcept because detail::const_pislo_iterator constructors aren't
  template <typename Node>
  [[nodiscard]] auto cend_pislo(WordGraph<Node> const& wg) {
    return detail::const_pislo_iterator<Node>(&wg, UNDEFINED, 0, 0);
  }

  // not noexcept because detail::const_pstilo_iterator constructors aren't
  template <typename Node1, typename Node2>
  [[nodiscard]] auto cbegin_pstilo(WordGraph<Node1> const& wg,
                                   Node2                   source,
                                   Node2                   target,
                                   size_t                  min = 0,
                                   size_t max = POSITIVE_INFINITY) {
    // source & target are validated in is_reachable.
    if (!word_graph::is_reachable(wg, source, target)) {
      return cend_pstilo(wg);
    }
    return detail::const_pstilo_iterator<Node1>(&wg, source, target, min, max);
  }

  // not noexcept because detail::const_pstilo_iterator constructors aren't
  template <typename Node>
  [[nodiscard]] auto cend_pstilo(WordGraph<Node> const& wg) {
    return detail::const_pstilo_iterator<Node>(&wg, 0, 0, 0, 0);
  }

  // not noexcept because cbegin_pislo isn't
  template <typename Node1, typename Node2>
  [[nodiscard]] auto cbegin_pstislo(WordGraph<Node1> const& wg,
                                    Node2                   source,
                                    Node2                   target,
                                    size_t                  min = 0,
                                    size_t max = POSITIVE_INFINITY) {
    // source & target are validated in is_reachable.
    if (!word_graph::is_reachable(wg, source, target)) {
      return cend_pstislo(wg);
    }
    return detail::const_pstislo_iterator<Node1>(&wg, source, target, min, max);
  }

  // not noexcept because cend_pislo isn't
  template <typename Node>
  [[nodiscard]] auto cend_pstislo(WordGraph<Node> const& wg) {
    return detail::const_pstislo_iterator<Node>(
        &wg, UNDEFINED, UNDEFINED, 0, 0);
  }

  template <typename Node1, typename Node2>
  [[nodiscard]] paths::algorithm
  number_of_paths_algorithm(WordGraph<Node1> const& wg, Node2 source) noexcept {
    (void) wg;
    (void) source;
    return paths::algorithm::acyclic;
  }

  template <typename Node1, typename Node2>
  [[nodiscard]] uint64_t number_of_paths(WordGraph<Node1> const& wg,
                                         Node2                   source);

  // Not noexcept because word_graph::topological_sort is not.
  template <typename Node1, typename Node2>
  [[nodiscard]] paths::algorithm
  number_of_paths_algorithm(WordGraph<Node1> const& wg,
                            Node2                   source,
                            size_t                  min,
                            size_t                  max);

  // not noexcept for example detail::number_of_paths_trivial can throw
  template <typename Node1, typename Node2>
  [[nodiscard]] uint64_t number_of_paths(WordGraph<Node1> const& wg,
                                         Node2                   source,
                                         size_t                  min,
                                         size_t                  max,
                                         paths::algorithm        lgrthm
                                         = paths::algorithm::automatic);

  // Not noexcept because word_graph::topological_sort isn't
  template <typename Node1, typename Node2>
  [[nodiscard]] paths::algorithm
  number_of_paths_algorithm(WordGraph<Node1> const& wg,
                            Node2                   source,
                            Node2                   target,
                            size_t                  min,
                            size_t                  max);

  // not noexcept because cbegin_pstilo isn't
  template <typename Node1, typename Node2>
  [[nodiscard]] uint64_t number_of_paths(WordGraph<Node1> const& wg,
                                         Node2                   source,
                                         Node2                   target,
                                         size_t                  min,
                                         size_t                  max,
                                         paths::algorithm        lgrthm
                                         = paths::algorithm::automatic);

  template <typename Node>
  class Paths {
   public:
    using node_type = Node;

    using size_type = typename WordGraph<Node>::size_type;

    using output_type = word_type const&;
 
   private:
    using const_iterator = std::variant<detail::const_pstislo_iterator<Node>,
                                        detail::const_pstilo_iterator<Node>,
                                        detail::const_pislo_iterator<Node>,
                                        detail::const_pilo_iterator<Node>>;
 
    WordGraph<node_type> const* _word_graph;
    Order                       _order;
    size_type                   _max;
    size_type                   _min;
    mutable size_type           _position;
    node_type                   _source;
    node_type                   _target;
    mutable const_iterator      _current;
    mutable const_iterator      _end;
    mutable bool                _current_valid;
 
    bool set_iterator_no_checks() const;
 
    // The following init function is private to avoid the case of constructing
    // a Paths object without setting _word_graph. The subsequent default
    // constructor is protected and still needed (instead of deleting it) to
    // avoid problems with having uninitialised std::variants with copy
    // constructors.
 
    Paths& init();
 
   protected:
    Paths() = default;
 
   public:
    // Constructors + initialization

    Paths(Paths const&);

    Paths(Paths&&);

    Paths& operator=(Paths const&);

    Paths& operator=(Paths&&);
 
    ~Paths();

    explicit Paths(WordGraph<Node> const& wg) : Paths() {
      init(wg);
    }

    Paths& init(WordGraph<Node> const& wg) {
      init();
      _word_graph = &wg;
      return *this;
    }

    // Validation

    void throw_if_source_undefined() const;

    // Functions + members required by rx::ranges

    output_type get() const {
      set_iterator_no_checks();
      return std::visit(
          [](auto& it) -> auto const& { return *it; }, _current);
    }

    void next() {
      if (!at_end()) {
        ++_position;
        std::visit([](auto& it) { ++it; }, _current);
      }
    }

    [[nodiscard]] bool at_end() const {
      if (!set_iterator_no_checks()) {
        return true;
      }
      return _current == _end;
    }

    [[nodiscard]] uint64_t size_hint() const;

    [[nodiscard]] uint64_t count() const {
      return size_hint();
    }
 
    static constexpr bool is_finite     = true;  // this isn't always true!
    static constexpr bool is_idempotent = true;

    // Settings

    Paths& source_no_checks(node_type n) noexcept {
      return source_no_checks(this, n);
    }

    Paths& source(node_type n) {
      word_graph::throw_if_node_out_of_bounds(word_graph(), n);
      return source_no_checks(n);
    }

    [[nodiscard]] node_type source() const noexcept {
      return _source;
    }

    Paths& target_no_checks(node_type n) noexcept {
      return target_no_checks(this, n);
    }

    Paths& target(node_type n) {
      if (n != UNDEFINED) {
        word_graph::throw_if_node_out_of_bounds(word_graph(), n);
      }
      return target_no_checks(n);
    }

    [[nodiscard]] node_type target() const noexcept {
      return _target;
    }

    [[nodiscard]] node_type current_target() const;

    Paths& min(size_type val) noexcept {
      return min(this, val);
    }

    [[nodiscard]] size_type min() const noexcept {
      return _min;
    }

    Paths& max(size_type val) noexcept {
      return max(this, val);
    }

    [[nodiscard]] size_type max() const noexcept {
      return _max;
    }

    Paths& order(Order val) {
      return order(this, val);
    }

    [[nodiscard]] Order order() const noexcept {
      return _order;
    }

    [[nodiscard]] WordGraph<Node> const& word_graph() const noexcept {
      return *_word_graph;
    }
 
   protected:
    template <typename Subclass>
    Subclass& source_no_checks(Subclass* obj, node_type src) {
      _current_valid &= (src == _source);
      _source = src;
      return *obj;
    }
 
    template <typename Subclass>
    Subclass& target_no_checks(Subclass* obj, node_type trgt) noexcept {
      _current_valid &= (trgt == _target);
      _target = trgt;
      return *obj;
    }
 
    template <typename Subclass>
    Subclass& min(Subclass* obj, size_type min) noexcept {
      _current_valid &= (min == _min);
      _min = min;
      return *obj;
    }
 
    template <typename Subclass>
    Subclass& max(Subclass* obj, size_type max) noexcept {
      _current_valid &= (max == _max);
      _max = max;
      return *obj;
    }
 
    template <typename Subclass>
    Subclass& order(Subclass* obj, Order val);
  };  // class Paths

  template <typename Node>
  Paths(WordGraph<Node> const&) -> Paths<Node>;

  template <typename Node>
  Paths(WordGraph<Node>&&) -> Paths<Node>;

  template <typename Node>
  std::string to_human_readable_repr(Paths<Node> const& p);
 
}  // namespace libsemigroups
 
#include "paths.tpp"
 
#endif  // LIBSEMIGROUPS_PATHS_HPP_