故障树算法JAVA实现

【排版出问题了，代码请点代码框上方的view plain查看】

对于图1这样一个故障树的最小割集的计算，我的思路是采用下行法和素数法：

图1 故障树示意图

所谓的下行法基本原理是故障树中的或门增加割集数目，与门增加割集的容量。从故障树的顶事件开始，由上到下，顺次把上一级事件置换为下一级事件，遇到与门就将输入事件横向并列写出，遇到或门就将输入事件竖向串联写出，直到把全部逻辑门都置换成底事件为止，此时最后一列代表所有割集，割集吸收得到最小割集采用素数法，其思想就是给每个底事件赋一素数，割集相除去掉能作为被除数的割集，从而得到最小割集。这部分实现起来比较容易，不做深入讲解。具体分析步骤如表1所示：

                         表1 最小割集分析步骤

以下是一些对于存储数据的一些定义，在一个实例中的运算过程【这是后来编辑的，之前看的朋友不好意思了】

【我就不明白了CSDN这编辑功能怎么这么烂】190-380行手动编辑的，还出问题，要疯了。。。

不想整了，直接上传了源码，链接【http://download.csdn.net/detail/conquerwave/5713163】注释乱码了，参考下文的源码

代码中使用的存储结构所对应的树结构：

<pre name="code" class="java">/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 * author: inmen.wang
 * mail: hugewave@yeah.net
 * build date: 2012.11.25
 * last edit: 2012.11.27
 */
package mytree;

/**
 *
 * @author Administrator
 */
public class MyTree {

