libsemigroups
v3.6.2
C++ library for semigroups and monoids
Toggle main menu visibility
Loading...
Searching...
No Matches
paths-count.hpp
1
//
2
// libsemigroups - C++ library for semigroups and monoids
3
// Copyright (C) 2025-2026 James D. Mitchell
4
//
5
// This program is free software: you can redistribute it and/or modify
6
// it under the terms of the GNU General Public License as published by
7
// the Free Software Foundation, either version 3 of the License, or
8
// (at your option) any later version.
9
//
10
// This program is distributed in the hope that it will be useful,
11
// but WITHOUT ANY WARRANTY; without even the implied warranty of
12
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13
// GNU General Public License for more details.
14
//
15
// You should have received a copy of the GNU General Public License
16
// along with this program. If not, see <http://www.gnu.org/licenses/>.
17
//
18
19
// This file contains declarations related to counting paths in
20
// WordGraphs.
21
22
#ifndef LIBSEMIGROUPS_PATHS_COUNT_HPP_
23
#define LIBSEMIGROUPS_PATHS_COUNT_HPP_
24
25
#include <algorithm>
// for min
26
#include <cstddef>
// for size_t
27
#include <cstdint>
// for uint64_t
28
#include <iterator>
// for distance
29
#include <numeric>
// for accum...
30
#include <vector>
// for vector
31
32
#include "detail/containers.hpp"
// for Dynam...
33
#include "detail/eigen.hpp"
// for eigenstuff
34
35
#include "config.hpp"
// for LIBSEMIGROUPS_EIGEN_ENABLED
36
#include "constants.hpp"
// for POSITIVE_INFINITY
37
#include "debug.hpp"
// for LIBSEMIGROUPS_ASSERT
38
#include "exception.hpp"
// for LIBSEMIGROUPS_EXCEPTION
39
#include "word-graph-helpers.hpp"
// for is_acyclic etc
40
#include "word-graph.hpp"
// for WordGraph
41
#include "word-range.hpp"
// for number_of_words
42
43
// TODO(v4) Remove the below line so this appears in the documentation
44
#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
45
namespace
libsemigroups::v4 {
51
namespace
paths {
54
enum class
algorithm
{
56
dfs
= 0,
58
matrix,
60
acyclic,
62
trivial,
65
automatic
66
};
67
81
template
<
typename
Node1,
typename
Node2>
82
[[nodiscard]]
algorithm
count_algorithm(WordGraph<Node1>
const
& wg,
83
Node2 source)
noexcept
{
84
(void) wg;
85
(void) source;
86
return
algorithm::acyclic;
87
}
88
111
template
<
typename
Node1,
typename
Node2>
112
[[nodiscard]] uint64_t
count
(WordGraph<Node1>
const
& wg, Node2 source);
113
134
// Not noexcept because v4::word_graph::topological_sort is not.
135
template
<
typename
Node1,
typename
Node2>
136
[[nodiscard]]
algorithm
count_algorithm(WordGraph<Node1>
const
& wg,
137
Node2 source,
138
size_t
min,
139
size_t
max);
140
190
// not noexcept for example detail::count_trivial can throw
191
template
<
typename
Node1,
typename
Node2>
192
[[nodiscard]] uint64_t
count
(WordGraph<Node1>
const
& wg,
193
Node2 source,
194
size_t
min,
195
size_t
max,
196
algorithm lgrthm = algorithm::automatic);
197
220
// Not noexcept because v4::word_graph::topological_sort isn't
221
template
<
typename
Node1,
typename
Node2>
222
[[nodiscard]]
algorithm
count_algorithm(WordGraph<Node1>
const
& wg,
223
Node2 source,
224
Node2 target,
225
size_t
min,
226
size_t
max);
227
272
// not noexcept because cbegin_pstilo isn't
273
template
<
typename
Node1,
typename
Node2>
274
[[nodiscard]] uint64_t
count
(WordGraph<Node1>
const
& wg,
275
Node2 source,
276
Node2 target,
277
size_t
min,
278
size_t
max,
279
algorithm lgrthm = algorithm::automatic);
280
}
// namespace paths
281
}
// namespace libsemigroups::v4
282
#endif
283
284
#include "paths-count.tpp"
285
286
#endif
// LIBSEMIGROUPS_PATHS_COUNT_HPP_
std::count
T count(T... args)
libsemigroups::paths::algorithm
v4::paths::algorithm algorithm
An enum for specifying the algorithm to the functions count().
libsemigroups::ukkonen::dfs
auto dfs(Ukkonen const &u, T &helper)
Perform a depth first search in a suffix tree.
include
libsemigroups
paths-count.hpp
Generated by
1.18.0