12650654883

Committed 07 Jan 2025 11:26AM UTC coverage: 91.569%. First build

Build # 12650654883

Build Type

Pull #85

github

Committed by

web-flow

Commit Message

Merge 2499df5ae into d156e0830

Pull Request Pull Request #85: Update dependencies

Run Details

192 of 217 new or added lines in 63 files covered. (88.48%)

16573 of 18099 relevant lines covered (91.57%)

1.69 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

55.56

/util/src/main/java/net/automatalib/util/automaton/random/RandomICAutomatonGenerator.java

/* Copyright (C) 2013-2024 TU Dortmund University
 * This file is part of AutomataLib, http://www.automatalib.net/.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package net.automatalib.util.automaton.random;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.List;
import java.util.Objects;
import java.util.Random;
import java.util.function.Function;
import java.util.function.Supplier;

import net.automatalib.alphabet.Alphabet;
import net.automatalib.automaton.AutomatonCreator;
import net.automatalib.automaton.MutableDeterministic;
import net.automatalib.common.util.collection.CollectionUtil;
import net.automatalib.common.util.random.RandomUtil;
import org.checkerframework.checker.nullness.qual.Nullable;

/**
 * A random generator for initially connected (IC) deterministic automata.
 * <p>
 * The object state of instances of this class only determines how state and transition properties are assigned. These
 * can be set conveniently using the {@code with...} methods in a fluent interface-like manner.
 * <p>
 * For conveniently generating initially connected deterministic automata of certain types, consider using the static
 * methods defined in class {@link RandomAutomata}, such as {@link RandomAutomata#randomICDFA(Random, int, Alphabet,
 * boolean)}.
 *
 * @param <SP>
 *         state property type
 * @param <TP>
 *         transition property type
 */
@SuppressWarnings("nullness") // for now the nullness of SP/TP depends on the provided suppliers
public class RandomICAutomatonGenerator<SP, TP> {

    private Function<? super Random, ? extends @Nullable SP> spSupplier = r -> null;
    private Function<? super Random, ? extends @Nullable TP> tpSupplier = r -> null;

    /**
     * Creates a random IC automaton generator instance for generating DFAs. States in generated automata will be
     * accepting or rejecting with equal probability.
     *
     * @return a random IC automaton generator instance for generating DFAs
     */
    public static RandomICAutomatonGenerator<Boolean, Void> forDFA() {
        return new RandomICAutomatonGenerator<Boolean, Void>().withStateProperties(Random::nextBoolean);
    }

    /**
     * Creates a random IC automaton generator instance for generating DFAs. The {@code acceptingRatio} parameter
     * controls the probability of a state in a generated automaton being an accepting state.
     *
     * @param acceptingRatio
     *         the (approximate) ratio of accepting states in generated automata
     *
     * @return a random IC automaton generator instance for generating DFAs
     */
    public static RandomICAutomatonGenerator<Boolean, Void> forDFA(double acceptingRatio) {
        return new RandomICAutomatonGenerator<Boolean, Void>().withStateProperties(r -> r.nextDouble() <
                                                                                        acceptingRatio);
    }

    /**
     * Sets the function for supplying state properties, and returns {@code this}.
     *
     * @param spFunc
     *         the function that supplies state properties, using a {@link Random} object as a source for randomness
     *
     * @return {@code this}
     */
    public RandomICAutomatonGenerator<SP, TP> withStateProperties(Function<? super Random, ? extends SP> spFunc) {
        this.spSupplier = Objects.requireNonNull(spFunc);
        return this;
    }

    /**
     * Sets the supplier for state properties, and returns {@code this}.
     * <p>
     * Using this function is discouraged, as it ignores the {@link Random} instance passed to the generation functions.
     * If possible, use {@link #withStateProperties(Function)}.
     *
     * @param spSupplier
     *         the supplier for state properties
     *
     * @return {@code this}
     */
    public RandomICAutomatonGenerator<SP, TP> withStateProperties(Supplier<? extends SP> spSupplier) {
        return withStateProperties(r -> spSupplier.get());
    }

    /**
     * Sets the possible state properties, and returns {@code this}. The collection is internally converted into a list,
     * from which state properties are selected using {@link RandomUtil#choose(Random, List)}. If the collection is
     * empty, {@code null} will always be chosen as the state property.
     * <p>
     * Note that if the collection contains elements several times, the probability of these elements being selected is
     * proportionally higher.
     *
     * @param possibleSps
     *         the collection of possible state properties
     *
     * @return {@code this}
     */
    public RandomICAutomatonGenerator<SP, TP> withStateProperties(Collection<? extends SP> possibleSps) {
        if (possibleSps.isEmpty()) {
            return withStateProperties(r -> null);
        }
        List<SP> spList = new ArrayList<>(possibleSps);
        return withStateProperties(r -> RandomUtil.choose(r, spList));
    }

