| 1 | package de.uka.ipd.sdq.reliability.solver; |
| 2 | |
| 3 | import org.apache.log4j.Logger; |
| 4 | |
| 5 | import de.uka.ipd.sdq.markov.MarkovChain; |
| 6 | import de.uka.ipd.sdq.markov.Transition; |
| 7 | |
| 8 | /** |
| 9 | * This class solves Markov Chains in the sense that it calculates the |
| 10 | * probability of getting from the Start State to the Success State (but not |
| 11 | * into the Failure State). |
| 12 | * |
| 13 | * @author brosch |
| 14 | * |
| 15 | */ |
| 16 | public class MarkovSolver { |
| 17 | |
| 18 | /** |
| 19 | * A logger to give detailed information about the PCM instance traversal. |
| 20 | */ |
| 21 | private static Logger logger = Logger.getLogger(MarkovSolver.class |
| 22 | .getName()); |
| 23 | |
| 24 | /** |
| 25 | * The static singleton instance. |
| 26 | */ |
| 27 | private static MarkovSolver singletonSolver; |
| 28 | |
| 29 | /** |
| 30 | * Retrieves the singleton solver instance. |
| 31 | * |
| 32 | * @return the singleton solver instance |
| 33 | */ |
| 34 | public static MarkovSolver getSingletonInstance() { |
| 35 | if (singletonSolver == null) { |
| 36 | singletonSolver = new MarkovSolver(); |
| 37 | } |
| 38 | return singletonSolver; |
| 39 | } |
| 40 | |
| 41 | /** |
| 42 | * Singleton instance - private constructor. |
| 43 | */ |
| 44 | private MarkovSolver() { |
| 45 | |
| 46 | } |
| 47 | |
| 48 | /** |
| 49 | * Calculates the probability for the given Markov Chain to reach the |
| 50 | * Success State starting from the Start State. |
| 51 | * |
| 52 | * @param markovChain |
| 53 | * the given Markov Chain |
| 54 | * @return the probability matrix |
| 55 | */ |
| 56 | public double[][] solve(MarkovChain markovChain) { |
| 57 | |
| 58 | // Do the logging: |
| 59 | logger.debug("Solving Markov Chain [" + markovChain.getName() + "]"); |
| 60 | |
| 61 | // Calculate the transition matrix: |
| 62 | double[][] transitionMatrix = new double[markovChain.getStates().size()][markovChain |
| 63 | .getStates().size()]; |
| 64 | |
| 65 | // Take over transition probabilities into the transition matrix: |
| 66 | for (int i = 0; i < markovChain.getTransitions().size(); i++) { |
| 67 | Transition transition = markovChain.getTransitions().get(i); |
| 68 | int index_from = markovChain.getStates().indexOf( |
| 69 | transition.getFromState()); |
| 70 | int index_to = markovChain.getStates().indexOf( |
| 71 | transition.getToState()); |
| 72 | transitionMatrix[index_from][index_to] = markovChain |
| 73 | .getTransitions().get(i).getProbability(); |
| 74 | } |
| 75 | |
| 76 | // Calculate (Identity Matrix - Transition Matrix): |
| 77 | for (int i = 0; i < transitionMatrix.length; i++) { |
| 78 | for (int j = 0; j < transitionMatrix[i].length; j++) { |
| 79 | transitionMatrix[i][j] = ((i == j) ? 1 : 0) |
| 80 | - transitionMatrix[i][j]; |
| 81 | } |
| 82 | } |
| 83 | |
| 84 | // Calculate the inverse matrix: |
| 85 | return Inverse.invert(transitionMatrix); |
| 86 | } |
| 87 | } |