package de.ugoe.cs.quest.usageprofiles; import java.util.ArrayList; import java.util.Collection; import java.util.LinkedList; import java.util.List; import java.util.Random; import de.ugoe.cs.quest.eventcore.Event; import de.ugoe.cs.util.StringTools; import de.ugoe.cs.util.console.Console; import edu.uci.ics.jung.graph.Graph; import edu.uci.ics.jung.graph.SparseMultigraph; import edu.uci.ics.jung.graph.util.EdgeType; import Jama.Matrix; /** *
* Implements first-order Markov models. The implementation is based on * {@link HighOrderMarkovModel} and restricts the Markov order to 1. In * comparison to {@link HighOrderMarkovModel}, more calculations are possible * with first-order models, e.g., the calculation of the entropy ( * {@link #calcEntropy()}). *
* * @author Steffen Herbold * @version 1.0 */ public class FirstOrderMarkovModel extends HighOrderMarkovModel implements IDotCompatible { /** ** Id for object serialization. *
*/ private static final long serialVersionUID = 1L; /** ** Maximum number of iterations when calculating the stationary distribution * as the limit of multiplying the transmission matrix with itself. *
*/ final static int MAX_STATDIST_ITERATIONS = 1000; /** ** Constructor. Creates a new FirstOrderMarkovModel. *
* * @param r * random number generator used by probabilistic methods of the * class */ public FirstOrderMarkovModel(Random r) { super(1, r); } /** ** Generates the transmission matrix of the Markov model. *
* * @return transmission matrix */ private Matrix getTransmissionMatrix() { List* Calculates the entropy of the model. To make it possible that the model * is stationary, a transition from {@link Event#ENDEVENT} to * {@link Event#STARTEVENT} is added. *
* * @return entropy of the model or NaN if it could not be calculated */ public double calcEntropy() { Matrix transmissionMatrix = getTransmissionMatrix(); List* The dot represenation of {@link FirstOrderMarkovModel}s is its graph * representation with the states as nodes and directed edges weighted with * transition probabilities. *
* * @see de.ugoe.cs.quest.usageprofiles.IDotCompatible#getDotRepresentation() */ @Override public String getDotRepresentation() { StringBuilder stringBuilder = new StringBuilder(); stringBuilder.append("digraph model {" + StringTools.ENDLINE); List* Returns a {@link Graph} representation of the model with the states as * nodes and directed edges weighted with transition probabilities. *
* * @return {@link Graph} of the model */ public Graph* Weight of the edge, i.e., its transition probability. *
*/ double weight; /** ** Constructor. Creates a new MarkovEdge. *
* * @param weight * weight of the edge, i.e., its transition probability */ MarkovEdge(double weight) { this.weight = weight; } /** ** The weight of the edge as {@link String}. *
*/ public String toString() { return "" + weight; } } }