31619759710

Committed 12 Aug 2026 04:27PM UTC coverage: 95.488% (+1.1%) from 94.368%

Build # 31619759710

Build Type

push

github

Committed by

mtf90

Commit Message

use new version scheme

Coverage Stats

15533 of 16267 relevant lines covered (95.49%)

1.72 hits per line

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

92.65

/algorithms/active/ttt/src/main/java/de/learnlib/algorithm/ttt/base/AbstractTTTHypothesis.java

/* Copyright (C) 2013-2026 TU Dortmund University
 * This file is part of LearnLib <https://learnlib.de>.
 *
 * 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 de.learnlib.algorithm.ttt.base;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
import java.util.Map;

import net.automatalib.alphabet.Alphabet;
import net.automatalib.alphabet.SupportsGrowingAlphabet;
import net.automatalib.automaton.DeterministicAutomaton;
import net.automatalib.automaton.FiniteAlphabetAutomaton;
import net.automatalib.automaton.abstraction.DeterministicAbstractions.FullIntAbstraction;
import net.automatalib.automaton.concept.StateIDs;
import net.automatalib.automaton.fsa.DFA;
import net.automatalib.graph.Graph;
import net.automatalib.visualization.DefaultVisualizationHelper;
import net.automatalib.visualization.VisualizationHelper;
import org.checkerframework.checker.nullness.qual.Nullable;

/**
 * Hypothesis DFA for the {@link AbstractTTTLearner TTT algorithm}.
 *
 * @param <S>
 *         state class type
 * @param <I>
 *         input symbol type
 * @param <D>
 *         output domain type
 * @param <T>
 *         transition type
 */