    /**
     * Sets the possible state properties, and returns {@code this}. State properties are selected from this array using
     * {@link RandomUtil#choose(Random, Object[])}. If the array is empty, {@code null} will always be chosen as the
     * state property.
     *
     * @param possibleSps
     *         the possible state properties
     *
     * @return {@code this}
     */
    @SafeVarargs
    public final RandomICAutomatonGenerator<SP, TP> withStateProperties(SP... possibleSps) {
        if (possibleSps.length == 0) {
            return withStateProperties(r -> null);
        }
        return withStateProperties(r -> RandomUtil.choose(r, possibleSps));
    }

    /**
     * Sets the supplier for transition properties, and returns {@code this}.
     * <p>
     * Using this function is discouraged, as it ignores the {@link Random} instance passed to the generation functions.
     * If possible, use {@link #withTransitionProperties(Function)}.
     *
     * @param tpSupplier
     *         the supplier for transition properties
     *
     * @return {@code this}
     */
    public RandomICAutomatonGenerator<SP, TP> withTransitionProperties(Supplier<? extends TP> tpSupplier) {
        return withTransitionProperties(r -> tpSupplier.get());
    }

    /**
     * Sets the function for supplying transition properties, and returns {@code this}.
     *
     * @param tpFunc
     *         the function that supplies transition properties, using a {@link Random} object as a source for
     *         randomness
     *
     * @return {@code this}
     */
    public RandomICAutomatonGenerator<SP, TP> withTransitionProperties(Function<? super Random, ? extends TP> tpFunc) {
        this.tpSupplier = Objects.requireNonNull(tpFunc);
        return this;
    }

    /**
     * Sets the possible transition properties, and returns {@code this}. Transition properties are selected from this
     * array using {@link RandomUtil#choose(Random, Object[])}. If the array is empty, {@code null} will always be
     * chosen as the state property.
     *
     * @param possibleTps
     *         the possible transition properties
     *
     * @return {@code this}
     */
    @SafeVarargs
    public final RandomICAutomatonGenerator<SP, TP> withTransitionProperties(TP... possibleTps) {
        if (possibleTps.length == 0) {
            return withTransitionProperties(r -> null);
        }
        return withTransitionProperties(Arrays.asList(possibleTps));
    }

    /**
     * Sets the possible transition properties, and returns {@code this}. The collection is internally converted into a
     * list, from which transition properties are selected using {@link RandomUtil#choose(Random, List)}. If the
     * collection is empty, {@code null} will always be chosen as the transition property.
     * <p>
     * Note that if the collection contains elements several times, the probability of these elements being selected is
     * proportionally higher.
     *
     * @param possibleTps
     *         the collection of possible transition properties
     *
     * @return {@code this}
     */
    public RandomICAutomatonGenerator<SP, TP> withTransitionProperties(Collection<? extends TP> possibleTps) {
        if (possibleTps.isEmpty()) {
            return withTransitionProperties(r -> null);
        }
        List<TP> tpList = new ArrayList<>(possibleTps);
        return withTransitionProperties(r -> RandomUtil.choose(r, tpList));
    }

    /**
     * Generates an initially-connected (IC) deterministic automaton with the given parameters. The resulting automaton
     * is instantiated using the given {@code creator}. Note that the resulting automaton will <b>not</b> be minimized.
     *
     * @param numStates
     *         the number of states of the resulting automaton
     * @param alphabet
     *         the input alphabet of the resulting automaton
     * @param creator
     *         an {@link AutomatonCreator} for instantiating the result automaton
     * @param r
     *         the randomness source
     * @param <I>
     *         input symbol type
     * @param <A>
     *         automaton type
     *
     * @return a randomly-generated IC deterministic automaton
     */
    public <I, A extends MutableDeterministic<?, I, ?, ? super SP, ? super TP>> A generateICDeterministicAutomaton(int numStates,
                                                                                                                   Alphabet<I> alphabet,
                                                                                                                   AutomatonCreator<? extends A, I> creator,
                                                                                                                   Random r) {
        A result = creator.createAutomaton(alphabet, numStates);
        return generateICDeterministicAutomaton(numStates, alphabet, result, r);
    }

