Lines
95.45 %
Functions
41.67 %
Branches
100 %
#![forbid(unsafe_code)]
use rand::Rng;
use rand::RngExt;
use rand::distr::Uniform;
use merc_utilities::MercError;
use crate::LTS;
use crate::LabelledTransitionSystem;
use crate::LtsBuilder;
use crate::LtsBuilderFast;
use crate::StateIndex;
use crate::TransitionLabel;
/// Generates a random LTS with the desired number of states and labels. Uses
/// the given [crate::TransitionLabel] type to generate the transition labels.
///
/// # Details
/// The number of labels is limited to 26, since only singular alphabetic labels
/// are used, because those are easier to read and understand.
pub fn random_lts<L: TransitionLabel, R: Rng>(
rng: &mut R,
num_of_states: usize,
num_of_labels: u32,
) -> LabelledTransitionSystem<L> {
assert!(
num_of_labels < 26,
"Too many labels requested, we only support alphabetic labels."
);
// Introduce lower case letters for the labels.
let mut labels: Vec<L> = Vec::new();
labels.push(L::tau_label()); // The initial hidden label, assumed to be index 0.
for i in 0..(num_of_labels - 1) {
labels.push(L::from_index(i as usize));
}
let mut builder = LtsBuilderFast::with_capacity(labels.clone(), Vec::new(), num_of_states);
for state_index in 0..num_of_states {
// Introduce outgoing transitions for this state based on the desired out degree.
for _ in 0..rng.random_range(0..num_of_labels) {
// Pick a random label and state.
let label = rng.random_range(0..num_of_labels);
let to = rng.random_range(0..num_of_states);
builder
.add_transition(
StateIndex::new(state_index),
&labels[label as usize],
StateIndex::new(to),
)
.expect("Adding transitions does not fail");
// Ensure there is at least one state (otherwise it would be an LTS without initial state).
builder.require_num_of_states(num_of_states.max(1));
builder.finish(StateIndex::new(rng.random_range(0..num_of_states)), true)
/// Mutates the given LTS by randomly adding and removing transitions, and
/// changing the labels of some transitions. The number of mutations is
/// determined by the `num_of_mutations` parameter.
pub fn mutate_lts<L: LTS, R: Rng>(
lts: &L,
num_of_mutations: usize,
) -> Result<LabelledTransitionSystem<L::Label>, MercError> {
let mut builder = LtsBuilderFast::new(lts.labels().to_vec(), Vec::new());
builder.require_num_of_states(lts.num_of_states());
let removed_transition = if num_of_mutations > 0 {
rng.random_range(0..num_of_mutations)
} else {
0
};
// The indices of the transitions to remove.
let to_remove = if lts.num_of_transitions() > 0 {
let uniform = Uniform::new(0, lts.num_of_transitions())?;
rng.sample_iter(uniform).take(removed_transition).collect::<Vec<_>>()
Vec::new()
let mut index = 0;
for state in lts.iter_states() {
for transition in lts.outgoing_transitions(state) {
// Skip this transition if it is one of the transitions to remove.
if !to_remove.contains(&index) {
.add_transition(state, <s.labels()[transition.label], transition.to)
index += 1;
// Add new random transitions for the remaining mutations.
let added_transitions = num_of_mutations - removed_transition;
if lts.num_of_states() > 0 && !lts.labels().is_empty() {
let state_uniform = Uniform::new(0, lts.num_of_states())?;
let label_uniform = Uniform::new(0, lts.labels().len())?;
for _ in 0..added_transitions {
let from = StateIndex::new(rng.sample(state_uniform));
let label = rng.sample(label_uniform);
let to = StateIndex::new(rng.sample(state_uniform));
builder.add_transition(from, <s.labels()[label], to).unwrap();
Ok(builder.finish(lts.initial_state_index(), true))