public abstract class AbstractTTTHypothesis<S extends TTTState<I, D>, I, D, T>
        implements DeterministicAutomaton<S, I, T>,
                   FiniteAlphabetAutomaton<S, I, T>,
                   FullIntAbstraction<T>,
                   StateIDs<S>,
                   SupportsGrowingAlphabet<I> {

    protected final List<S> states = new ArrayList<>();

    private final Alphabet<I> alphabet;
    private int alphabetSize;

    private S initialState;

    /**
     * Constructor.
     *
     * @param alphabet
     *         the input alphabet
     */
    public AbstractTTTHypothesis(Alphabet<I> alphabet) {
        this.alphabet = alphabet;
        this.alphabetSize = this.alphabet.size();
    }

    @Override
    public S getInitialState() {
        return initialState;
    }

    @Override
    public T getTransition(int stateId, int symIdx) {
        S state = states.get(stateId);
        TTTTransition<I, D> trans = getInternalTransition(state, symIdx);
        return mapTransition(trans);
    }

    @Override
    public @Nullable T getTransition(S state, I input) {
        TTTTransition<I, D> trans = getInternalTransition(state, input);
        return trans == null ? null : mapTransition(trans);
    }

    /**
     * Retrieves the <i>internal</i> transition (i.e., the {@link TTTTransition} object) for a given state and input.
     * This method is required since the {@link DFA} interface requires the return value of
     * {@link #getTransition(TTTState, Object)} to refer to the successor state directly.
     *
     * @param state
     *         the source state
     * @param input
     *         the input symbol triggering the transition
     *
     * @return the transition object
     */
    public TTTTransition<I, D> getInternalTransition(TTTState<I, D> state, I input) {
        int inputIdx = alphabet.getSymbolIndex(input);
        return getInternalTransition(state, inputIdx);
    }

    public TTTTransition<I, D> getInternalTransition(TTTState<I, D> state, int input) {
        return state.getTransition(input);
    }

    protected abstract T mapTransition(TTTTransition<I, D> internalTransition);

    /**
     * Initializes the automaton, adding an initial state. Whether the initial state is accepting needs to be known at
     * this point.
     *
     * @return the initial state of this newly initialized automaton
     */
    public S initialize() {
        assert !isInitialized();

        initialState = createState(null);
        return initialState;
    }

    /**
     * Checks whether this automaton was initialized (i.e., {@link #initialize()} has been called).
     *
     * @return {@code true} if this automaton was initialized, {@code false} otherwise.
     */
    public boolean isInitialized() {
        return initialState != null;
    }

    public S createState(TTTTransition<I, D> parent) {
        S state = newState(alphabet.size(), parent, states.size());
        states.add(state);
        if (parent != null) {
            parent.makeTree(state);
        }
        return state;
    }

    protected abstract S newState(int alphabetSize, TTTTransition<I, D> parent, int id);

    @Override
    public Alphabet<I> getInputAlphabet() {
        return alphabet;
    }

    @Override
    public GraphView graphView() {
        return new GraphView();
    }

    @Override
    public int getIntInitialState() {
        return 0;
    }

    @Override
    public int numInputs() {
        return alphabet.size();
    }

    @Override
    public int getIntSuccessor(T trans) {
        return getSuccessor(trans).id;
    }

    @Override
    public FullIntAbstraction<T> fullIntAbstraction(Alphabet<I> alphabet) {
        if (alphabet == this.alphabet) {
            return this;
        }
        return DeterministicAutomaton.super.fullIntAbstraction(alphabet);
    }

    @Override
    public void addAlphabetSymbol(I symbol) {
        if (!this.alphabet.containsSymbol(symbol)) {
            this.alphabet.asGrowingAlphabetOrThrowException().addSymbol(symbol);
        }

        final int newAlphabetSize = this.alphabet.size();

        if (alphabetSize < newAlphabetSize) {
            for (TTTState<I, D> s : this.getStates()) {
                s.ensureInputCapacity(newAlphabetSize);
            }

            alphabetSize = newAlphabetSize;
        }
    }

    @Override
    public Collection<S> getStates() {
        return Collections.unmodifiableList(states);
    }

    @Override
    public int size() {
        return states.size();
    }

    @Override
    public int getStateId(S state) {
        return state.id;
    }

    @Override
    public S getState(int id) {
        return this.states.get(id);
    }

    @Override
    public StateIDs<S> stateIDs() {
        return this;
    }

    public static final class TTTEdge<I, D> {

        public final TTTTransition<I, D> transition;
        public final TTTState<I, D> target;

        public TTTEdge(TTTTransition<I, D> transition, TTTState<I, D> target) {
            this.transition = transition;
            this.target = target;
        }
    }

    public class GraphView implements Graph<TTTState<I, D>, TTTEdge<I, D>> {

        @Override
        public Collection<TTTState<I, D>> getNodes() {
            return Collections.unmodifiableList(states);
        }

        @Override
        public Collection<TTTEdge<I, D>> getOutgoingEdges(TTTState<I, D> node) {
            List<TTTEdge<I, D>> result = new ArrayList<>();
            for (TTTTransition<I, D> trans : node.getTransitions()) {
                for (TTTState<I, D> target : trans.getDTTarget().subtreeStates()) {
                    result.add(new TTTEdge<>(trans, target));
                }
            }
            return result;
        }

        @Override
        public TTTState<I, D> getTarget(TTTEdge<I, D> edge) {
            return edge.target;
        }

        @Override
        public VisualizationHelper<TTTState<I, D>, TTTEdge<I, D>> getVisualizationHelper() {
            return new DefaultVisualizationHelper<>() {

                @Override
                public boolean getEdgeProperties(TTTState<I, D> src,
                                                 TTTEdge<I, D> edge,
                                                 TTTState<I, D> tgt,
                                                 Map<String, String> properties) {
                    super.getEdgeProperties(src, edge, tgt, properties);

                    properties.put(EdgeAttrs.LABEL, String.valueOf(edge.transition.getInput()));
                    if (edge.transition.isTree()) {
                        properties.put(EdgeAttrs.STYLE, EdgeStyles.BOLD);
                    } else if (edge.transition.getDTTarget().isInner()) {
                        properties.put(EdgeAttrs.STYLE, EdgeStyles.DOTTED);
                    }

                    return true;
                }
            };
        }
    }
}

