6433387082

Committed 06 Oct 2023 03:10PM UTC coverage: 92.296% (-0.007%) from 92.303%

Build # 6433387082

Build Type

push

github

Committed by

mtf90

Commit Message

update Falk's developer id

Run Details

11573 of 12539 relevant lines covered (92.3%)

1.67 hits per line

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

92.19

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

/* Copyright (C) 2013-2023 TU Dortmund
 * This file is part of LearnLib, http://www.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.algorithms.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.SupportsGrowingAlphabet;
import net.automatalib.automata.DeterministicAutomaton;
import net.automatalib.automata.FiniteAlphabetAutomaton;
import net.automatalib.automata.fsa.DFA;
import net.automatalib.graphs.Graph;
import net.automatalib.visualization.DefaultVisualizationHelper;
import net.automatalib.visualization.VisualizationHelper;
import net.automatalib.words.Alphabet;
import net.automatalib.words.GrowingAlphabet;
import net.automatalib.words.impl.Alphabets;

/**
 * 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>,
                   DeterministicAutomaton.FullIntAbstraction<T>,
                   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 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 DeterministicAutomaton.FullIntAbstraction<T> fullIntAbstraction(Alphabet<I> alphabet) {
        if (alphabet == this.alphabet) {
            return this;
        }
        return DeterministicAutomaton.super.fullIntAbstraction(alphabet);
    }

    @Override
    public void addAlphabetSymbol(I symbol) {
        final GrowingAlphabet<I> growingAlphabet = Alphabets.toGrowingAlphabetOrThrowException(this.alphabet);

        if (!growingAlphabet.containsSymbol(symbol)) {
            growingAlphabet.addSymbol(symbol);
        }

        final int newAlphabetSize = growingAlphabet.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();
    }

    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<TTTState<I, D>, TTTEdge<I, D>>() {

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

LearnLib / learnlib / 6433387082

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