Minimizer.minimize overload without start states is broken

[dhendriks]

Using this code:

import java.io.IOException;

import net.automatalib.automata.fsa.impl.FastDFA;
import net.automatalib.automata.fsa.impl.FastDFAState;
import net.automatalib.serialization.dot.GraphDOT;
import net.automatalib.util.minimizer.MinimizationResult;
import net.automatalib.util.minimizer.Minimizer;
import net.automatalib.words.impl.GrowingMapAlphabet;

public class MinimizerTest {
	public static void main(String[] args) throws IOException {
		GrowingMapAlphabet<String> alphabet = new GrowingMapAlphabet<>();
		alphabet.add("a");
		alphabet.add("b");
		FastDFA<String> dfa = new FastDFA<>(alphabet);
		dfa.addInitialState(false);
		FastDFAState stateAfterA = dfa.addState(true);
		FastDFAState stateAfterB = dfa.addState(true);
		dfa.setTransition(dfa.getInitialState(), "a", stateAfterA);
		dfa.setTransition(dfa.getInitialState(), "b", stateAfterB);

		StringBuilder b = new StringBuilder();
		GraphDOT.write(dfa, dfa.getInputAlphabet(), b);
		System.out.println(b.toString());

		MinimizationResult<FastDFAState, ?> rslt = Minimizer.minimize(dfa.transitionGraphView());
		System.out.println(rslt.getNumBlocks());
	}
}

Prints:

digraph g {

	s0 [shape="circle" label="s0"];
	s1 [shape="doublecircle" label="s1"];
	s2 [shape="doublecircle" label="s2"];
	s0 -> s1 [label="a"];
	s0 -> s2 [label="b"];

__start0 [label="" shape="none" width="0" height="0"];
__start0 -> s0;

}

0

Obviously 0 blocks is wrong.

net.automatalib.util.minimizer.Minimizer.minimize(UniversalGraph<S, ?, ?, L>) uses an empty list to as 2nd argument for net.automatalib.util.minimizer.Minimizer.minimize(UniversalGraph<S, ?, ?, L>, Collection<? extends S>), which invokes net.automatalib.util.minimizer.Minimizer.performMinimization(UniversalGraph<S, ?, ?, L>, Collection<? extends S>), which invokes net.automatalib.util.minimizer.Minimizer.initialize(UniversalGraph<S, E, ?, L>, Collection<? extends S>) which initializes with 0 blocks, meaning minimization will also result in 0 blocks.

net.automatalib.util.minimizer.Minimizer.performMinimization(UniversalGraph<S, E, ?, L>) seems to have a similar issue.

I used AutomataLib 0.9 distribution. AutomataLib 0.7.1 did not have this issue.

[dhendriks]

It seems it was broken by this commit: 74e6486#diff-b01e8a42b1004a4a3d265b7c50b88f6b

[mtf90]

Good catch. The null-safety refactoring introduced a wrong initialization of the default set of initial nodes. It should have been graph.getNodes() instead of Collections.emptyList().

For now, you can simply work-around this issue by invoking the overloaded version that takes the set of initial nodes explicitly, i.e.

MinimizationResult<FastDFAState, ?> rslt = Minimizer.minimize(
   dfa.transitionGraphView(),
   dfa.transitionGraphView().getNodes()
);