paths-count.hpp

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2025-2026 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 counting paths in
// WordGraphs.
 
#ifndef LIBSEMIGROUPS_PATHS_COUNT_HPP_
#define LIBSEMIGROUPS_PATHS_COUNT_HPP_
 
#include <algorithm>  // for min
#include <cstddef>    // for size_t
#include <cstdint>    // for uint64_t
#include <iterator>   // for distance
#include <numeric>    // for accum...
#include <vector>     // for vector
 
#include "detail/containers.hpp"  // for Dynam...
#include "detail/eigen.hpp"       // for eigenstuff
 
#include "config.hpp"              // for LIBSEMIGROUPS_EIGEN_ENABLED
#include "constants.hpp"           // for POSITIVE_INFINITY
#include "debug.hpp"               // for LIBSEMIGROUPS_ASSERT
#include "exception.hpp"           // for LIBSEMIGROUPS_EXCEPTION
#include "word-graph-helpers.hpp"  // for is_acyclic etc
#include "word-graph.hpp"          // for WordGraph
#include "word-range.hpp"          // for number_of_words
 
// TODO(v4) Remove the below line so this appears in the documentation
#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
namespace libsemigroups::v4 {
  namespace paths {
    enum class algorithm {
      dfs = 0,
      matrix,
      acyclic,
      trivial,
      automatic
    };

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

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

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

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

    // Not noexcept because v4::word_graph::topological_sort isn't
    template <typename Node1, typename Node2>
    [[nodiscard]] algorithm count_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 count(WordGraph<Node1> const& wg,
                                 Node2                   source,
                                 Node2                   target,
                                 size_t                  min,
                                 size_t                  max,
                                 algorithm lgrthm = algorithm::automatic);
  }  // namespace paths
}  // namespace libsemigroups::v4
#endif
 
#include "paths-count.tpp"
 
#endif  // LIBSEMIGROUPS_PATHS_COUNT_HPP_