    //private static int counter = 0;
    private static int subtree;        // 保存有多少个子树
    private static String[] label = new String[100];      // 对应该节点名称  
    private static int[][] treemap = new int[100][50];       // 保存树的对应关系
    private static int[][] subnode = new int[500][100];       // 保存所有割集，不去除重复，不用素数法去除
    private static int[][] middletable = new int[100][20];
    private static int middletable_n;
    private static int subnode_n;                                //记录相对应（subnode）割集数
    private static int [][] subnode_sole = new int[400][20];       // 保存所有割集，去除重复，不用素数法去除
    private static int subnode_sole_n;                                //记录相对应（subnode_sole）割集数
    private static int[][] subnode_result = new int[300][20];       // 保存所有割集，最张结果
    private static int subnode_result_n;                                //记录相对应（subnode_result）割集数
    private static int[][] subnode_ouput = new int [100][50];
    private static int subnode_output_n;
    private static int[] prime = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};
    
    
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        /*********************************************************************************************************
         * 示例数据
         * */
        int subt = 13;
        int[][] tree;
        tree = new int[][]{{2, -1, 1, 11},       // 0
                           {3, -2, 2, 3, 4},     // 1
                           {2, -1, 5, 6},        // 2
                           {2, -1, 7, 8},        // 3
                           {2, -1, 9, 10},       // 4
                           {0, 0},              // 5
                           {0, 0},              // 6
                           {0, 0},              // 7
                           {0, 0},              // 8
                           {0, 0},              // 9
                           {0, 0},              // 10
                           {2, -2, 12, 13},      // 11
                           {0, 0},              // 12
                           {0, 0}};             // 13
        String[] lab = new String[]{"T", "H2", "H4", "H5", "H6", "X7", "X2", "X7", "X3", "X2", "X3", "H3", "X4", "X5"};
        /*************************************the end 示例数据****************************************************/
        MyTree.getSubTree(subt);
        MyTree.getLabel(lab);
        MyTree.getTreeMap(tree);
            // 显示保存的故障树
            for(int i = 0; i <= subt; i ++)
            {
               for(int j = 0; j<=MyTree.treemap[i][0]+1; j++)
               {
                   System.out.print(MyTree.treemap[i][j]+" ");
               }
               System.out.println();
            }
            System.out.println("******************************");
            //calLayer();
            MyTree.getAllSubNode();
            buildupMiddleTable();
            MyTree.cutRepet();
            MyTree.getEnd();
        //System.out.println(subtree);
    }

    public static void getSubTree(int subt) {
        MyTree.subtree = subt;
    }
    
    public static void getLabel(String[] lab){
        for(int i = 0; i < lab.length; i ++)
        {
            MyTree.label[i] = lab[i];
        }
    }
    
    public static void getTreeMap(int[][] tree)
    {
        for (int i = 0; i < tree.length; i++) {
            for(int j = 0; j <= tree[i][0]+1; j ++)
            {
                MyTree.treemap[i][j] = tree[i][j];
            }
            
        }
    }
    private static void getAllSubNode(){
        MyTree.calculateAllSubNode(treemap[0]);
        printArray(subnode, subnode_n, 5);
    }

    /***********************************
     * 计算出所有最小割集并存入subnode[][]数组
     * */
    private static void calculateAllSubNode(int[] arr){
        int position = feedbackPosition(arr);
        int men_p = position+1;
        int new_position = position;
        int length = getMyArrayLength(arr);
        if(position == length)
        // 如果当前位置和数组长度相等，则说明数组中已经没有门记号
        {
            //printArray1V(arr, 0, length+1);     
            subnode[subnode_n][0] = length+1;
            MyTree.copyArray1V(arr, 0, length+1, subnode[subnode_n++], 1);
        }
        else if(arr[men_p]==-1)         // or
        {
            // 如果门记号为或门则需要对每个符号建立新的数组
            for(int i = men_p+1; i <= men_p +arr[position]; i ++)
            {
                int[] array = new int[100];
                MyTree.copyArray1V(arr, 0, position-1, array, 0);
                if(treemap[arr[i]][0] == 0)
                {
                    array[position] = arr[i];
                    new_position = position+1;
                }
                else
                {
                    MyTree.copyArray1V(treemap[arr[i]], 0, treemap[arr[i]][0]+2, array, position);
                    new_position =new_position+ (treemap[arr[i]][0]+2);
                }
                MyTree.copyArray1V(arr, position+arr[position]+2, length-position-arr[position]-2, array, new_position);
                calculateAllSubNode(array);
            }
        }
        else if(arr[men_p] == -2)
        {
            int[] array = new int[100];
            MyTree.copyArray1V(arr, 0, position-1, array, 0);
            for(int i = men_p +1; i <= men_p + arr[position]; i ++)
            {
                if (treemap[arr[i]][0] == 0) {
                    array[new_position] = arr[i];
                    new_position = position+1;
                }
                else
                {
                    MyTree.copyArray1V(treemap[arr[i]], 0, treemap[arr[i]][0]+2, array, new_position);
                    new_position += treemap[arr[i]][0]+2;
                }
            }
            MyTree.copyArray1V(arr, position+arr[position]+2, length-position-arr[position]-2, array, new_position);
            calculateAllSubNode(array);
        }
    }
    
    private static void buildupMiddleTable(){
        int[] temp = new int[label.length];
        for(int i = 1; i <= subtree; i ++)
        {
            if(treemap[i][0] == 0)          // 后续无节点，则判断此末节点是否需要存入middletable
            {
                // 
                if(temp[i] == 0)                   //检察名字是否已经存在于middletable中, 不存在则另起一行存入
                {
                    middletable[middletable_n][0] ++;
                    middletable[middletable_n][middletable[middletable_n][0]] = i;
                    temp[i] = 1;
                    for(int j = 0; j < subtree; j ++)      // 如果是本身则向后移一个单位
                    {
                        if(i == j)                  // 如果是本身则向后移一个单位
                        {
                            j++;
                        }
                        //int len = label.length;
                        if(j<subtree)          // 判断是否超出数组长度
                        {      
                                if(compareStr(label[i], label[j]) == 0 && temp[j] == 0)
                                {
                                    middletable[middletable_n][0] ++;
                                    middletable[middletable_n][middletable[middletable_n][0]] = j;
                                    //middletable_n++;
                                    temp[j] = 1;
                                }
                        }
                    }
                    middletable_n++;
                }
            }
        }
        // 添加素数和行号
        for(int i = 0; i < middletable_n; i ++)
        {
            middletable[i][middletable[i][0]+1] = prime[i];
            middletable[i][middletable[i][0]+2] = i;
        }
        printArray(middletable, middletable_n, 5);
    }
    /***************************************
     * 去除重复割集，并存入subnode_sole[][]数组
     * 
     * ************************************/
    private static void cutRepet(){
        // 利用middletable替换不同编号的相同项
        //int tempflag[][]  = new int[subnode_n][50];         // the number 50 maybe need changed
        for(int i = 0; i < subnode_n; i ++)
        {
            // 第0列直接拷贝过来
            subnode_sole[i][0] = subnode[i][0];
            for(int j = 1; j <= subnode[i][0]; j++)
            {
                int tempflag = 0;
                for(int k = 0; k <middletable_n;k++)
                {
                    // 判断当前编号是否是在buildtable中的第1列
                    if(subnode[i][j] == middletable[k][1])
                    // 在第1列则不用替换
                    {
                        tempflag = 1;
                    }
                }
                if(tempflag == 0)
                // 如果不是第1列则需要寻找存在于第几行中
                {
                    for(int m = 0; m < middletable_n; m ++)
                    {
                        for(int n = 2; n <= middletable[m][0]; n ++)
                        {
                            if(subnode[i][j] == middletable[m][n])
                            {
                                subnode_sole[i][j]= middletable[m][1];
                                 n = middletable[m][0];
                            }
                        }
                    }
                    
                }
                else
                // 如果不是第1列则需要替换
                {
                    subnode_sole[i][j] = subnode[i][j];
                }
            }
        }
        subnode_sole_n = subnode_n;
        //printArray(subnode_sole, subnode_sole_n, 5);
        // 消除一行中的重复项
        for(int i = 0 ; i < subnode_sole_n; i ++)
        {
            for (int j = 1; j < subnode_sole[i][0]; j++)
            {
                for(int k = j+1; k <= subnode_sole[i][0]; k ++)
                {
                    if(subnode_sole[i][j] == subnode_sole[i][k] && subnode_sole[i][k] != -1)
                    {
                        subnode_sole[i][k] = -1;
                    }
                }
            }
            for(int j = 1; j < subnode_sole[i][0]; j ++)
            {
                int k = j+1;
                if(subnode_sole[i][j] == -1)
                {
                    if(subnode_sole[i][k] != -1)
                    {
                        subnode_sole[i][j] = subnode_sole[i][k];
                        subnode_sole[i][k] = -1;
                        subnode_sole[i][0]--;
                    }
                    else
                    {
                        k++;
                    }
                    
                }
            }
            if(subnode_sole[i][subnode_sole[i][0]] == -1)
            {
                subnode_sole[i][0] --;
            }
        }
        //printArray(subnode_sole, subnode_sole_n, 5);
        // 行排序
        for(int i = 0; i < subnode_sole_n; i ++)
        {
            for(int j = 0; j < subnode_sole[i][0]; j++)
            {
                for(int k = 1; k < subnode_sole[i][0]; k ++)
                {
                    if(subnode_sole[i][k]>subnode_sole[i][k+1])
                    {
                        int temp= subnode_sole[i][k+1];
                        subnode_sole[i][k+1] = subnode_sole[i][k];
                        subnode_sole[i][k] = temp;
                    }
                }
            }
        }
        // 消除相同行
        for(int i = 0; i <subnode_sole_n-1; i ++)
        {
            for(int j = i+1; j < subnode_sole_n; j++)
            {
                int temp = compareArray(subnode_sole[i], subnode_sole[i][0], subnode_sole[j], subnode_sole[j][0]);
                if( temp == 0 && subnode_sole[i][0]!=0)
                {
                    subnode_sole[j][0] = 0;
                }
            }
        }
        for(int i = 0; i < subnode_sole_n; i ++)
        {
            if(subnode_sole[i][0]!=0)
            {
                for(int j = 0; j <= subnode_sole[i][0]; j++)
                {
                    subnode_result[subnode_result_n][j] =subnode_sole[i][j];
                }
                subnode_result_n++;
            }
        }
        //printArray(subnode_sole, subnode_sole_n, 5);
        printArray(subnode_result, subnode_result_n, 5);
    }
    
    /*******************************************
     * 用素数法，获得最终割集并存入subnode_result[][]数组
     * **************************************/
    private static void getEnd(){
        // 生成映射队列 防止编号过大，素数数量不够用
        int[] map= new int[200];
        int number = 0;
        for(int i = 0; i < subnode_result_n; i ++)
        {
            for(int j = 1; j <= subnode_result[i][0]; j++)
            {
                if(map[subnode_result[i][j]] ==0)
                {
                    map[subnode_result[i][j]] = number;
                    number++;
                }
            }
        }
        for(int i = 0; i < subnode_result_n; i ++)
        {
            int multi = 1;
            for(int j = 1; j <= subnode_result[i][0]; j ++)
            {
                multi *= prime[map[subnode_result[i][j]]];
            }
            subnode_result[i][subnode_result[i][0]+1] = multi;
        }
        // 消除能非最小时素数积项
        for(int i = 0; i < subnode_result_n-1; i ++)
        {
            for(int j = 0; j < subnode_result_n && i!=j; j ++)
            {
                int tt = subnode_result[i][subnode_result[i][0]+1]%subnode_result[j][subnode_result[j][0]+1];
                if(tt == 0 && subnode_result[j][0] !=0 )
                {
                    subnode_result[i][0] = 0;
                }
            }
        }
        printArray(subnode_result, subnode_result_n, 5);
        subnode_output_n = 0;
        for(int i = 0;i < subnode_result_n; i ++)
        {
            if(subnode_result[i][0] != 0)
            {
                for(int j = 0;j <= subnode_result[i][0]; j ++)
                {
                    subnode_output[subnode_output_n][j] = subnode_result[i][j];
                }
                subnode_output_n ++;
            }
        }
        printArray(subnode_ouput, subnode_output_n, 5);
    }
    

    
    private static void printArray(int[][] arr, int x, int y){
        for(int i = 0; i < x; i ++)
        {
            for(int j = 0; j < y; j ++)
            {
                System.out.print(arr[i][j]+" ");
            }
            System.out.println();
        }
        System.out.println("******************************");
    }

    /*
     * 从数组str1 sx1起拷备长度为len到str2 从sx2起
     */
    private static void copyArray1V(int[] str1, int sx1, int len, int[] str2, int sx2)
    {
            //for(int i = sx1; i <= sx1+len; i++)
            for(int i = 0; i <= len; i++)
            {
                str2[sx2+i] = str1[sx1+i];
            }
    }
  
    /*
     * example : array as 2 -1 1 11
     * return 3
     */
    private static int getMyArrayLength(int[] myarr){
        int i = 0;
        //while（myarr[i] != 0)
        while (myarr[i] != 0) {  
            i ++;
        }
        return i-1;    
    }
    /*
     * example: array as 2 -1 1 11
     * return 0
     *          array as 2 2 12 13
     * return 3
     * 位置定位为数组中第一个门记号位置前一位
     */
    private static int feedbackPosition(int[] arr){
        int i = 0;
        while (arr[i]>0 && arr[i]!= 0) {            
            i++;
        }
        return i-1;
    }
    private static String[] cutRepetName(String[] orig, int len){
        String[] temps = new String[orig.length];
        //temps[0] = orig[0];
        int k = 1;
        int length = len;
        for(int i = 1; i <= len; i ++)
        {
            String ss = orig[i];
            int sum = 0;
            for(int j = i+1; j <=len; j++)
            {
                if(ss.equals(orig[j])) {
                    //判断是否相同
                    sum++;
                }
            }
            if(sum==0)
            {
                temps[k] = orig[i];
                k ++;
            }
            else
            {
                length--;
            }
                
        }
        temps[0] = Integer.toString(length);
        return temps;
    }
    
    private static String[] sortStrings(String[] orig){
        String[] temp = orig;
        int start = 1;      // 第一个数据（即orig[0]）不进行排序
        String ss;
        int length = Integer.parseInt(orig[0]);
        for (int i = start; i < length; i++) {
            for (int j = start; j < length; j++) {
                int tt = compareStr(temp[j], temp[j+1]);
                if(tt == 1){
                    ss = temp[j];
                    temp[j] = temp[j+1];
                    temp[j+1] = ss;
                }
            }
        }
        return temp;
    }
    
    private static int compareStr(String str1, String str2){
        char[] ch1 = str1.toCharArray();
        char[] ch2 = str2.toCharArray();
        if(ch1.length>ch2.length)
        {
            return 1;
        }
        else if(ch1.length<ch2.length)
        {
            return 2;
        } 
        else
        {
            for(int i = 0; i <ch1.length; i ++)
            {
                if(ch1[i] > ch2[i]) {
                    return 1;
                }
                else if(ch1[i] < ch2[i]) {
                    return 2;
                }
                //return 0;       // 返回0是要出问题的，相同项已经被排除了
            }
        }
        return 0;
    }
    
    private static int compareArrayString(String[] str1, String[] str2){
        int len1 = Integer.parseInt(str1[0]);
        int len2 = Integer.parseInt(str2[0]);
        if(len1 != len2)
        {
            return 1;
        }
        else
        {
            int temp = 0;
            for(int i = 1; i < len1; i++)
            {
                
                if(str1[i].equals(str2[i]))
                {
                    temp ++;
                }
                else
                {
                    return 1;
                }
            }
            if(temp == (len1))
            {
                return 0;
            }
        }
        return 1;
    }
   
    /*
     * if same return 0
     * else return 1
     */
    private static int compareArray(int[] str1, int len1, int[] str2, int len2)
    {
        if(len1 != len2)
        {
            return 1;
        }
        else
        {
            for(int i = 0;i <= len1; i ++)
            {
                if(str1[i] != str2[i])
                {
                    return 1;
                }
            }
        }
        return 0;
    }
}