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

97.22

/util/src/main/java/net/automatalib/util/automaton/ads/ADSUtil.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.ads;

import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Set;
import java.util.function.BiFunction;
import java.util.function.Predicate;

import net.automatalib.automaton.transducer.MealyMachine;
import net.automatalib.common.util.Pair;
import net.automatalib.graph.ads.ADSNode;
import net.automatalib.graph.ads.RecursiveADSNode;
import net.automatalib.graph.ads.impl.ADSSymbolNode;
import net.automatalib.word.Word;
import net.automatalib.word.WordBuilder;
import org.checkerframework.checker.nullness.qual.Nullable;

/**
 * Utility class, that offers some operations revolving around adaptive distinguishing sequences.
 */
public final class ADSUtil {

    private ADSUtil() {}

    public static int computeLength(ADSNode<?, ?, ?> node) {
        if (node.isLeaf()) {
            return 0;
        }

        int max = 0;
        for (ADSNode<?, ?, ?> n : node.getChildren().values()) {
            max = Math.max(max, computeLength(n));
        }

        return 1 + max;
    }

    public static int countSymbolNodes(ADSNode<?, ?, ?> node) {
        if (node.isLeaf()) {
            return 0;
        }

        int result = 1;
        for (ADSNode<?, ?, ?> n : node.getChildren().values()) {
            result += countSymbolNodes(n);
        }
        return result;
    }

    public static <S, I, T, O> Pair<ADSNode<S, I, O>, ADSNode<S, I, O>> buildFromTrace(MealyMachine<S, I, T, O> automaton,
                                                                                       Word<I> trace,
                                                                                       S state) {
        return buildFromTrace(automaton, trace, state, ADSSymbolNode::new);
    }

    public static <S, I, T, O, N extends RecursiveADSNode<S, I, O, N>> Pair<N, N> buildFromTrace(MealyMachine<S, I, T, O> automaton,
                                                                                                 Word<I> trace,
                                                                                                 S state,
                                                                                                 BiFunction<@Nullable N, I, N> creator) {
        final Iterator<I> sequenceIter = trace.iterator();
        final I input = sequenceIter.next();
        final N head = creator.apply(null, input);

        N tempADS = head;
        I tempInput = input;
        S tempState = state;

        while (sequenceIter.hasNext()) {
            final I nextInput = sequenceIter.next();
            final N nextNode = creator.apply(tempADS, nextInput);

            final T trans = automaton.getTransition(tempState, tempInput);
            assert trans != null;
            final O oldOutput = automaton.getTransitionOutput(trans);

            tempADS.getChildren().put(oldOutput, nextNode);

            tempADS = nextNode;
            tempState = automaton.getSuccessor(trans);
            tempInput = nextInput;
        }

        return Pair.of(head, tempADS);
    }

    public static <S, I, O> Set<ADSNode<S, I, O>> collectLeaves(ADSNode<S, I, O> root) {
        final Set<ADSNode<S, I, O>> result = new LinkedHashSet<>();
        collectLeavesRecursively(result, root);
        return result;
    }

    private static <S, I, O> void collectLeavesRecursively(Set<ADSNode<S, I, O>> nodes, ADSNode<S, I, O> current) {
        if (current.isLeaf()) {
            nodes.add(current);
        } else {
            for (ADSNode<S, I, O> n : current.getChildren().values()) {
                collectLeavesRecursively(nodes, n);
            }
        }
    }

    public static <S, I, O> Pair<Word<I>, Word<O>> buildTraceForNode(ADSNode<S, I, O> node) {
        return buildTraceForNode(node, n -> true);
    }

    public static <S, I, O, N extends RecursiveADSNode<S, I, O, N>> Pair<Word<I>, Word<O>> buildTraceForNode(N node,
                                                                                                             Predicate<N> predicate) {
        N parentIter = node.getParent();
        N nodeIter = node;

        final WordBuilder<I> inputBuilder = new WordBuilder<>();
        final WordBuilder<O> outputBuilder = new WordBuilder<>();

        while (parentIter != null && predicate.test(parentIter)) {
            inputBuilder.append(parentIter.getSymbol());
            outputBuilder.append(getOutputForSuccessor(parentIter, nodeIter));

            nodeIter = parentIter;
            parentIter = parentIter.getParent();
        }

        return Pair.of(inputBuilder.reverse().toWord(), outputBuilder.reverse().toWord());
    }

