39 template <
typename Ctx>
40 mutable_automaton<Ctx>
42 unsigned num_states,
float density = 0.1,
43 unsigned num_initial = 1,
unsigned num_final = 1,
44 boost::optional<unsigned> max_labels = {},
45 float loop_chance = 0.0)
47 require(0 <= density && density <= 1,
48 "random_automaton: density must be in [0,1]");
49 require(0 <= loop_chance && loop_chance <= 1,
50 "random_automaton: loop chance must be in [0,1]");
53 using automaton_t = mutable_automaton<Ctx>;
54 using state_t = state_t_of<automaton_t>;
55 auto res = make_shared_ptr<automaton_t>(
ctx);
60 const auto& ls = *ctx.labelset();
64 "random_automaton: max number of labels cannot be null");
66 require(*max_labels <= boost::distance(ls.generators()) + ls.has_one(),
67 "random_automaton: max number of labels cannot be greater "
68 "than the number of generators");
72 max_labels = (boost::distance(ls.generators()) + ls.has_one());
74 "random_automaton: empty labelset: ", ls);
76 auto num_labels = std::uniform_int_distribution<>(1, *max_labels);
78 auto states = std::vector<state_t>{};
79 states.reserve(num_states);
81 auto state_randomizer = std::vector<int>{};
82 state_randomizer.reserve(num_states);
87 using state_set = std::set<int>;
90 state_set unreachables;
94 states.emplace_back(
res->new_state());
95 state_randomizer.emplace_back(i);
98 unreachables.emplace(i);
100 res->set_initial(states[i]);
107 auto dis = std::uniform_int_distribution<>(i, num_states - 1);
108 int index = dis(gen);
109 res->set_final(states[state_randomizer[index]]);
112 std::swap(state_randomizer[index], state_randomizer[i]);
118 auto bin = std::binomial_distribution<>(num_states - 1, density);
123 while (!worklist.empty())
125 auto src = states[*worklist.begin()];
126 worklist.erase(worklist.begin());
130 unsigned nsucc = 1 + bin(gen);
135 bool saw_unreachable =
false;
136 auto possibilities = num_states;
145 && !unreachables.empty())
148 dst = pick.pop(unreachables);
149 worklist.insert(dst);
155 = std::uniform_int_distribution<>(0, possibilities - 1);
156 int index = dis(gen);
159 dst = state_randomizer[index];
163 std::swap(state_randomizer[index],
164 state_randomizer[possibilities]);
166 state_set::iterator j = unreachables.find(dst);
167 if (j != unreachables.end())
169 worklist.insert(dst);
170 unreachables.erase(j);
171 saw_unreachable =
true;
174 auto n = num_labels(gen);
176 res->add_transition(src, states[dst],
184 auto dis = std::bernoulli_distribution(loop_chance);
185 for (
auto s :
res->states())
198 template <
typename Ctx,
typename NumStates,
typename Density,
199 typename NumInitial,
typename NumFinal,
200 typename MaxLabels,
typename LoopChance>
203 unsigned num_states,
float density,
204 unsigned num_initial,
unsigned num_final,
205 boost::optional<unsigned> max_labels,
208 const auto& c = ctx->
as<Ctx>();
210 num_initial, num_final,
222 template <
typename Ctx>
223 mutable_automaton<Ctx>
226 require(0 < num_states,
"num_states must be > 0");
230 automaton_t
res = make_shared_ptr<automaton_t>(
ctx);
233 auto dis = std::uniform_int_distribution<int>(0, num_states - 1);
235 auto states = std::vector<state_t>{};
236 states.reserve(num_states);
239 states.emplace_back(res->new_state());
242 for (
auto l : ctx.labelset()->generators())
243 res->add_transition(states[i], states[dis(gen)], l,
244 ctx.weightset()->one());
246 res->set_initial(states[dis(gen)]);
247 res->set_final(states[dis(gen)]);
257 template <
typename Ctx,
typename>
261 const auto& c = ctx->
as<Ctx>();
automaton random_automaton_deterministic(const context &ctx, unsigned num_states)
Bridge.
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
automaton random_automaton(const context &ctx, unsigned num_states, float density, unsigned num_initial, unsigned num_final, boost::optional< unsigned > max_labels, float loop_chance)
Bridge.
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
auto & as()
Downcast to the exact type.
random_selector< RandomGenerator > make_random_selector(RandomGenerator &g)
Template-less root for contexts.
std::mt19937 & make_random_engine()
Generate a unique random device.
mutable_automaton< Ctx > random_automaton_deterministic(const Ctx &ctx, unsigned num_states)
std::shared_ptr< detail::mutable_automaton_impl< Context >> mutable_automaton
expressionset< Context >::value_t random_label(const expressionset< Context > &rs, RandomGenerator &gen=RandomGenerator())
Random label from expressionset: limited to a single label.
auto irange(Integer last)
Generate an integer range.
mutable_automaton< Ctx > random_automaton(const Ctx &ctx, unsigned num_states, float density=0.1, unsigned num_initial=1, unsigned num_final=1, boost::optional< unsigned > max_labels={}, float loop_chance=0.0)
Produce a random automaton.