public double calculateCostForStringAVM(RegexGraph graph){
  final int ROWS=graph.getNumberOfRows();
  final int COLUMNS=graph.getNumberOfColumns();
  final double[][][] matrix=new double[ROWS][COLUMNS][3];
  calculateInsertionCostOnFirstRow(graph,matrix);
  for (int i=1; i < ROWS; i++) {
    for (int col=0; col < COLUMNS; col++) {
      matrix[i][col][DEL]=Double.MAX_VALUE;
      matrix[i][col][REP]=Double.MAX_VALUE;
      matrix[i][col][INS]=Double.MAX_VALUE;
      for (      GraphTransition t : graph.getIncomingTransitions(i,col)) {
        int otherCol=graph.getColumn(t.fromState);
        int otherRow=t.fromRow;
        if (t.type.equals(GraphTransition.TransitionType.INSERTION)) {
          assert otherRow == i;
          matrix[i][col][INS]=Math.min(matrix[i][col][INS],getSubPathCost(matrix[otherRow][otherCol][DEL],t.cost));
          matrix[i][col][INS]=Math.min(matrix[i][col][INS],getSubPathCost(matrix[otherRow][otherCol][REP],t.cost));
          matrix[i][col][INS]=Math.min(matrix[i][col][INS],getSubPathCost(matrix[otherRow][otherCol][INS],t.cost));
        }
 else         if (t.type.equals(GraphTransition.TransitionType.REPLACEMENT)) {
          matrix[i][col][REP]=Math.min(matrix[i][col][REP],getSubPathCost(matrix[otherRow][otherCol][DEL],t.cost));
          matrix[i][col][REP]=Math.min(matrix[i][col][REP],getSubPathCost(matrix[otherRow][otherCol][REP],t.cost));
          matrix[i][col][INS]=Math.min(matrix[i][col][INS],getSubPathCost(matrix[otherRow][otherCol][DEL],t.cost));
          matrix[i][col][INS]=Math.min(matrix[i][col][INS],getSubPathCost(matrix[otherRow][otherCol][REP],t.cost));
        }
 else         if (t.type.equals(GraphTransition.TransitionType.DELETION)) {
          matrix[i][col][DEL]=Math.min(matrix[i][col][DEL],getSubPathCost(matrix[otherRow][otherCol][DEL],t.cost));
          matrix[i][col][REP]=Math.min(matrix[i][col][REP],getSubPathCost(matrix[otherRow][otherCol][DEL],t.cost));
          matrix[i][col][INS]=Math.min(matrix[i][col][INS],getSubPathCost(matrix[otherRow][otherCol][DEL],t.cost));
        }
 else         if (t.type.equals(GraphTransition.TransitionType.PHANTOM)) {
          assert t.cost == 0;
          matrix[i][col][DEL]=Math.min(matrix[i][col][DEL],matrix[otherRow][otherCol][DEL]);
          matrix[i][col][REP]=Math.min(matrix[i][col][REP],matrix[otherRow][otherCol][REP]);
          matrix[i][col][INS]=Math.min(matrix[i][col][INS],matrix[otherRow][otherCol][INS]);
        }
      }
    }
  }
  double min=Double.MAX_VALUE;
  for (  double value : matrix[ROWS - 1][COLUMNS - 1]) {
    if (value < min) {
      min=value;
    }
  }
  return min;
}