    /**
     * Generates an initially connected (IC) deterministic automaton with the given parameters. Note that the automaton
     * will <b>not</b> be minimized.
     *
     * @param numStates
     *         the number of states of the resulting automaton
     * @param inputs
     *         the input symbols to consider during generation
     * @param result
     *         the result automaton (should be empty)
     * @param r
     *         the randomness source
     * @param <I>
     *         input symbol type
     * @param <A>
     *         automaton type
     *
     * @return the result automaton
     */
    public <I, A extends MutableDeterministic<?, I, ?, ? super SP, ? super TP>> A generateICDeterministicAutomaton(int numStates,
                                                                                                                   Collection<? extends I> inputs,
                                                                                                                   A result,
                                                                                                                   Random r) {
        MutableDeterministic.StateIntAbstraction<I, ?, ? super SP, ? super TP> resultAbs = result.stateIntAbstraction();

        List<? extends I> inputsList = CollectionUtil.randomAccessList(inputs);

        resultAbs.addIntInitialState(spSupplier.apply(r));
        for (int i = 1; i < numStates; i++) {
            int src, succ;
            I input;
            do {
                src = r.nextInt(i);
                input = RandomUtil.choose(r, inputsList);
                succ = resultAbs.getSuccessor(src, input);
            } while (succ >= 0);
            int next = resultAbs.addIntState(spSupplier.apply(r));
            resultAbs.setTransition(src, input, next, tpSupplier.apply(r));
        }

        for (int i = 0; i < numStates; i++) {
            for (I input : inputs) {
                if (resultAbs.getSuccessor(i, input) >= 0) {
                    continue;
                }
                int succ = r.nextInt(numStates);
                resultAbs.setTransition(i, input, succ, tpSupplier.apply(r));
            }
        }

        return result;
    }

}