1	/* Copyright (C) 2013-2026 TU Dortmund University
2	* This file is part of LearnLib <https://learnlib.de>.
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 de.learnlib.algorithm.ttt.base;
17
18	import java.util.ArrayList;
19	import java.util.Collection;
20	import java.util.Collections;
21	import java.util.List;
22	import java.util.Map;
23
24	import net.automatalib.alphabet.Alphabet;
25	import net.automatalib.alphabet.SupportsGrowingAlphabet;
26	import net.automatalib.automaton.DeterministicAutomaton;
27	import net.automatalib.automaton.FiniteAlphabetAutomaton;
28	import net.automatalib.automaton.abstraction.DeterministicAbstractions.FullIntAbstraction;
29	import net.automatalib.automaton.concept.StateIDs;
30	import net.automatalib.automaton.fsa.DFA;
31	import net.automatalib.graph.Graph;
32	import net.automatalib.visualization.DefaultVisualizationHelper;
33	import net.automatalib.visualization.VisualizationHelper;
34	import org.checkerframework.checker.nullness.qual.Nullable;
35
36	/**
37	* Hypothesis DFA for the {@link AbstractTTTLearner TTT algorithm}.
38	*
39	* @param <S>
40	* state class type
41	* @param <I>
42	* input symbol type
43	* @param <D>
44	* output domain type
45	* @param <T>
46	* transition type
47	*/
48	public abstract class AbstractTTTHypothesis<S extends TTTState<I, D>, I, D, T>	2✔
49	implements DeterministicAutomaton<S, I, T>,
50	FiniteAlphabetAutomaton<S, I, T>,
51	FullIntAbstraction<T>,
52	StateIDs<S>,
53	SupportsGrowingAlphabet<I> {
54
55	protected final List<S> states = new ArrayList<>();	2✔
56
57	private final Alphabet<I> alphabet;
58	private int alphabetSize;
59
60	private S initialState;
61
62	/**
63	* Constructor.
64	*
65	* @param alphabet
66	* the input alphabet
67	*/
68	public AbstractTTTHypothesis(Alphabet<I> alphabet) {	2✔
69	this.alphabet = alphabet;	2✔
70	this.alphabetSize = this.alphabet.size();	2✔
71	}	2✔
72
73	@Override
74	public S getInitialState() {
75	return initialState;	2✔
76	}
77
78	@Override
79	public T getTransition(int stateId, int symIdx) {
80	S state = states.get(stateId);	2✔
81	TTTTransition<I, D> trans = getInternalTransition(state, symIdx);	2✔
82	return mapTransition(trans);	2✔
83	}
84
85	@Override
86	public @Nullable T getTransition(S state, I input) {
87	TTTTransition<I, D> trans = getInternalTransition(state, input);	2✔
88	return trans == null ? null : mapTransition(trans);	2✔
89	}
90
91	/**
92	* Retrieves the <i>internal</i> transition (i.e., the {@link TTTTransition} object) for a given state and input.
93	* This method is required since the {@link DFA} interface requires the return value of
94	* {@link #getTransition(TTTState, Object)} to refer to the successor state directly.
95	*
96	* @param state
97	* the source state
98	* @param input
99	* the input symbol triggering the transition
100	*
101	* @return the transition object
102	*/
103	public TTTTransition<I, D> getInternalTransition(TTTState<I, D> state, I input) {
104	int inputIdx = alphabet.getSymbolIndex(input);	2✔
105	return getInternalTransition(state, inputIdx);	2✔
106	}
107
108	public TTTTransition<I, D> getInternalTransition(TTTState<I, D> state, int input) {
109	return state.getTransition(input);	2✔
110	}
111
112	protected abstract T mapTransition(TTTTransition<I, D> internalTransition);
113
114	/**
115	* Initializes the automaton, adding an initial state. Whether the initial state is accepting needs to be known at
116	* this point.
117	*
118	* @return the initial state of this newly initialized automaton
119	*/
120	public S initialize() {
121	assert !isInitialized();	2✔
122
123	initialState = createState(null);	2✔
124	return initialState;	2✔
125	}
126
127	/**
128	* Checks whether this automaton was initialized (i.e., {@link #initialize()} has been called).
129	*
130	* @return {@code true} if this automaton was initialized, {@code false} otherwise.
131	*/
132	public boolean isInitialized() {
133	return initialState != null;	2✔
134	}
135
136	public S createState(TTTTransition<I, D> parent) {
137	S state = newState(alphabet.size(), parent, states.size());	2✔
138	states.add(state);	2✔
139	if (parent != null) {	2✔
140	parent.makeTree(state);	2✔
141	}
142	return state;	2✔
143	}
144
145	protected abstract S newState(int alphabetSize, TTTTransition<I, D> parent, int id);
146
147	@Override
148	public Alphabet<I> getInputAlphabet() {
149	return alphabet;	2✔
150	}
151
152	@Override
153	public GraphView graphView() {
154	return new GraphView();	2✔
155	}
156
157	@Override
158	public int getIntInitialState() {
159	return 0;	2✔
160	}
161
162	@Override
163	public int numInputs() {
164	return alphabet.size();	2✔
165	}
166
167	@Override
168	public int getIntSuccessor(T trans) {
169	return getSuccessor(trans).id;	2✔
170	}
171
172	@Override
173	public FullIntAbstraction<T> fullIntAbstraction(Alphabet<I> alphabet) {
174	if (alphabet == this.alphabet) {	×
175	return this;	×
176	}
177	return DeterministicAutomaton.super.fullIntAbstraction(alphabet);	×
178	}
179
180	@Override
181	public void addAlphabetSymbol(I symbol) {
182	if (!this.alphabet.containsSymbol(symbol)) {	2✔
183	this.alphabet.asGrowingAlphabetOrThrowException().addSymbol(symbol);	×
184	}
185
186	final int newAlphabetSize = this.alphabet.size();	2✔
187
188	if (alphabetSize < newAlphabetSize) {	2✔
189	for (TTTState<I, D> s : this.getStates()) {	2✔
190	s.ensureInputCapacity(newAlphabetSize);	2✔
191	}	2✔
192
193	alphabetSize = newAlphabetSize;	2✔
194	}
195	}	2✔
196
197	@Override
198	public Collection<S> getStates() {
199	return Collections.unmodifiableList(states);	2✔
200	}
201
202	@Override
203	public int size() {
204	return states.size();	2✔
205	}
206
207	@Override
208	public int getStateId(S state) {
209	return state.id;	2✔
210	}
211
212	@Override
213	public S getState(int id) {
214	return this.states.get(id);	1✔
215	}
216
217	@Override
218	public StateIDs<S> stateIDs() {
219	return this;	2✔
220	}
221
222	public static final class TTTEdge<I, D> {
223
224	public final TTTTransition<I, D> transition;
225	public final TTTState<I, D> target;
226
227	public TTTEdge(TTTTransition<I, D> transition, TTTState<I, D> target) {	2✔
228	this.transition = transition;	2✔
229	this.target = target;	2✔
230	}	2✔
231	}
232
233	public class GraphView implements Graph<TTTState<I, D>, TTTEdge<I, D>> {	2✔
234
235	@Override
236	public Collection<TTTState<I, D>> getNodes() {
237	return Collections.unmodifiableList(states);	2✔
238	}
239
240	@Override
241	public Collection<TTTEdge<I, D>> getOutgoingEdges(TTTState<I, D> node) {
242	List<TTTEdge<I, D>> result = new ArrayList<>();	2✔
243	for (TTTTransition<I, D> trans : node.getTransitions()) {	2✔
244	for (TTTState<I, D> target : trans.getDTTarget().subtreeStates()) {	2✔
245	result.add(new TTTEdge<>(trans, target));	2✔
246	}	2✔
247	}	2✔
248	return result;	2✔
249	}
250
251	@Override
252	public TTTState<I, D> getTarget(TTTEdge<I, D> edge) {
253	return edge.target;	2✔
254	}
255
256	@Override
257	public VisualizationHelper<TTTState<I, D>, TTTEdge<I, D>> getVisualizationHelper() {
258	return new DefaultVisualizationHelper<>() {	2✔
259
260	@Override
261	public boolean getEdgeProperties(TTTState<I, D> src,
262	TTTEdge<I, D> edge,
263	TTTState<I, D> tgt,
264	Map<String, String> properties) {
265	super.getEdgeProperties(src, edge, tgt, properties);	2✔
266
267	properties.put(EdgeAttrs.LABEL, String.valueOf(edge.transition.getInput()));	2✔
268	if (edge.transition.isTree()) {	2✔
269	properties.put(EdgeAttrs.STYLE, EdgeStyles.BOLD);	2✔
270	} else if (edge.transition.getDTTarget().isInner()) {	2✔
271	properties.put(EdgeAttrs.STYLE, EdgeStyles.DOTTED);	×
272	}
273
274	return true;	2✔
275	}
276	};
277	}
278	}
279	}

LearnLib / learnlib / 31619759710

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