12304577693

Committed 12 Dec 2024 08:51PM UTC coverage: 91.182% (+0.4%) from 90.804%

Build # 12304577693

Build Type

push

github

Committed by

web-flow

Commit Message

Overhaul minimization code (#83)

* add valmaris algorithm

* initial PT refactoring

* implement bisimulation via valmari

* add documentation

* cleanups

* add invasive hopcroft methods

* some more universal tests

* performance tweaks

* move OneSEVPAMinimizer

* improve documentation

* cleanup

* wording

* fix javadoc errors

Run Details

564 of 581 new or added lines in 25 files covered. (97.07%)

1 existing line in 1 file now uncovered.

16535 of 18134 relevant lines covered (91.18%)

1.69 hits per line

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

94.44

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

import java.util.Collection;

import net.automatalib.automaton.transducer.MutableMealyMachine;
import net.automatalib.util.automaton.minimizer.HopcroftMinimizer;

public final class MutableMealyMachines {

    private MutableMealyMachines() {
        // prevent instantiation
    }

    public static <I, O> void complete(MutableMealyMachine<?, I, ?, O> mealy,
                                       Collection<? extends I> inputs,
                                       O undefinedOutput) {
        complete(mealy, inputs, undefinedOutput, false);
    }

    public static <S, I, O> void complete(MutableMealyMachine<S, I, ?, O> mealy,
                                          Collection<? extends I> inputs,
                                          O undefinedOutput,
                                          boolean minimize) {
        S sink = null;

        for (S state : mealy) {
            for (I input : inputs) {
                S succ = mealy.getSuccessor(state, input);
                if (succ == null) {
                    if (sink == null) {
                        sink = mealy.addState();
                        for (I inputSym : inputs) {
                            mealy.addTransition(sink, inputSym, sink, undefinedOutput);
                        }
                    }
                    mealy.addTransition(state, input, sink, undefinedOutput);
                }
            }
        }

        if (minimize) {
            HopcroftMinimizer.minimizeMealyInvasive(mealy, inputs);
        }
    }
}

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.transducer;
17
18	import java.util.Collection;
19
20	import net.automatalib.automaton.transducer.MutableMealyMachine;
21	import net.automatalib.util.automaton.minimizer.HopcroftMinimizer;
22
23	public final class MutableMealyMachines {
24
25	private MutableMealyMachines() {
26	// prevent instantiation
27	}
28
29	public static <I, O> void complete(MutableMealyMachine<?, I, ?, O> mealy,
30	Collection<? extends I> inputs,
31	O undefinedOutput) {
32	complete(mealy, inputs, undefinedOutput, false);	2✔
33	}	2✔
34
35	public static <S, I, O> void complete(MutableMealyMachine<S, I, ?, O> mealy,
36	Collection<? extends I> inputs,
37	O undefinedOutput,
38	boolean minimize) {
39	S sink = null;	2✔
40
41	for (S state : mealy) {	2✔
42	for (I input : inputs) {	2✔
43	S succ = mealy.getSuccessor(state, input);	2✔
44	if (succ == null) {	2✔
45	if (sink == null) {	2✔
46	sink = mealy.addState();	2✔
47	for (I inputSym : inputs) {	2✔
48	mealy.addTransition(sink, inputSym, sink, undefinedOutput);	2✔
49	}	2✔
50	}
51	mealy.addTransition(state, input, sink, undefinedOutput);	2✔
52	}
53	}	2✔
54	}	2✔
55
56	if (minimize) {	2✔
NEW 57	HopcroftMinimizer.minimizeMealyInvasive(mealy, inputs);	×
58	}
59	}	2✔
60	}

LearnLib / automatalib / 12304577693

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