1	/* Copyright (C) 2013-2024 TU Dortmund University
2	* This file is part of AutomataLib, http://www.automatalib.net/.
3	*
4	* Licensed under the Apache License, Version 2.0 (the "License");
5	* you may not use this file except in compliance with the License.
6	* You may obtain a copy of the License at
7	*
8	* http://www.apache.org/licenses/LICENSE-2.0
9	*
10	* Unless required by applicable law or agreed to in writing, software
11	* distributed under the License is distributed on an "AS IS" BASIS,
12	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13	* See the License for the specific language governing permissions and
14	* limitations under the License.
15	*/
16	package net.automatalib.util.automaton.random;
17
18	import java.util.ArrayList;
19	import java.util.Arrays;
20	import java.util.Collection;
21	import java.util.List;
22	import java.util.Objects;
23	import java.util.Random;
24	import java.util.function.Function;
25	import java.util.function.Supplier;
26
27	import net.automatalib.alphabet.Alphabet;
28	import net.automatalib.automaton.AutomatonCreator;
29	import net.automatalib.automaton.MutableDeterministic;
30	import net.automatalib.common.util.collection.CollectionUtil;
31	import net.automatalib.common.util.random.RandomUtil;
32	import org.checkerframework.checker.nullness.qual.Nullable;
33
34	/**
35	* A random generator for initially connected (IC) deterministic automata.
36	* <p>
37	* The object state of instances of this class only determines how state and transition properties are assigned. These
38	* can be set conveniently using the {@code with...} methods in a fluent interface-like manner.
39	* <p>
40	* For conveniently generating initially connected deterministic automata of certain types, consider using the static
41	* methods defined in class {@link RandomAutomata}, such as {@link RandomAutomata#randomICDFA(Random, int, Alphabet,
42	* boolean)}.
43	*
44	* @param <SP>
45	* state property type
46	* @param <TP>
47	* transition property type
48	*/
49	@SuppressWarnings("nullness") // for now the nullness of SP/TP depends on the provided suppliers
50	public class RandomICAutomatonGenerator<SP, TP> {	2✔
51
52	private Function<? super Random, ? extends @Nullable SP> spSupplier = r -> null;	2✔
53	private Function<? super Random, ? extends @Nullable TP> tpSupplier = r -> null;	2✔
54
55	/**
56	* Creates a random IC automaton generator instance for generating DFAs. States in generated automata will be
57	* accepting or rejecting with equal probability.
58	*
59	* @return a random IC automaton generator instance for generating DFAs
60	*/
61	public static RandomICAutomatonGenerator<Boolean, Void> forDFA() {
62	return new RandomICAutomatonGenerator<Boolean, Void>().withStateProperties(Random::nextBoolean);	×
63	}
64
65	/**
66	* Creates a random IC automaton generator instance for generating DFAs. The {@code acceptingRatio} parameter
67	* controls the probability of a state in a generated automaton being an accepting state.
68	*
69	* @param acceptingRatio
70	* the (approximate) ratio of accepting states in generated automata
71	*
72	* @return a random IC automaton generator instance for generating DFAs
73	*/
74	public static RandomICAutomatonGenerator<Boolean, Void> forDFA(double acceptingRatio) {
75	return new RandomICAutomatonGenerator<Boolean, Void>().withStateProperties(r -> r.nextDouble() <	×
76	acceptingRatio);
77	}
78
79	/**
80	* Sets the function for supplying state properties, and returns {@code this}.
81	*
82	* @param spFunc
83	* the function that supplies state properties, using a {@link Random} object as a source for randomness
84	*
85	* @return {@code this}
86	*/
87	public RandomICAutomatonGenerator<SP, TP> withStateProperties(Function<? super Random, ? extends SP> spFunc) {
88	this.spSupplier = Objects.requireNonNull(spFunc);	2✔
89	return this;	2✔
90	}
91
92	/**
93	* Sets the supplier for state properties, and returns {@code this}.
94	* <p>
95	* Using this function is discouraged, as it ignores the {@link Random} instance passed to the generation functions.
96	* If possible, use {@link #withStateProperties(Function)}.
97	*
98	* @param spSupplier
99	* the supplier for state properties
100	*
101	* @return {@code this}
102	*/
103	public RandomICAutomatonGenerator<SP, TP> withStateProperties(Supplier<? extends SP> spSupplier) {
104	return withStateProperties(r -> spSupplier.get());	×
105	}
106
107	/**
108	* Sets the possible state properties, and returns {@code this}. The collection is internally converted into a list,
109	* from which state properties are selected using {@link RandomUtil#choose(Random, List)}. If the collection is
110	* empty, {@code null} will always be chosen as the state property.
111	* <p>
112	* Note that if the collection contains elements several times, the probability of these elements being selected is
113	* proportionally higher.
114	*
115	* @param possibleSps
116	* the collection of possible state properties
117	*
118	* @return {@code this}
119	*/
120	public RandomICAutomatonGenerator<SP, TP> withStateProperties(Collection<? extends SP> possibleSps) {
121	if (possibleSps.isEmpty()) {	×
122	return withStateProperties(r -> null);	×
123	}
124	List<SP> spList = new ArrayList<>(possibleSps);	×
NEW 125	return withStateProperties(r -> RandomUtil.choose(r, spList));	×
126	}
127
128	/**
129	* Sets the possible state properties, and returns {@code this}. State properties are selected from this array using
130	* {@link RandomUtil#choose(Random, Object[])}. If the array is empty, {@code null} will always be chosen as the
131	* state property.
132	*
133	* @param possibleSps
134	* the possible state properties
135	*
136	* @return {@code this}
137	*/
138	@SafeVarargs
139	public final RandomICAutomatonGenerator<SP, TP> withStateProperties(SP... possibleSps) {
140	if (possibleSps.length == 0) {	×
141	return withStateProperties(r -> null);	×
142	}
143	return withStateProperties(r -> RandomUtil.choose(r, possibleSps));	×
144	}
145
146	/**
147	* Sets the supplier for transition properties, and returns {@code this}.
148	* <p>
149	* Using this function is discouraged, as it ignores the {@link Random} instance passed to the generation functions.
150	* If possible, use {@link #withTransitionProperties(Function)}.
151	*
152	* @param tpSupplier
153	* the supplier for transition properties
154	*
155	* @return {@code this}
156	*/
157	public RandomICAutomatonGenerator<SP, TP> withTransitionProperties(Supplier<? extends TP> tpSupplier) {
158	return withTransitionProperties(r -> tpSupplier.get());	×
159	}
160
161	/**
162	* Sets the function for supplying transition properties, and returns {@code this}.
163	*
164	* @param tpFunc
165	* the function that supplies transition properties, using a {@link Random} object as a source for
166	* randomness
167	*
168	* @return {@code this}
169	*/
170	public RandomICAutomatonGenerator<SP, TP> withTransitionProperties(Function<? super Random, ? extends TP> tpFunc) {
171	this.tpSupplier = Objects.requireNonNull(tpFunc);	×
172	return this;	×
173	}
174
175	/**
176	* Sets the possible transition properties, and returns {@code this}. Transition properties are selected from this
177	* array using {@link RandomUtil#choose(Random, Object[])}. If the array is empty, {@code null} will always be
178	* chosen as the state property.
179	*
180	* @param possibleTps
181	* the possible transition properties
182	*
183	* @return {@code this}
184	*/
185	@SafeVarargs
186	public final RandomICAutomatonGenerator<SP, TP> withTransitionProperties(TP... possibleTps) {
187	if (possibleTps.length == 0) {	×
188	return withTransitionProperties(r -> null);	×
189	}
190	return withTransitionProperties(Arrays.asList(possibleTps));	×
191	}
192
193	/**
194	* Sets the possible transition properties, and returns {@code this}. The collection is internally converted into a
195	* list, from which transition properties are selected using {@link RandomUtil#choose(Random, List)}. If the
196	* collection is empty, {@code null} will always be chosen as the transition property.
197	* <p>
198	* Note that if the collection contains elements several times, the probability of these elements being selected is
199	* proportionally higher.
200	*
201	* @param possibleTps
202	* the collection of possible transition properties
203	*
204	* @return {@code this}
205	*/
206	public RandomICAutomatonGenerator<SP, TP> withTransitionProperties(Collection<? extends TP> possibleTps) {
207	if (possibleTps.isEmpty()) {	×
208	return withTransitionProperties(r -> null);	×
209	}
210	List<TP> tpList = new ArrayList<>(possibleTps);	×
NEW 211	return withTransitionProperties(r -> RandomUtil.choose(r, tpList));	×
212	}
213
214	/**
215	* Generates an initially-connected (IC) deterministic automaton with the given parameters. The resulting automaton
216	* is instantiated using the given {@code creator}. Note that the resulting automaton will <b>not</b> be minimized.
217	*
218	* @param numStates
219	* the number of states of the resulting automaton
220	* @param alphabet
221	* the input alphabet of the resulting automaton
222	* @param creator
223	* an {@link AutomatonCreator} for instantiating the result automaton
224	* @param r
225	* the randomness source
226	* @param <I>
227	* input symbol type
228	* @param <A>
229	* automaton type
230	*
231	* @return a randomly-generated IC deterministic automaton
232	*/
233	public <I, A extends MutableDeterministic<?, I, ?, ? super SP, ? super TP>> A generateICDeterministicAutomaton(int numStates,
234	Alphabet<I> alphabet,
235	AutomatonCreator<? extends A, I> creator,
236	Random r) {
237	A result = creator.createAutomaton(alphabet, numStates);	2✔
238	return generateICDeterministicAutomaton(numStates, alphabet, result, r);	2✔
239	}
240
241	/**
242	* Generates an initially connected (IC) deterministic automaton with the given parameters. Note that the automaton
243	* will <b>not</b> be minimized.
244	*
245	* @param numStates
246	* the number of states of the resulting automaton
247	* @param inputs
248	* the input symbols to consider during generation
249	* @param result
250	* the result automaton (should be empty)
251	* @param r
252	* the randomness source
253	* @param <I>
254	* input symbol type
255	* @param <A>
256	* automaton type
257	*
258	* @return the result automaton
259	*/
260	public <I, A extends MutableDeterministic<?, I, ?, ? super SP, ? super TP>> A generateICDeterministicAutomaton(int numStates,
261	Collection<? extends I> inputs,
262	A result,
263	Random r) {
264	MutableDeterministic.StateIntAbstraction<I, ?, ? super SP, ? super TP> resultAbs = result.stateIntAbstraction();	2✔
265
266	List<? extends I> inputsList = CollectionUtil.randomAccessList(inputs);	2✔
267
268	resultAbs.addIntInitialState(spSupplier.apply(r));	2✔
269	for (int i = 1; i < numStates; i++) {	2✔
270	int src, succ;
271	I input;
272	do {
273	src = r.nextInt(i);	2✔
274	input = RandomUtil.choose(r, inputsList);	2✔
275	succ = resultAbs.getSuccessor(src, input);	2✔
276	} while (succ >= 0);	2✔
277	int next = resultAbs.addIntState(spSupplier.apply(r));	2✔
278	resultAbs.setTransition(src, input, next, tpSupplier.apply(r));	2✔
279	}
280
281	for (int i = 0; i < numStates; i++) {	2✔
282	for (I input : inputs) {	2✔
283	if (resultAbs.getSuccessor(i, input) >= 0) {	2✔
284	continue;	2✔
285	}
286	int succ = r.nextInt(numStates);	2✔
287	resultAbs.setTransition(i, input, succ, tpSupplier.apply(r));	2✔
288	}	2✔
289	}
290
291	return result;	2✔
292	}
293
294	}

LearnLib / automatalib / 12650654883

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous