13138848026

Committed 04 Feb 2025 02:53PM UTC coverage: 92.108% (+2.2%) from 89.877%

Build # 13138848026

Build Type

push

github

Committed by

mtf90

Commit Message

[maven-release-plugin] prepare release automatalib-0.12.0

Run Details

16609 of 18032 relevant lines covered (92.11%)

1.7 hits per line

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

95.58

/util/src/main/java/net/automatalib/util/automaton/Automata.java

/* Copyright (C) 2013-2025 TU Dortmund University
 * This file is part of AutomataLib <https://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;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;

import net.automatalib.automaton.Automaton;
import net.automatalib.automaton.DeterministicAutomaton;
import net.automatalib.automaton.MutableDeterministic;
import net.automatalib.automaton.UniversalDeterministicAutomaton;
import net.automatalib.automaton.graph.TransitionEdge;
import net.automatalib.common.util.array.ArrayStorage;
import net.automatalib.common.util.collection.CollectionUtil;
import net.automatalib.graph.Graph;
import net.automatalib.graph.UniversalGraph;
import net.automatalib.util.automaton.cover.Covers;
import net.automatalib.util.automaton.equivalence.CharacterizingSets;
import net.automatalib.util.automaton.equivalence.DeterministicEquivalenceTest;
import net.automatalib.util.automaton.equivalence.NearLinearEquivalenceTest;
import net.automatalib.util.automaton.minimizer.HopcroftMinimizer;
import net.automatalib.util.minimizer.Block;
import net.automatalib.util.minimizer.MinimizationResult;
import net.automatalib.util.minimizer.Minimizer;
import net.automatalib.util.ts.TS;
import net.automatalib.util.ts.TS.TransRef;
import net.automatalib.word.Word;
import org.checkerframework.checker.nullness.qual.Nullable;

public final class Automata {

    private Automata() {
        // prevent instantiation
    }

    public static <S, I, T> Graph<S, TransitionEdge<I, T>> asGraph(Automaton<S, I, T> automaton,
                                                                   Collection<? extends I> inputs) {
        return automaton.transitionGraphView(inputs);
    }

    /**
     * Minimizes the given automaton. Internally, this method delegates to the
     * {@link Minimizer Beal-Crochemore algorithm} which performs well especially for partial automata. If you have a
     * total (or very dense) automaton, {@link HopcroftMinimizer} may provide better performance.
     *
     * @param automaton
     *         the automaton to minimize
     * @param inputs
     *         the inputs to consider for minimization
     * @param output
     *         the object to write the minimized automaton to
     * @param <S>
     *         (input) state type
     * @param <I>
     *         input symbol type
     * @param <T>
     *         (input) transition type
     * @param <SP>
     *         state property type
     * @param <TP>
     *         transition property type
     * @param <SO>
     *         (output) state type
     * @param <TO>
     *         (output) transition type
     * @param <A>
     *         explicit automaton type
     *
     * @return {@code output}, for convenience
     */
    public static <S, I, T, SP, TP, SO, TO, A extends MutableDeterministic<SO, ? super I, TO, ? super SP, ? super TP>> A minimize(
            UniversalDeterministicAutomaton<S, I, T, SP, TP> automaton,
            Collection<? extends I> inputs,
            A output) {

        UniversalGraph<S, TransitionEdge<I, T>, SP, TransitionEdge.Property<I, TP>> aag =
                automaton.transitionGraphView(inputs);

        MinimizationResult<S, TransitionEdge.Property<I, TP>> mr =
                Minimizer.minimize(aag, automaton.getInitialStates());
        output.clear();

        S init = automaton.getInitialState();
        Block<S, TransitionEdge.Property<I, TP>> initBlock = init == null ? null : mr.getBlockForState(init);
        ArrayStorage<SO> storage = new ArrayStorage<>(mr.getNumBlocks());

        for (Block<S, TransitionEdge.Property<I, TP>> block : mr.getBlocks()) {
            S rep = mr.getRepresentative(block);
            SO state;
            SP repProp = automaton.getStateProperty(rep);
            if (block == initBlock) {
                state = output.addInitialState(repProp);
            } else {
                state = output.addState(repProp);
            }
            storage.set(block.getId(), state);
        }

        for (Block<S, TransitionEdge.Property<I, TP>> block : mr.getBlocks()) {
            S rep = mr.getRepresentative(block);
            SO state = storage.get(block.getId());
            for (I input : inputs) {
                T trans = automaton.getTransition(rep, input);
                if (trans != null) {
                    TP prop = automaton.getTransitionProperty(trans);
                    S oldSucc = automaton.getSuccessor(trans);
                    Block<S, TransitionEdge.Property<I, TP>> succBlock = mr.getBlockForState(oldSucc);
                    SO newSucc = storage.get(succBlock.getId());
                    output.addTransition(state, input, newSucc, prop);
                }
            }
        }
        return output;
    }

    /**
     * Minimizes the given automaton in-place. Internally, this method delegates to the
     * {@link Minimizer Beal-Crochemore algorithm} which performs well especially for partial automata. If you have a
     * total automaton, {@link HopcroftMinimizer} may provide better performance.
     *
     * @param automaton
     *         the automaton to minimize
     * @param inputs
     *         the inputs to consider for minimization
     * @param <S>
     *         state type
     * @param <I>
     *         input symbol type
     * @param <T>
     *         transition type
     * @param <SP>
     *         state property type
     * @param <TP>
     *         transition property type
     * @param <A>
     *         automaton type
     *
     * @return {@code automaton}, for convenience
     */
    public static <S, I, T, SP, TP, A extends MutableDeterministic<S, I, T, SP, TP>> A invasiveMinimize(A automaton,
                                                                                                        Collection<? extends I> inputs) {

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

        int numInputs = inputs.size();

        UniversalGraph<S, TransitionEdge<I, T>, SP, TransitionEdge.Property<I, TP>> aag =
                automaton.transitionGraphView(inputs);

        MinimizationResult<S, TransitionEdge.Property<I, TP>> mr =
                Minimizer.minimize(aag, automaton.getInitialStates());

        S init = automaton.getInitialState();
        int initId = init == null ? -1 : mr.getBlockForState(init).getId();

        @SuppressWarnings("unchecked")
        ResultStateRecord<SP, TP>[] records = new ResultStateRecord[mr.getNumBlocks()];

        // Store minimized automaton data in the records array
        for (Block<S, TransitionEdge.Property<I, TP>> blk : mr.getBlocks()) {
            int id = blk.getId();
            S state = mr.getRepresentative(blk);
            SP prop = automaton.getStateProperty(state);
            ResultStateRecord<SP, TP> rec = new ResultStateRecord<>(numInputs, prop);
            records[id] = rec;
            for (int i = 0; i < numInputs; i++) {
                I input = inputList.get(i);
                T trans = automaton.getTransition(state, input);
                if (trans == null) {
                    continue;
                }

                TP transProp = automaton.getTransitionProperty(trans);
                S succ = automaton.getSuccessor(trans);
                int tgtId = mr.getBlockForState(succ).getId();
                rec.transitions[i] = new ResultTransRecord<>(tgtId, transProp);
            }
        }

        automaton.clear();

        // Add states from records
        @Nullable Object[] states = new Object[records.length];
        for (int i = 0; i < records.length; i++) {
            ResultStateRecord<SP, TP> rec = records[i];
            SP prop = rec.property;
            S state;
            if (i == initId) {
                state = automaton.addInitialState(prop);
            } else {
                state = automaton.addState(prop);
            }
            states[i] = state;
        }

        // Add transitions from records
        for (int i = 0; i < records.length; i++) {
            ResultStateRecord<SP, TP> rec = records[i];
            @SuppressWarnings("unchecked")
            S state = (S) states[i];

            for (int j = 0; j < numInputs; j++) {
                ResultTransRecord<TP> transRec = rec.transitions[j];
                if (transRec == null) {
                    continue;
                }
                @SuppressWarnings("unchecked")
                S succ = (S) states[transRec.targetId];
                I input = inputList.get(j);
                automaton.addTransition(state, input, succ, transRec.property);
            }
        }
        return automaton;
    }

    /**
     * Tests whether two automata are equivalent, i.e. whether there exists a
     * {@link #findSeparatingWord(UniversalDeterministicAutomaton, UniversalDeterministicAutomaton, Collection)
     * separating word} for the two given automata.
     *
     * @param <I>
     *         input symbol type
     * @param reference
     *         the one automaton to consider
     * @param other
     *         the other automaton to consider
     * @param inputs
     *         the input symbols to consider
     *
     * @return {@code true} if the automata are equivalent, {@code false} otherwise.
     *
     * @see #findSeparatingWord(UniversalDeterministicAutomaton, UniversalDeterministicAutomaton, Collection)
     */
    public static <I> boolean testEquivalence(UniversalDeterministicAutomaton<?, I, ?, ?, ?> reference,
                                              UniversalDeterministicAutomaton<?, I, ?, ?, ?> other,
                                              Collection<? extends I> inputs) {
        return findSeparatingWord(reference, other, inputs) == null;
    }

    /**
     * Finds a separating word for two automata. A separating word is a word that exposes a difference (differing state
     * or transition properties, or a transition undefined in only one of the automata) between the two automata.
     *
     * @param <I>
     *         input symbol type
     * @param reference
     *         the one automaton to consider
     * @param other
     *         the other automaton to consider
     * @param inputs
     *         the input symbols to consider
     *
     * @return a separating word, or {@code null} if no such word could be found.
     */
    public static <I> @Nullable Word<I> findSeparatingWord(UniversalDeterministicAutomaton<?, I, ?, ?, ?> reference,
                                                           UniversalDeterministicAutomaton<?, I, ?, ?, ?> other,
                                                           Collection<? extends I> inputs) {
        return NearLinearEquivalenceTest.findSeparatingWord(reference, other, inputs);
    }

    /**
     * Finds a separating word for two states in an automaton. A separating word is a word that exposes a difference
     * (differing state or transition properties, or a transition undefined in only one of the paths) between the two
     * states.
     *
     * @param <S>
     *         state type
     * @param <I>
     *         input symbol type
     * @param automaton
     *         the automaton containing the states
     * @param state1
     *         the one state
     * @param state2
     *         the other state
     * @param inputs
     *         the input symbols to consider
     *
     * @return a separating word, or {@code null} if no such word could be found
     */
    public static <S, I> @Nullable Word<I> findSeparatingWord(UniversalDeterministicAutomaton<S, I, ?, ?, ?> automaton,
                                                              S state1,
                                                              S state2,
                                                              Collection<? extends I> inputs) {
        return NearLinearEquivalenceTest.findSeparatingWord(automaton, state1, state2, inputs);
    }

    /**
     * Finds a shortest separating word for two automata. A separating word is a word that exposes a difference
     * (differing state or transition properties, or a transition undefined in only one of the automata) between the two
     * automata.
     *
     * @param <I>
     *         input symbol type
     * @param reference
     *         the one automaton to consider
     * @param other
     *         the other automaton to consider
     * @param inputs
     *         the input symbols to consider
     *
     * @return a separating word, or {@code null} if no such word could be found.
     */
    public static <I> @Nullable Word<I> findShortestSeparatingWord(UniversalDeterministicAutomaton<?, I, ?, ?, ?> reference,
                                                                   UniversalDeterministicAutomaton<?, I, ?, ?, ?> other,
                                                                   Collection<? extends I> inputs) {
        return DeterministicEquivalenceTest.findSeparatingWord(reference, other, inputs);
    }

    /**
     * Computes a characterizing set, and returns it as a {@link List}.
     *
     * @param <I>
     *         input symbol type
     * @param automaton
     *         the automaton for which to determine the characterizing set
     * @param inputs
     *         the input symbols to consider
     *
     * @return a list containing the characterizing words
     *
     * @see CharacterizingSets
     */
    public static <I> List<Word<I>> characterizingSet(UniversalDeterministicAutomaton<?, I, ?, ?, ?> automaton,
                                                      Collection<? extends I> inputs) {
        List<Word<I>> result = new ArrayList<>();
        characterizingSet(automaton, inputs, result);
        return result;
    }

    /**
     * Computes a characterizing set for the given automaton.
     * <p>
     * This is a convenience method acting as a shortcut to
     * {@link CharacterizingSets#findCharacterizingSet(UniversalDeterministicAutomaton, Collection, Collection)}.
     *
     * @param <I>
     *         input symbol type
     * @param automaton
     *         the automaton for which to determine the characterizing set
     * @param inputs
     *         the input symbols to consider
     * @param result
     *         the collection in which to store the characterizing words
     *
     * @see CharacterizingSets
     */
    public static <I> void characterizingSet(UniversalDeterministicAutomaton<?, I, ?, ?, ?> automaton,
                                             Collection<? extends I> inputs,
                                             Collection<? super Word<I>> result) {
        CharacterizingSets.findCharacterizingSet(automaton, inputs, result);
    }

    public static <I> boolean incrementalCharacterizingSet(UniversalDeterministicAutomaton<?, I, ?, ?, ?> automaton,
                                                           Collection<? extends I> inputs,
                                                           Collection<? extends Word<I>> oldSuffixes,
                                                           Collection<? super Word<I>> newSuffixes) {
        return CharacterizingSets.findIncrementalCharacterizingSet(automaton, inputs, oldSuffixes, newSuffixes);
    }

    /**
     * Computes a characterizing set for a single state, and returns it as a {@link List}.
     *
     * @param <S>
     *         state type
     * @param <I>
     *         input symbol type
     * @param automaton
     *         the automaton containing the state
     * @param inputs
     *         the input symbols to consider
     * @param state
     *         the state for which to determine a characterizing set
     *
     * @return a list containing the characterizing words
     *
     * @see CharacterizingSets
     */
    public static <S, I> List<Word<I>> stateCharacterizingSet(UniversalDeterministicAutomaton<S, I, ?, ?, ?> automaton,
                                                              Collection<? extends I> inputs,
                                                              S state) {
        List<Word<I>> result = new ArrayList<>();
        stateCharacterizingSet(automaton, inputs, state, result);
        return result;
    }

    /**
     * Computes a characterizing set for a single state.
     * <p>
     * This is a convenience method acting as a shortcut to
     * {@link CharacterizingSets#findCharacterizingSet(UniversalDeterministicAutomaton, Collection, Object,
     * Collection)}.
     *
     * @param <S>
     *         state type
     * @param <I>
     *         input symbol type
     * @param automaton
     *         the automaton containing the state
     * @param inputs
     *         the input symbols to consider
     * @param state
     *         the state for which to determine a characterizing set
     * @param result
     *         the collection in which to store the characterizing words
     *
     * @see CharacterizingSets
     */
    public static <S, I> void stateCharacterizingSet(UniversalDeterministicAutomaton<S, I, ?, ?, ?> automaton,
                                                     Collection<? extends I> inputs,
                                                     S state,
                                                     Collection<? super Word<I>> result) {
        CharacterizingSets.findCharacterizingSet(automaton, inputs, state, result);
    }

    /**
     * Convenient method for computing a state cover.
     *
     * @param automaton
     *         the automaton for which the cover should be computed
     * @param inputs
     *         the set of input symbols allowed in the cover sequences
     * @param <I>
     *         input symbol type
     *
     * @return the state cover for the given automaton
     *
     * @see Covers#stateCover(DeterministicAutomaton, Collection, Collection)
     */
    public static <I> List<Word<I>> stateCover(DeterministicAutomaton<?, I, ?> automaton,
                                               Collection<? extends I> inputs) {
        final List<Word<I>> result = new ArrayList<>(automaton.size());
        Covers.stateCover(automaton, inputs, result);
        return result;
    }

    /**
     * Convenient method for computing a state cover.
     *
     * @param automaton
     *         the automaton for which the cover should be computed
     * @param inputs
     *         the set of input symbols allowed in the cover sequences
     * @param <I>
     *         input symbol type
     *
     * @return the transition cover for the given automaton
     *
     * @see Covers#transitionCover(DeterministicAutomaton, Collection, Collection)
     */
    public static <I> List<Word<I>> transitionCover(DeterministicAutomaton<?, I, ?> automaton,
                                                    Collection<? extends I> inputs) {
        final List<Word<I>> result = new ArrayList<>(automaton.size() * inputs.size());
        Covers.transitionCover(automaton, inputs, result);
        return result;
    }

    /**
     * Convenient method for computing a structural cover.
     *
     * @param automaton
     *         the automaton for which the cover should be computed
     * @param inputs
     *         the set of input symbols allowed in the cover sequences
     * @param <I>
     *         input symbol type
     *
     * @return the structural cover for the given automaton
     *
     * @see Covers#structuralCover(DeterministicAutomaton, Collection, Collection)
     */
    public static <I> List<Word<I>> structuralCover(DeterministicAutomaton<?, I, ?> automaton,
                                                    Collection<? extends I> inputs) {
        final List<Word<I>> result = new ArrayList<>(automaton.size() * (inputs.size() + 1));
        Covers.structuralCover(automaton, inputs, result);
        return result;
    }

    public static <S, I> Iterator<TransRef<S, I, ?>> allDefinedInputsIterator(Automaton<S, I, ?> automaton,
                                                                              Iterable<? extends I> inputs) {
        return TS.allDefinedInputsIterator(automaton, automaton.iterator(), inputs);
    }

    public static <S, I> Iterable<TransRef<S, I, ?>> allDefinedInputs(Automaton<S, I, ?> automaton,
                                                                      Iterable<? extends I> inputs) {
        return TS.allDefinedInputs(automaton, automaton, inputs);
    }

    public static <S, I> Iterable<TransRef<S, I, ?>> allUndefinedInputs(Automaton<S, I, ?> automaton,
                                                                        Iterable<? extends I> inputs) {
        return TS.allUndefinedTransitions(automaton, automaton, inputs);
    }

    public static <I> boolean hasUndefinedInput(Automaton<?, I, ?> automaton, Iterable<? extends I> inputs) {
        return allUndefinedInputsIterator(automaton, inputs).hasNext();
    }

    public static <S, I> Iterator<TransRef<S, I, ?>> allUndefinedInputsIterator(Automaton<S, I, ?> automaton,
                                                                                Iterable<? extends I> inputs) {
        return TS.allUndefinedTransitionsIterator(automaton, automaton.iterator(), inputs);
    }

    private static final class ResultTransRecord<TP> {

        public final int targetId;
        public final TP property;

        ResultTransRecord(int targetId, TP property) {
            this.targetId = targetId;
            this.property = property;
        }
    }

    private static final class ResultStateRecord<SP, TP> {

        public final SP property;
        public final ResultTransRecord<TP>[] transitions;

        @SuppressWarnings("unchecked")
        ResultStateRecord(int numInputs, SP property) {
            this.property = property;
            this.transitions = new ResultTransRecord[numInputs];
        }
    }
}

1	/* Copyright (C) 2013-2025 TU Dortmund University
2	* This file is part of AutomataLib <https://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;
17
18	import java.util.ArrayList;
19	import java.util.Collection;
20	import java.util.Iterator;
21	import java.util.List;
22
23	import net.automatalib.automaton.Automaton;
24	import net.automatalib.automaton.DeterministicAutomaton;
25	import net.automatalib.automaton.MutableDeterministic;
26	import net.automatalib.automaton.UniversalDeterministicAutomaton;
27	import net.automatalib.automaton.graph.TransitionEdge;
28	import net.automatalib.common.util.array.ArrayStorage;
29	import net.automatalib.common.util.collection.CollectionUtil;
30	import net.automatalib.graph.Graph;
31	import net.automatalib.graph.UniversalGraph;
32	import net.automatalib.util.automaton.cover.Covers;
33	import net.automatalib.util.automaton.equivalence.CharacterizingSets;
34	import net.automatalib.util.automaton.equivalence.DeterministicEquivalenceTest;
35	import net.automatalib.util.automaton.equivalence.NearLinearEquivalenceTest;
36	import net.automatalib.util.automaton.minimizer.HopcroftMinimizer;
37	import net.automatalib.util.minimizer.Block;
38	import net.automatalib.util.minimizer.MinimizationResult;
39	import net.automatalib.util.minimizer.Minimizer;
40	import net.automatalib.util.ts.TS;
41	import net.automatalib.util.ts.TS.TransRef;
42	import net.automatalib.word.Word;
43	import org.checkerframework.checker.nullness.qual.Nullable;
44
45	public final class Automata {
46
47	private Automata() {
48	// prevent instantiation
49	}
50
51	public static <S, I, T> Graph<S, TransitionEdge<I, T>> asGraph(Automaton<S, I, T> automaton,
52	Collection<? extends I> inputs) {
53	return automaton.transitionGraphView(inputs);	×
54	}
55
56	/**
57	* Minimizes the given automaton. Internally, this method delegates to the
58	* {@link Minimizer Beal-Crochemore algorithm} which performs well especially for partial automata. If you have a
59	* total (or very dense) automaton, {@link HopcroftMinimizer} may provide better performance.
60	*
61	* @param automaton
62	* the automaton to minimize
63	* @param inputs
64	* the inputs to consider for minimization
65	* @param output
66	* the object to write the minimized automaton to
67	* @param <S>
68	* (input) state type
69	* @param <I>
70	* input symbol type
71	* @param <T>
72	* (input) transition type
73	* @param <SP>
74	* state property type
75	* @param <TP>
76	* transition property type
77	* @param <SO>
78	* (output) state type
79	* @param <TO>
80	* (output) transition type
81	* @param <A>
82	* explicit automaton type
83	*
84	* @return {@code output}, for convenience
85	*/
86	public static <S, I, T, SP, TP, SO, TO, A extends MutableDeterministic<SO, ? super I, TO, ? super SP, ? super TP>> A minimize(
87	UniversalDeterministicAutomaton<S, I, T, SP, TP> automaton,
88	Collection<? extends I> inputs,
89	A output) {
90
91	UniversalGraph<S, TransitionEdge<I, T>, SP, TransitionEdge.Property<I, TP>> aag =	2✔
92	automaton.transitionGraphView(inputs);	2✔
93
94	MinimizationResult<S, TransitionEdge.Property<I, TP>> mr =	2✔
95	Minimizer.minimize(aag, automaton.getInitialStates());	2✔
96	output.clear();	2✔
97
98	S init = automaton.getInitialState();	2✔
99	Block<S, TransitionEdge.Property<I, TP>> initBlock = init == null ? null : mr.getBlockForState(init);	2✔
100	ArrayStorage<SO> storage = new ArrayStorage<>(mr.getNumBlocks());	2✔
101
102	for (Block<S, TransitionEdge.Property<I, TP>> block : mr.getBlocks()) {	2✔
103	S rep = mr.getRepresentative(block);	2✔
104	SO state;
105	SP repProp = automaton.getStateProperty(rep);	2✔
106	if (block == initBlock) {	2✔
107	state = output.addInitialState(repProp);	2✔
108	} else {
109	state = output.addState(repProp);	2✔
110	}
111	storage.set(block.getId(), state);	2✔
112	}	2✔
113
114	for (Block<S, TransitionEdge.Property<I, TP>> block : mr.getBlocks()) {	2✔
115	S rep = mr.getRepresentative(block);	2✔
116	SO state = storage.get(block.getId());	2✔
117	for (I input : inputs) {	2✔
118	T trans = automaton.getTransition(rep, input);	2✔
119	if (trans != null) {	2✔
120	TP prop = automaton.getTransitionProperty(trans);	2✔
121	S oldSucc = automaton.getSuccessor(trans);	2✔
122	Block<S, TransitionEdge.Property<I, TP>> succBlock = mr.getBlockForState(oldSucc);	2✔
123	SO newSucc = storage.get(succBlock.getId());	2✔
124	output.addTransition(state, input, newSucc, prop);	2✔
125	}
126	}	2✔
127	}	2✔
128	return output;	2✔
129	}
130
131	/**
132	* Minimizes the given automaton in-place. Internally, this method delegates to the
133	* {@link Minimizer Beal-Crochemore algorithm} which performs well especially for partial automata. If you have a
134	* total automaton, {@link HopcroftMinimizer} may provide better performance.
135	*
136	* @param automaton
137	* the automaton to minimize
138	* @param inputs
139	* the inputs to consider for minimization
140	* @param <S>
141	* state type
142	* @param <I>
143	* input symbol type
144	* @param <T>
145	* transition type
146	* @param <SP>
147	* state property type
148	* @param <TP>
149	* transition property type
150	* @param <A>
151	* automaton type
152	*
153	* @return {@code automaton}, for convenience
154	*/
155	public static <S, I, T, SP, TP, A extends MutableDeterministic<S, I, T, SP, TP>> A invasiveMinimize(A automaton,
156	Collection<? extends I> inputs) {
157
158	final List<? extends I> inputList = CollectionUtil.randomAccessList(inputs);	2✔
159
160	int numInputs = inputs.size();	2✔
161
162	UniversalGraph<S, TransitionEdge<I, T>, SP, TransitionEdge.Property<I, TP>> aag =	2✔
163	automaton.transitionGraphView(inputs);	2✔
164
165	MinimizationResult<S, TransitionEdge.Property<I, TP>> mr =	2✔
166	Minimizer.minimize(aag, automaton.getInitialStates());	2✔
167
168	S init = automaton.getInitialState();	2✔
169	int initId = init == null ? -1 : mr.getBlockForState(init).getId();	2✔
170
171	@SuppressWarnings("unchecked")
172	ResultStateRecord<SP, TP>[] records = new ResultStateRecord[mr.getNumBlocks()];	2✔
173
174	// Store minimized automaton data in the records array
175	for (Block<S, TransitionEdge.Property<I, TP>> blk : mr.getBlocks()) {	2✔
176	int id = blk.getId();	2✔
177	S state = mr.getRepresentative(blk);	2✔
178	SP prop = automaton.getStateProperty(state);	2✔
179	ResultStateRecord<SP, TP> rec = new ResultStateRecord<>(numInputs, prop);	2✔
180	records[id] = rec;	2✔
181	for (int i = 0; i < numInputs; i++) {	2✔
182	I input = inputList.get(i);	2✔
183	T trans = automaton.getTransition(state, input);	2✔
184	if (trans == null) {	2✔
185	continue;	2✔
186	}
187
188	TP transProp = automaton.getTransitionProperty(trans);	2✔
189	S succ = automaton.getSuccessor(trans);	2✔
190	int tgtId = mr.getBlockForState(succ).getId();	2✔
191	rec.transitions[i] = new ResultTransRecord<>(tgtId, transProp);	2✔
192	}
193	}	2✔
194
195	automaton.clear();	2✔
196
197	// Add states from records
198	@Nullable Object[] states = new Object[records.length];	2✔
199	for (int i = 0; i < records.length; i++) {	2✔
200	ResultStateRecord<SP, TP> rec = records[i];	2✔
201	SP prop = rec.property;	2✔
202	S state;
203	if (i == initId) {	2✔
204	state = automaton.addInitialState(prop);	2✔
205	} else {
206	state = automaton.addState(prop);	2✔
207	}
208	states[i] = state;	2✔
209	}
210
211	// Add transitions from records
212	for (int i = 0; i < records.length; i++) {	2✔
213	ResultStateRecord<SP, TP> rec = records[i];	2✔
214	@SuppressWarnings("unchecked")
215	S state = (S) states[i];	2✔
216
217	for (int j = 0; j < numInputs; j++) {	2✔
218	ResultTransRecord<TP> transRec = rec.transitions[j];	2✔
219	if (transRec == null) {	2✔
220	continue;	2✔
221	}
222	@SuppressWarnings("unchecked")
223	S succ = (S) states[transRec.targetId];	2✔
224	I input = inputList.get(j);	2✔
225	automaton.addTransition(state, input, succ, transRec.property);	2✔
226	}
227	}
228	return automaton;	2✔
229	}
230
231	/**
232	* Tests whether two automata are equivalent, i.e. whether there exists a
233	* {@link #findSeparatingWord(UniversalDeterministicAutomaton, UniversalDeterministicAutomaton, Collection)
234	* separating word} for the two given automata.
235	*
236	* @param <I>
237	* input symbol type
238	* @param reference
239	* the one automaton to consider
240	* @param other
241	* the other automaton to consider
242	* @param inputs
243	* the input symbols to consider
244	*
245	* @return {@code true} if the automata are equivalent, {@code false} otherwise.
246	*
247	* @see #findSeparatingWord(UniversalDeterministicAutomaton, UniversalDeterministicAutomaton, Collection)
248	*/
249	public static <I> boolean testEquivalence(UniversalDeterministicAutomaton<?, I, ?, ?, ?> reference,
250	UniversalDeterministicAutomaton<?, I, ?, ?, ?> other,
251	Collection<? extends I> inputs) {
252	return findSeparatingWord(reference, other, inputs) == null;	2✔
253	}
254
255	/**
256	* Finds a separating word for two automata. A separating word is a word that exposes a difference (differing state
257	* or transition properties, or a transition undefined in only one of the automata) between the two automata.
258	*
259	* @param <I>
260	* input symbol type
261	* @param reference
262	* the one automaton to consider
263	* @param other
264	* the other automaton to consider
265	* @param inputs
266	* the input symbols to consider
267	*
268	* @return a separating word, or {@code null} if no such word could be found.
269	*/
270	public static <I> @Nullable Word<I> findSeparatingWord(UniversalDeterministicAutomaton<?, I, ?, ?, ?> reference,
271	UniversalDeterministicAutomaton<?, I, ?, ?, ?> other,
272	Collection<? extends I> inputs) {
273	return NearLinearEquivalenceTest.findSeparatingWord(reference, other, inputs);	2✔
274	}
275
276	/**
277	* Finds a separating word for two states in an automaton. A separating word is a word that exposes a difference
278	* (differing state or transition properties, or a transition undefined in only one of the paths) between the two
279	* states.
280	*
281	* @param <S>
282	* state type
283	* @param <I>
284	* input symbol type
285	* @param automaton
286	* the automaton containing the states
287	* @param state1
288	* the one state
289	* @param state2
290	* the other state
291	* @param inputs
292	* the input symbols to consider
293	*
294	* @return a separating word, or {@code null} if no such word could be found
295	*/
296	public static <S, I> @Nullable Word<I> findSeparatingWord(UniversalDeterministicAutomaton<S, I, ?, ?, ?> automaton,
297	S state1,
298	S state2,
299	Collection<? extends I> inputs) {
300	return NearLinearEquivalenceTest.findSeparatingWord(automaton, state1, state2, inputs);	2✔
301	}
302
303	/**
304	* Finds a shortest separating word for two automata. A separating word is a word that exposes a difference
305	* (differing state or transition properties, or a transition undefined in only one of the automata) between the two
306	* automata.
307	*
308	* @param <I>
309	* input symbol type
310	* @param reference
311	* the one automaton to consider
312	* @param other
313	* the other automaton to consider
314	* @param inputs
315	* the input symbols to consider
316	*
317	* @return a separating word, or {@code null} if no such word could be found.
318	*/
319	public static <I> @Nullable Word<I> findShortestSeparatingWord(UniversalDeterministicAutomaton<?, I, ?, ?, ?> reference,
320	UniversalDeterministicAutomaton<?, I, ?, ?, ?> other,
321	Collection<? extends I> inputs) {
322	return DeterministicEquivalenceTest.findSeparatingWord(reference, other, inputs);	1✔
323	}
324
325	/**
326	* Computes a characterizing set, and returns it as a {@link List}.
327	*
328	* @param <I>
329	* input symbol type
330	* @param automaton
331	* the automaton for which to determine the characterizing set
332	* @param inputs
333	* the input symbols to consider
334	*
335	* @return a list containing the characterizing words
336	*
337	* @see CharacterizingSets
338	*/
339	public static <I> List<Word<I>> characterizingSet(UniversalDeterministicAutomaton<?, I, ?, ?, ?> automaton,
340	Collection<? extends I> inputs) {
341	List<Word<I>> result = new ArrayList<>();	2✔
342	characterizingSet(automaton, inputs, result);	2✔
343	return result;	2✔
344	}
345
346	/**
347	* Computes a characterizing set for the given automaton.
348	* <p>
349	* This is a convenience method acting as a shortcut to
350	* {@link CharacterizingSets#findCharacterizingSet(UniversalDeterministicAutomaton, Collection, Collection)}.
351	*
352	* @param <I>
353	* input symbol type
354	* @param automaton
355	* the automaton for which to determine the characterizing set
356	* @param inputs
357	* the input symbols to consider
358	* @param result
359	* the collection in which to store the characterizing words
360	*
361	* @see CharacterizingSets
362	*/
363	public static <I> void characterizingSet(UniversalDeterministicAutomaton<?, I, ?, ?, ?> automaton,
364	Collection<? extends I> inputs,
365	Collection<? super Word<I>> result) {
366	CharacterizingSets.findCharacterizingSet(automaton, inputs, result);	2✔
367	}	2✔
368
369	public static <I> boolean incrementalCharacterizingSet(UniversalDeterministicAutomaton<?, I, ?, ?, ?> automaton,
370	Collection<? extends I> inputs,
371	Collection<? extends Word<I>> oldSuffixes,
372	Collection<? super Word<I>> newSuffixes) {
373	return CharacterizingSets.findIncrementalCharacterizingSet(automaton, inputs, oldSuffixes, newSuffixes);	2✔
374	}
375
376	/**
377	* Computes a characterizing set for a single state, and returns it as a {@link List}.
378	*
379	* @param <S>
380	* state type
381	* @param <I>
382	* input symbol type
383	* @param automaton
384	* the automaton containing the state
385	* @param inputs
386	* the input symbols to consider
387	* @param state
388	* the state for which to determine a characterizing set
389	*
390	* @return a list containing the characterizing words
391	*
392	* @see CharacterizingSets
393	*/
394	public static <S, I> List<Word<I>> stateCharacterizingSet(UniversalDeterministicAutomaton<S, I, ?, ?, ?> automaton,
395	Collection<? extends I> inputs,
396	S state) {
397	List<Word<I>> result = new ArrayList<>();	2✔
398	stateCharacterizingSet(automaton, inputs, state, result);	2✔
399	return result;	2✔
400	}
401
402	/**
403	* Computes a characterizing set for a single state.
404	* <p>
405	* This is a convenience method acting as a shortcut to
406	* {@link CharacterizingSets#findCharacterizingSet(UniversalDeterministicAutomaton, Collection, Object,
407	* Collection)}.
408	*
409	* @param <S>
410	* state type
411	* @param <I>
412	* input symbol type
413	* @param automaton
414	* the automaton containing the state
415	* @param inputs
416	* the input symbols to consider
417	* @param state
418	* the state for which to determine a characterizing set
419	* @param result
420	* the collection in which to store the characterizing words
421	*
422	* @see CharacterizingSets
423	*/
424	public static <S, I> void stateCharacterizingSet(UniversalDeterministicAutomaton<S, I, ?, ?, ?> automaton,
425	Collection<? extends I> inputs,
426	S state,
427	Collection<? super Word<I>> result) {
428	CharacterizingSets.findCharacterizingSet(automaton, inputs, state, result);	2✔
429	}	2✔
430
431	/**
432	* Convenient method for computing a state cover.
433	*
434	* @param automaton
435	* the automaton for which the cover should be computed
436	* @param inputs
437	* the set of input symbols allowed in the cover sequences
438	* @param <I>
439	* input symbol type
440	*
441	* @return the state cover for the given automaton
442	*
443	* @see Covers#stateCover(DeterministicAutomaton, Collection, Collection)
444	*/
445	public static <I> List<Word<I>> stateCover(DeterministicAutomaton<?, I, ?> automaton,
446	Collection<? extends I> inputs) {
447	final List<Word<I>> result = new ArrayList<>(automaton.size());	2✔
448	Covers.stateCover(automaton, inputs, result);	2✔
449	return result;	2✔
450	}
451
452	/**
453	* Convenient method for computing a state cover.
454	*
455	* @param automaton
456	* the automaton for which the cover should be computed
457	* @param inputs
458	* the set of input symbols allowed in the cover sequences
459	* @param <I>
460	* input symbol type
461	*
462	* @return the transition cover for the given automaton
463	*
464	* @see Covers#transitionCover(DeterministicAutomaton, Collection, Collection)
465	*/
466	public static <I> List<Word<I>> transitionCover(DeterministicAutomaton<?, I, ?> automaton,
467	Collection<? extends I> inputs) {
468	final List<Word<I>> result = new ArrayList<>(automaton.size() * inputs.size());	2✔
469	Covers.transitionCover(automaton, inputs, result);	2✔
470	return result;	2✔
471	}
472
473	/**
474	* Convenient method for computing a structural cover.
475	*
476	* @param automaton
477	* the automaton for which the cover should be computed
478	* @param inputs
479	* the set of input symbols allowed in the cover sequences
480	* @param <I>
481	* input symbol type
482	*
483	* @return the structural cover for the given automaton
484	*
485	* @see Covers#structuralCover(DeterministicAutomaton, Collection, Collection)
486	*/
487	public static <I> List<Word<I>> structuralCover(DeterministicAutomaton<?, I, ?> automaton,
488	Collection<? extends I> inputs) {
489	final List<Word<I>> result = new ArrayList<>(automaton.size() * (inputs.size() + 1));	×
490	Covers.structuralCover(automaton, inputs, result);	×
491	return result;	×
492	}
493
494	public static <S, I> Iterator<TransRef<S, I, ?>> allDefinedInputsIterator(Automaton<S, I, ?> automaton,
495	Iterable<? extends I> inputs) {
496	return TS.allDefinedInputsIterator(automaton, automaton.iterator(), inputs);	×
497	}
498
499	public static <S, I> Iterable<TransRef<S, I, ?>> allDefinedInputs(Automaton<S, I, ?> automaton,
500	Iterable<? extends I> inputs) {
501	return TS.allDefinedInputs(automaton, automaton, inputs);	2✔
502	}
503
504	public static <S, I> Iterable<TransRef<S, I, ?>> allUndefinedInputs(Automaton<S, I, ?> automaton,
505	Iterable<? extends I> inputs) {
506	return TS.allUndefinedTransitions(automaton, automaton, inputs);	2✔
507	}
508
509	public static <I> boolean hasUndefinedInput(Automaton<?, I, ?> automaton, Iterable<? extends I> inputs) {
510	return allUndefinedInputsIterator(automaton, inputs).hasNext();	2✔
511	}
512
513	public static <S, I> Iterator<TransRef<S, I, ?>> allUndefinedInputsIterator(Automaton<S, I, ?> automaton,
514	Iterable<? extends I> inputs) {
515	return TS.allUndefinedTransitionsIterator(automaton, automaton.iterator(), inputs);	2✔
516	}
517
518	private static final class ResultTransRecord<TP> {
519
520	public final int targetId;
521	public final TP property;
522
523	ResultTransRecord(int targetId, TP property) {	2✔
524	this.targetId = targetId;	2✔
525	this.property = property;	2✔
526	}	2✔
527	}
528
529	private static final class ResultStateRecord<SP, TP> {
530
531	public final SP property;
532	public final ResultTransRecord<TP>[] transitions;
533
534	@SuppressWarnings("unchecked")
535	ResultStateRecord(int numInputs, SP property) {	2✔
536	this.property = property;	2✔
537	this.transitions = new ResultTransRecord[numInputs];	2✔
538	}	2✔
539	}
540	}

LearnLib / automatalib / 13138848026

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