Index: branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/MatrixEntry.java =================================================================== --- branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/MatrixEntry.java (revision 1558) +++ branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/MatrixEntry.java (revision 1558) @@ -0,0 +1,27 @@ +package de.ugoe.cs.autoquest.tasktrees.alignment.algorithms; + +public class MatrixEntry { + private float score; + private MatrixEntry previous; + + public MatrixEntry(float score, MatrixEntry previous) { + this.score = score; + this.previous = previous; + } + + public MatrixEntry() { + } + + public float getScore() { + return score; + } + public void setScore(float score) { + this.score = score; + } + public MatrixEntry getPrevious() { + return previous; + } + public void setPrevious(MatrixEntry previous) { + this.previous = previous; + } +} Index: branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/NumberSequence.java =================================================================== --- branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/NumberSequence.java (revision 1557) +++ branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/NumberSequence.java (revision 1558) @@ -25,4 +25,12 @@ this.signature = signature; } + + public void printSequence() + { + for (int i = 0; i < sequence.length; i++) { + System.out.format("%4d", sequence[i]); + } + System.out.println(); + } } Index: branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/SmithWaterman.java =================================================================== --- branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/SmithWaterman.java (revision 1557) +++ branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/SmithWaterman.java (revision 1558) @@ -162,5 +162,5 @@ * Get the maximum value in the score matrix. */ - private double getMaxScore() { + public double getMaxScore() { double maxScore = 0; @@ -184,4 +184,6 @@ } + + /** * TODO: Iterative Version!!! Output the local alignments ending in the (i, @@ -272,5 +274,4 @@ } } - // Note: empty alignments are not printed. } Index: branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/SmithWatermanRepeated.java =================================================================== --- branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/SmithWatermanRepeated.java (revision 1558) +++ branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/SmithWatermanRepeated.java (revision 1558) @@ -0,0 +1,250 @@ +package de.ugoe.cs.autoquest.tasktrees.alignment.algorithms; + +import java.util.ArrayList; +import java.util.List; + +import de.ugoe.cs.autoquest.tasktrees.alignment.substitution.SubstitutionMatrix; + +public class SmithWatermanRepeated implements Alignment { + + /** + * The first input + */ + private int[] input1; + + /** + * The second input String + */ + private int[] input2; + + /** + * The lengths of the input + */ + private int length1, length2; + + /** + * The score matrix. The true scores should be divided by the normalization + * factor. + */ + private MatrixEntry[][] matrix; + + + + private float scoreThreshold; + + /** + * Substitution matrix to calculate scores + */ + private SubstitutionMatrix submat; + + public SmithWatermanRepeated(int[] input1, int[] input2, SubstitutionMatrix submat,float threshold) { + this.input1 = input1; + this.input2 = input2; + length1 = input1.length; + length2 = input2.length; + this.submat = submat; + + //System.out.println("Starting SmithWaterman algorithm with a " + // + submat.getClass() + " Substitution Matrix: " + submat.getClass().getCanonicalName()); + this.scoreThreshold = threshold; + + matrix = new MatrixEntry[length1+2][length2+1]; + + for (int i = 0; i <= length1; i++) { + for(int j = 0; j< length2; j++) { + matrix[i][j] = new MatrixEntry(); + } + } + + + buildMatrix(); + } + + /** + * Compute the similarity score of substitution The position of the first + * character is 1. A position of 0 represents a gap. + * + * @param i + * Position of the character in str1 + * @param j + * Position of the character in str2 + * @return Cost of substitution of the character in str1 by the one in str2 + */ + private float similarity(int i, int j) { + if (i == 0 || j == 0) { + // it's a gap + return submat.getGapPenalty(); + } + // System.out.println("Diag letters: " + input1[i-1] + " " + + // input2[j-1]); + // return (input1[i - 1] == input2[j - 1]) ? MATCH_SCORE : + // MISMATCH_SCORE; + return submat.getDistance(input1[i - 1], input2[j - 1]); + } + + /** + * Build the score matrix using dynamic programming. Note: The indel scores + * must be negative. Otherwise, the part handling the first row and column + * has to be modified. + */ + private void buildMatrix() { + if (submat.getGapPenalty() >= 0) { + throw new Error("Indel score must be negative"); + } + + + // base case + matrix[0][0].setScore(0); + matrix[0][0].setPrevious(null); // starting point + + // the first column + for (int j = 1; j < length2; j++) { + matrix[0][j].setScore(0); + matrix[0][j].setPrevious(matrix[0][j-1]); + + } + + + + for (int i = 1; i <= length1; i++) { + + // Formula for first row: + // F(i,0) = max { F(i-1,0), F(i-1,j)-T j=1,...,m + + float firstRowLeftScore = matrix[i-1][0].getScore(); + float tempMax = matrix[i-1][1].getScore(); + + //position of the maximal score of the previous row + int maxRowIndex = 1; + + for(int j = 2; j < length2;j++) { + if(matrix[i-1][j].getScore() > tempMax) { + tempMax = matrix[i-1][j].getScore(); + maxRowIndex = j; + } + } + + tempMax -= scoreThreshold; + matrix[i][0].setScore(Math.max(firstRowLeftScore, tempMax)); + + + for (int j = 1; j < length2; j++) { + float diagScore = matrix[i - 1][j - 1].getScore() + similarity(i, j); + float upScore = matrix[i][j - 1].getScore() + similarity(0, j); + float leftScore = matrix[i - 1][j].getScore() + similarity(i, 0); + + matrix[i][j].setScore(Math.max(diagScore,Math.max(upScore, Math.max(leftScore,matrix[i][0].getScore())))); + + // find the directions that give the maximum scores. + // Multiple directions are ignored TODO + if (diagScore == matrix[i][j].getScore()) { + matrix[i][j].setPrevious(matrix[i-1][j-1]); + } + if (leftScore == matrix[i][j].getScore()) { + matrix[i][j].setPrevious(matrix[i-1][j]); + } + if (upScore == matrix[i][j].getScore()) { + matrix[i][j].setPrevious(matrix[i][j-1]); + } + if (matrix[i][0].getScore() == matrix[i][j].getScore()) { + matrix[i][j].setPrevious(matrix[i-1][maxRowIndex]); + } + } + } + } + + /** + * Get the maximum value in the score matrix. + */ + public double getMaxScore() { + double maxScore = 0; + + // skip the first row and column + for (int i = 1; i <= length1; i++) { + for (int j = 1; j < length2; j++) { + if (matrix[i][j].getScore() > maxScore) { + maxScore = matrix[i][j].getScore(); + } + } + } + + return maxScore; + } + + /** + * Get the alignment score between the two input strings. + */ + public double getAlignmentScore() { + return getMaxScore(); + } + + + + + /** + * given the bottom right corner point trace back the top left conrner. at + * entry: i, j hold bottom right (end of Aligment coords) at return: hold + * top left (start of Alignment coords) + */ + private int[] traceback(int i, int j) { + + return null; + } + + + /** + * print the dynmaic programming matrix + */ + public void printDPMatrix() { + System.out.print(" "); + for (int i = 1; i <= length1; i++) + System.out.format("%5d", input1[i - 1]); + System.out.println(); + for (int j = 0; j < length2; j++) { + if (j > 0) + System.out.format("%5d ",input2[j - 1]); + else{ + System.out.print(" "); + } + for (int i = 0; i <= length1; i++) { + System.out.format("%4.1f ",matrix[i][j].getScore()); + } + System.out.println(); + } + } + + /** + * Return a set of Matches identified in Dynamic programming matrix. A match + * is a pair of subsequences whose score is higher than the preset + * scoreThreshold + **/ + public List getMatches() { + ArrayList matchList = new ArrayList(); + int fA = 0, fB = 0; + // skip the first row and column, find the next maxScore after + // prevmaxScore + for (int i = 1; i <= length1; i++) { + for (int j = 1; j <= length2; j++) { + if (matrix[i][j].getScore() > scoreThreshold + && matrix[i][j].getScore() > matrix[i - 1][j - 1].getScore() + && matrix[i][j].getScore() > matrix[i - 1][j].getScore() + && matrix[i][j].getScore() > matrix[i][j - 1].getScore()) { + if (i == length1 || j == length2 + || matrix[i][j].getScore() > matrix[i + 1][j + 1].getScore()) { + // should be lesser than prev maxScore + fA = i; + fB = j; + int[] f = traceback(fA, fB); // sets the x, y to + // startAlignment + // coordinates + System.out.println(f[0] + " " + i + " " + f[1] + " " + + j + " " + matrix[i][j].getScore()); + // TODO Add matches to matchList + } + } + } + } + return matchList; + } + +} Index: branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/substitution/ObjectDistanceSubstitionMatrix.java =================================================================== --- branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/substitution/ObjectDistanceSubstitionMatrix.java (revision 1557) +++ branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/substitution/ObjectDistanceSubstitionMatrix.java (revision 1558) @@ -30,11 +30,11 @@ public ObjectDistanceSubstitionMatrix( - SymbolMap uniqueTasks) { + SymbolMap uniqueTasks,float positiveThreshold) { this.uniqueTasks = uniqueTasks; + this.positiveThreshold = positiveThreshold; idmapping = new HashMap(); matrix = new TriangleMatrix(uniqueTasks.size()+1); gapPenalty = -10; - //Todo: Calculate this value (the mean distance between every element) before - positiveThreshold =7; + } @@ -47,5 +47,8 @@ public void generate() { int index = 0; - float meandistance = 0; + //TODO We need to determine this parameter before generating the matrix.. + float meandistance = 18; + //TODO We need to determine this parameter before generating the matrix.. + float maxDistance =34; for (Iterator it = uniqueTasks.getSymbols().iterator(); it .hasNext();) { @@ -87,15 +90,23 @@ tempindex2 = idmapping.get(eti2.getTask().getId()); } - float distance = AlignmentHelpers.distanceBetween(first, second); - meandistance += distance; + float distance = -1*AlignmentHelpers.distanceBetween(first, second); + //meandistance += distance; - if (distance > positiveThreshold) { - distance = -1*distance; + if(distance > maxDistance){ + maxDistance = distance; } + + distance += 5; + + //if (distance < positiveThreshold) { + // distance = -1*distance; + //} + matrix.set(tempindex1, tempindex2,distance); } } - System.out.println(meandistance/(uniqueTasks.size()*uniqueTasks.size())); + //System.out.println("ObjectDistanceMatrix: MaxDistance: " + maxDistance); + //System.out.println(meandistance/(uniqueTasks.size()*uniqueTasks.size())); //System.out.println(idmapping.toString()); //System.out.println(matrix.toString()); @@ -104,9 +115,12 @@ } + + public String toString(){ + return matrix.toString(); + } @Override public float getDistance(int taskId1, int taskId2) { //System.out.println("Taskid1: " + taskId1 + " Taskid2: " + taskId2 + " Idmapping1: " + idmapping.get(taskId1) + " Idmapping2: " + idmapping.get(taskId2)); - return matrix.get(idmapping.get(taskId1),idmapping.get(taskId2)); } Index: branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/substitution/TriangleMatrix.java =================================================================== --- branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/substitution/TriangleMatrix.java (revision 1557) +++ branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/substitution/TriangleMatrix.java (revision 1558) @@ -33,8 +33,8 @@ for(int j = 0; j< size; j++) { if(i uniqueTasks = harmonizeEventTaskInstancesModel(appData); - ObjectDistanceSubstitionMatrix submat = new ObjectDistanceSubstitionMatrix(uniqueTasks); + ObjectDistanceSubstitionMatrix submat = new ObjectDistanceSubstitionMatrix(uniqueTasks,20); submat.generate(); - - SmithWaterman sw = new SmithWaterman(numberseqs.get(1).getSequence(), numberseqs.get(1).getSequence(), submat); - + + + + System.out.print("Sequence 1: "); + NumberSequence ns1 = numberseqs.get(7); + NumberSequence ns2 = numberseqs.get(8); + ns1.printSequence(); + System.out.print("Sequence 2: "); + ns2.printSequence(); + //SmithWatermanRepeated sw = new SmithWatermanRepeated(numberseqs.get(20).getSequence(), numberseqs.get(24).getSequence(), submat,10); + SmithWatermanRepeated sw = new SmithWatermanRepeated(ns1.getSequence(), ns2.getSequence(), submat,15); + System.out.println("Max Scrore: " + sw.getMaxScore()); + + sw.printDPMatrix(); - - - - //Hier mein kram hin + do { System.out.println(); @@ -165,15 +173,15 @@ - appData.getStopWatch().start("whole loop"); - detectAndReplaceIterations(appData); - - appData.getStopWatch().start("task replacement"); - detectAndReplaceTasks(appData); - appData.getStopWatch().stop("task replacement"); - appData.getStopWatch().stop("whole loop"); - - - appData.getStopWatch().dumpStatistics(System.out); - appData.getStopWatch().reset(); + //appData.getStopWatch().start("whole loop"); + //detectAndReplaceIterations(appData); + + //appData.getStopWatch().start("task replacement"); + //detectAndReplaceTasks(appData); + //appData.getStopWatch().stop("task replacement"); + //appData.getStopWatch().stop("whole loop"); + + + //appData.getStopWatch().dumpStatistics(System.out); + //appData.getStopWatch().reset(); }