@Test
public void testComputeMostLikelySequence() {

    final List<Rain> candidates = new ArrayList<>();
    candidates.add(Rain.T);
    candidates.add(Rain.F);
    final Map<Rain, Double> emissionLogProbabilitiesForUmbrella = new LinkedHashMap<>();
    emissionLogProbabilitiesForUmbrella.put(Rain.T, log(0.9));
    emissionLogProbabilitiesForUmbrella.put(Rain.F, log(0.2));
    final Map<Rain, Double> emissionLogProbabilitiesForNoUmbrella = new LinkedHashMap<>();
    emissionLogProbabilitiesForNoUmbrella.put(Rain.T, log(0.1));
    emissionLogProbabilitiesForNoUmbrella.put(Rain.F, log(0.8));
    final Map<Transition<Rain>, Double> transitionLogProbabilities = new LinkedHashMap<>();
    transitionLogProbabilities.put(new Transition<Rain>(Rain.T, Rain.T), log(0.7));
    transitionLogProbabilities.put(new Transition<Rain>(Rain.T, Rain.F), log(0.3));
    transitionLogProbabilities.put(new Transition<Rain>(Rain.F, Rain.T), log(0.3));
    transitionLogProbabilities.put(new Transition<Rain>(Rain.F, Rain.F), log(0.7));
    final Map<Transition<Rain>, Descriptor> transitionDescriptors = new LinkedHashMap<>();
    transitionDescriptors.put(new Transition<Rain>(Rain.T, Rain.T), Descriptor.R2R);
    transitionDescriptors.put(new Transition<Rain>(Rain.T, Rain.F), Descriptor.R2S);
    transitionDescriptors.put(new Transition<Rain>(Rain.F, Rain.T), Descriptor.S2R);
    transitionDescriptors.put(new Transition<Rain>(Rain.F, Rain.F), Descriptor.S2S);
    final ViterbiAlgorithm<Rain, Umbrella, Descriptor> viterbi = new ViterbiAlgorithm<>(true);
    viterbi.startWithInitialObservation(Umbrella.T, candidates,
            emissionLogProbabilitiesForUmbrella);
    viterbi.nextStep(Umbrella.T, candidates, emissionLogProbabilitiesForUmbrella,
            transitionLogProbabilities, transitionDescriptors);
    viterbi.nextStep(Umbrella.F, candidates, emissionLogProbabilitiesForNoUmbrella,
            transitionLogProbabilities, transitionDescriptors);
    viterbi.nextStep(Umbrella.T, candidates, emissionLogProbabilitiesForUmbrella,
            transitionLogProbabilities, transitionDescriptors);
    final List<SequenceState<Rain, Umbrella, Descriptor>> result =
            viterbi.computeMostLikelySequence();
    // Check most likely sequence
    assertEquals(4, result.size());
    assertEquals(Rain.T, result.get(0).state);
    assertEquals(Rain.T, result.get(1).state);
    assertEquals(Rain.F, result.get(2).state);
    assertEquals(Rain.T, result.get(3).state);
    assertEquals(Umbrella.T, result.get(0).observation);
    assertEquals(Umbrella.T, result.get(1).observation);
    assertEquals(Umbrella.F, result.get(2).observation);
    assertEquals(Umbrella.T, result.get(3).observation);
    assertEquals(null,           result.get(0).transitionDescriptor);
    assertEquals(Descriptor.R2R, result.get(1).transitionDescriptor);
    assertEquals(Descriptor.R2S, result.get(2).transitionDescriptor);
    assertEquals(Descriptor.S2R, result.get(3).transitionDescriptor);
    // Check for HMM breaks
    assertFalse(viterbi.isBroken());
    // Check message history
    List<Map<Rain, Double>> expectedMessageHistory = new ArrayList<>();
    Map<Rain, Double> message = new LinkedHashMap<>();
    message.put(Rain.T, 0.9);
    message.put(Rain.F, 0.2);
    expectedMessageHistory.add(message);
    message = new LinkedHashMap<>();
    message.put(Rain.T, 0.567);
    message.put(Rain.F, 0.054);
    expectedMessageHistory.add(message);
    message = new LinkedHashMap<>();
    message.put(Rain.T, 0.03969);
    message.put(Rain.F, 0.13608);
    expectedMessageHistory.add(message);
    message = new LinkedHashMap<>();
    message.put(Rain.T, 0.0367416);
    message.put(Rain.F, 0.0190512);
    expectedMessageHistory.add(message);
    List<Map<Rain, Double>> actualMessageHistory = viterbi.messageHistory();
    checkMessageHistory(expectedMessageHistory, actualMessageHistory);
}