    public static <O, N extends RecursiveADSNode<?, ?, O, N>> O getOutputForSuccessor(N node, N successor) {

        if (!node.equals(successor.getParent())) {
            throw new IllegalArgumentException("No parent relationship");
        }

        for (Map.Entry<O, N> entry : node.getChildren().entrySet()) {
            if (entry.getValue().equals(successor)) {
                return entry.getKey();
            }
        }

        throw new IllegalArgumentException("No child relationship");
    }

    /**
     * Computes an upper bound for the length of a splitting word. Based on
     * <p>
     * I.V. Kogan. "Estimated Length of a Minimal Simple Conditional Diagnostic Experiment". In: Automation and Remote
     * Control 34 (1973)
     *
     * @param n
     *         the size of the automaton (number of states)
     * @param i
     *         the number of states that should be distinguished by the current splitting word
     * @param m
     *         the number of states that should originally be distinguished
     *
     * @return upper bound for the length of a splitting word
     */
    public static long computeMaximumSplittingWordLength(int n, int i, int m) {
        if (m == 2) {
            return n;
        }

        return binomial(n, i) - binomial(m - 1, i - 1) + 1;
    }

    private static long binomial(int n, int k) {

        // abuse symmetry
        final int effectiveK = Math.min(k, n - k);
        long result = 1;

        try {
            for (int i = 1; i <= effectiveK; i++) {
                result = Math.multiplyExact(result, n + 1 - i);
                result /= i;
            }

            return result;
        } catch (ArithmeticException ae) {
            return Long.MAX_VALUE;
        }
    }

}

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.ads;
17
18	import java.util.Iterator;
19	import java.util.LinkedHashSet;
20	import java.util.Map;
21	import java.util.Set;
22	import java.util.function.BiFunction;
23	import java.util.function.Predicate;
24
25	import net.automatalib.automaton.transducer.MealyMachine;
26	import net.automatalib.common.util.Pair;
27	import net.automatalib.graph.ads.ADSNode;
28	import net.automatalib.graph.ads.RecursiveADSNode;
29	import net.automatalib.graph.ads.impl.ADSSymbolNode;
30	import net.automatalib.word.Word;
31	import net.automatalib.word.WordBuilder;
32	import org.checkerframework.checker.nullness.qual.Nullable;
33
34	/**
35	* Utility class, that offers some operations revolving around adaptive distinguishing sequences.
36	*/
37	public final class ADSUtil {	2✔
38
39	private ADSUtil() {}
40
41	public static int computeLength(ADSNode<?, ?, ?> node) {
42	if (node.isLeaf()) {	2✔
43	return 0;	2✔
44	}
45
46	int max = 0;	2✔
47	for (ADSNode<?, ?, ?> n : node.getChildren().values()) {	2✔
48	max = Math.max(max, computeLength(n));	2✔
49	}	2✔
50
51	return 1 + max;	2✔
52	}
53
54	public static int countSymbolNodes(ADSNode<?, ?, ?> node) {
55	if (node.isLeaf()) {	2✔
56	return 0;	2✔
57	}
58
59	int result = 1;	2✔
60	for (ADSNode<?, ?, ?> n : node.getChildren().values()) {	2✔
61	result += countSymbolNodes(n);	2✔
62	}	2✔
63	return result;	2✔
64	}
65
66	public static <S, I, T, O> Pair<ADSNode<S, I, O>, ADSNode<S, I, O>> buildFromTrace(MealyMachine<S, I, T, O> automaton,
67	Word<I> trace,
68	S state) {
69	return buildFromTrace(automaton, trace, state, ADSSymbolNode::new);	2✔
70	}
71
72	public static <S, I, T, O, N extends RecursiveADSNode<S, I, O, N>> Pair<N, N> buildFromTrace(MealyMachine<S, I, T, O> automaton,
73	Word<I> trace,
74	S state,
75	BiFunction<@Nullable N, I, N> creator) {
76	final Iterator<I> sequenceIter = trace.iterator();	2✔
77	final I input = sequenceIter.next();	2✔
78	final N head = creator.apply(null, input);	2✔
79
80	N tempADS = head;	2✔
81	I tempInput = input;	2✔
82	S tempState = state;	2✔
83
84	while (sequenceIter.hasNext()) {	2✔
85	final I nextInput = sequenceIter.next();	2✔
86	final N nextNode = creator.apply(tempADS, nextInput);	2✔
87
88	final T trans = automaton.getTransition(tempState, tempInput);	2✔
89	assert trans != null;	2✔
90	final O oldOutput = automaton.getTransitionOutput(trans);	2✔
91
92	tempADS.getChildren().put(oldOutput, nextNode);	2✔
93
94	tempADS = nextNode;	2✔
95	tempState = automaton.getSuccessor(trans);	2✔
96	tempInput = nextInput;	2✔
97	}	2✔
98
99	return Pair.of(head, tempADS);	2✔
100	}
101
102	public static <S, I, O> Set<ADSNode<S, I, O>> collectLeaves(ADSNode<S, I, O> root) {
103	final Set<ADSNode<S, I, O>> result = new LinkedHashSet<>();	2✔
104	collectLeavesRecursively(result, root);	2✔
105	return result;	2✔
106	}
107
108	private static <S, I, O> void collectLeavesRecursively(Set<ADSNode<S, I, O>> nodes, ADSNode<S, I, O> current) {
109	if (current.isLeaf()) {	2✔
110	nodes.add(current);	2✔
111	} else {
112	for (ADSNode<S, I, O> n : current.getChildren().values()) {	2✔
113	collectLeavesRecursively(nodes, n);	2✔
114	}	2✔
115	}
116	}	2✔
117
118	public static <S, I, O> Pair<Word<I>, Word<O>> buildTraceForNode(ADSNode<S, I, O> node) {
119	return buildTraceForNode(node, n -> true);	2✔
120	}
121
122	public static <S, I, O, N extends RecursiveADSNode<S, I, O, N>> Pair<Word<I>, Word<O>> buildTraceForNode(N node,
123	Predicate<N> predicate) {
124	N parentIter = node.getParent();	2✔
125	N nodeIter = node;	2✔
126
127	final WordBuilder<I> inputBuilder = new WordBuilder<>();	2✔
128	final WordBuilder<O> outputBuilder = new WordBuilder<>();	2✔
129
130	while (parentIter != null && predicate.test(parentIter)) {	2✔
131	inputBuilder.append(parentIter.getSymbol());	2✔
132	outputBuilder.append(getOutputForSuccessor(parentIter, nodeIter));	2✔
133
134	nodeIter = parentIter;	2✔
135	parentIter = parentIter.getParent();	2✔
136	}
137
138	return Pair.of(inputBuilder.reverse().toWord(), outputBuilder.reverse().toWord());	2✔
139	}
140
141	public static <O, N extends RecursiveADSNode<?, ?, O, N>> O getOutputForSuccessor(N node, N successor) {
142
143	if (!node.equals(successor.getParent())) {	2✔
144	throw new IllegalArgumentException("No parent relationship");	×
145	}
146
147	for (Map.Entry<O, N> entry : node.getChildren().entrySet()) {	2✔
148	if (entry.getValue().equals(successor)) {	2✔
149	return entry.getKey();	2✔
150	}
151	}	2✔
152
153	throw new IllegalArgumentException("No child relationship");	×
154	}
155
156	/**
157	* Computes an upper bound for the length of a splitting word. Based on
158	* <p>
159	* I.V. Kogan. "Estimated Length of a Minimal Simple Conditional Diagnostic Experiment". In: Automation and Remote
160	* Control 34 (1973)
161	*
162	* @param n
163	* the size of the automaton (number of states)
164	* @param i
165	* the number of states that should be distinguished by the current splitting word
166	* @param m
167	* the number of states that should originally be distinguished
168	*
169	* @return upper bound for the length of a splitting word
170	*/
171	public static long computeMaximumSplittingWordLength(int n, int i, int m) {
172	if (m == 2) {	2✔
173	return n;	2✔
174	}
175
176	return binomial(n, i) - binomial(m - 1, i - 1) + 1;	2✔
177	}
178
179	private static long binomial(int n, int k) {
180
181	// abuse symmetry
182	final int effectiveK = Math.min(k, n - k);	2✔
183	long result = 1;	2✔
184
185	try {
186	for (int i = 1; i <= effectiveK; i++) {	2✔
187	result = Math.multiplyExact(result, n + 1 - i);	2✔
188	result /= i;	2✔
189	}
190
191	return result;	2✔
192	} catch (ArithmeticException ae) {	2✔
193	return Long.MAX_VALUE;	2✔
194	}
195	}
196
197	}

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