public double calculateCostForStringAVM ( RegexGraph graph ) { final int ROWS = graph . getNumberOfRows ( ) ; final int COLUMNS = graph . getNumberOfColumns ( ) ; final double [ ] [ ] [ ] matrix = new double [ ROWS ] [ COLUMNS ] [ 3 ] ; calculateInsertionCostOnFirstRow ( graph , matrix ) ; for ( int i = 1 ; i < ROWS ; i ++ ) { for ( int col = 0 ; col < COLUMNS ; col ++ ) { matrix [ i ] [ col ] [ DEL ] = Double . MAX_VALUE ; matrix [ i ] [ col ] [ REP ] = Double . MAX_VALUE ; matrix [ i ] [ col ] [ INS ] = Double . MAX_VALUE ; for ( GraphTransition t : graph . getIncomingTransitions ( i , col ) ) { int otherCol = graph . getColumn ( t . fromState ) ; int otherRow = t . fromRow ; if ( t . type . equals ( GraphTransition . TransitionType . INSERTION ) ) { assert otherRow == i ; matrix [ i ] [ col ] [ INS ] = Math . min ( matrix [ i ] [ col ] [ INS ] , getSubPathCost ( matrix [ otherRow ] [ otherCol ] [ DEL ] , t . cost ) ) ; matrix [ i ] [ col ] [ INS ] = Math . min ( matrix [ i ] [ col ] [ INS ] , getSubPathCost ( matrix [ otherRow ] [ otherCol ] [ REP ] , t . cost ) ) ; matrix [ i ] [ col ] [ INS ] = Math . min ( matrix [ i ] [ col ] [ INS ] , getSubPathCost ( matrix [ otherRow ] [ otherCol ] [ INS ] , t . cost ) ) ; } else if ( t . type . equals ( GraphTransition . TransitionType . REPLACEMENT ) ) { matrix [ i ] [ col ] [ REP ] = Math . min ( matrix [ i ] [ col ] [ REP ] , getSubPathCost ( matrix [ otherRow ] [ otherCol ] [ DEL ] , t . cost ) ) ; matrix [ i ] [ col ] [ REP ] = Math . min ( matrix [ i ] [ col ] [ REP ] , getSubPathCost ( matrix [ otherRow ] [ otherCol ] [ REP ] , t . cost ) ) ; matrix [ i ] [ col ] [ INS ] = Math . min ( matrix [ i ] [ col ] [ INS ] , getSubPathCost ( matrix [ otherRow ] [ otherCol ] [ DEL ] , t . cost ) ) ; matrix [ i ] [ col ] [ INS ] = Math . min ( matrix [ i ] [ col ] [ INS ] , getSubPathCost ( matrix [ otherRow ] [ otherCol ] [ REP ] , t . cost ) ) ; } else if ( t . type . equals ( GraphTransition . TransitionType . DELETION ) ) { matrix [ i ] [ col ] [ DEL ] = Math . min ( matrix [ i ] [ col ] [ DEL ] , getSubPathCost ( matrix [ otherRow ] [ otherCol ] [ DEL ] , t . cost ) ) ; matrix [ i ] [ col ] [ REP ] = Math . min ( matrix [ i ] [ col ] [ REP ] , getSubPathCost ( matrix [ otherRow ] [ otherCol ] [ DEL ] , t . cost ) ) ; matrix [ i ] [ col ] [ INS ] = Math . min ( matrix [ i ] [ col ] [ INS ] , getSubPathCost ( matrix [ otherRow ] [ otherCol ] [ DEL ] , t . cost ) ) ; } else if ( t . type . equals ( GraphTransition . TransitionType . PHANTOM ) ) { assert t . cost == 0 ; matrix [ i ] [ col ] [ DEL ] = Math . min ( matrix [ i ] [ col ] [ DEL ] , matrix [ otherRow ] [ otherCol ] [ DEL ] ) ; matrix [ i ] [ col ] [ REP ] = Math . min ( matrix [ i ] [ col ] [ REP ] , matrix [ otherRow ] [ otherCol ] [ REP ] ) ; matrix [ i ] [ col ] [ INS ] = Math . min ( matrix [ i ] [ col ] [ INS ] , matrix [ otherRow ] [ otherCol ] [ INS ] ) ; } } } } double min = Double . MAX_VALUE ; for ( double value : matrix [ ROWS - 1 ] [ COLUMNS - 1 ] ) { if ( value < min ) { min = value ; } } return min ; }
note : this is different from normal matching algorithms , as we enforce an order among the operators : delete , replace and then insert .
