Struct RandomWalkMethod 

pub struct RandomWalkMethod { /* private fields */ }

Random-walk based equivalence-test strategy.

Implementations

impl RandomWalkMethod

pub fn new( knowledge_base: Arc<Mutex<dyn KnowledgeBaseTrait>>, input_letters: Vec<Letter>, max_steps: usize, restart_probability: f64, ) -> Self

Create a new random-walk equivalence tester.

max_steps bounds the number of transitions explored, and restart_probability controls how often the walk restarts at the initial state.

Examples found in repository

examples/all_eqtests_custom_kb.rs (line 30)

fn main() -> Result<(), Box<dyn std::error::Error>> {
    println!("=== Custom KB: All Equivalence Tests ===");
    println!("System under learning: ATM protocol");

    let mut reports = Vec::new();

    let strategies: Vec<(&str, Box<EqBuilder>)> = vec![
        (
            "WMethodEQ",
            Box::new(|kb, input_letters, max_states| {
                Arc::new(WMethodEQ::new(kb, input_letters, max_states))
            }),
        ),
        (
            "RandomWalkMethod",
            Box::new(|kb, input_letters, _| {
                Arc::new(RandomWalkMethod::new(kb, input_letters, 10_000, 0.75))
            }),
        ),
        (
            "BDistMethod",
            Box::new(|kb, input_letters, _| Arc::new(BDistMethod::new(kb, input_letters, 2))),
        ),
        (
            "MultipleEqtests",
            Box::new(|kb, input_letters, max_states| {
                let eqtests: Vec<Arc<dyn EquivalenceTest>> = vec![
                    Arc::new(WMethodEQ::new(
                        kb.clone(),
                        input_letters.clone(),
                        max_states,
                    )),
                    Arc::new(RandomWalkMethod::new(
                        kb.clone(),
                        input_letters.clone(),
                        5_000,
                        0.65,
                    )),
                    Arc::new(BDistMethod::new(kb, input_letters, 2)),
                ];
                Arc::new(MultipleEqtests::new(eqtests))
            }),
        ),
    ];

    for (name, builder) in strategies {
        reports.push(run_strategy(name, builder.as_ref()));
    }

    print_summary(&reports);

    Ok(())
}

examples/random_walk_eq.rs (lines 44-49)

fn main() -> Result<(), Box<dyn std::error::Error>> {
    println!("=== Random Walk Equivalence Test Example ===\n");

    // Create a simple system
    let mut kb = DemoKnowledgeBase::new();

    // Define a simple state machine:
    // S0 -a/0-> S1   (initial state)
    // S0 -b/1-> S0
    // S1 -a/0-> S2
    // S1 -b/1-> S0
    // S2 -a/0-> S2
    // S2 -b/1-> S1

    // Make outputs state-dependent so learner must distinguish states
    kb.add_transition("s0", "a", "0", "s1");
    kb.add_transition("s0", "b", "1", "s0");
    kb.add_transition("s1", "a", "1", "s2");
    kb.add_transition("s1", "b", "0", "s0");
    kb.add_transition("s2", "a", "1", "s2");
    kb.add_transition("s2", "b", "0", "s1");

    let knowledge_base = Arc::new(Mutex::new(kb));

    // Create vocabulary
    let vocabulary = vec!["a".to_string(), "b".to_string()];

    // Create learner
    let mut lstar = LSTAR::new(vocabulary.clone(), knowledge_base.clone(), 5, None, None);

    // Use random walk equivalence test instead of W-method
    let input_letters = vocabulary
        .iter()
        .map(|s| Letter::new(s))
        .collect::<Vec<_>>();
    let random_walk = RandomWalkMethod::new(
        knowledge_base.clone(),
        input_letters,
        10000, // max_steps: 10000 steps
        0.75,  // restart_probability: 75%
    );

    lstar = lstar.with_equivalence_test(Arc::new(random_walk));

    // Run learning
    match lstar.learn() {
        Ok(automata) => {
            println!("\n=== Learned Automaton (Random Walk Test) ===\n");
            println!("{}", automata.build_dot_code());
            println!("\nLearning completed successfully!");

            // Print statistics
            println!("\nStatistics:");
            println!("  Number of states: {}", automata.get_states().len());
            println!("  Number of transitions: {}", automata.transitions.len());
        }
        Err(e) => eprintln!("Error during learning: {}", e),
    }

    let kb_guard = knowledge_base.lock().unwrap();
    println!("\nKnowledge Base Statistics:\n{}", kb_guard.stats);

    Ok(())
}

Trait Implementations

impl EquivalenceTest for RandomWalkMethod

fn find_counterexample( &self, hypothesis: &mut Automata, ) -> Option<Counterexample>

Find a counterexample for the given hypothesis Returns None if the automaton is equivalent to the system under learning