findtheconcurrentevents.java

一个可以找到并发事件的算法。程序运用了闭包搜寻矩阵的算法。

/*
 * Assignment4
 * 作成日: 2008-11-7
 *
 */
package assignment4;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

import utils.FileUtil;

/**
 * @author Jianwei Yang(0801877)
 *
 */
public class FindTheConcurrentEvents {
    
    static final String keyOfVerticeCount = "VerticesCount";
    static final String significantValue = "1";

    public static void main(String[] args) {
        
        try {
            /* step.1 get the V[G] and E[G] from the input file */
            Map Edges = getContentsFromInputFile(args);
            
            /* step.2 use the algorithm of Transitive-Closure to find the matrices T(k) */
            int verticesCount = Integer.parseInt((String) Edges.get(keyOfVerticeCount));
            int [][][] T = new int[verticesCount + 1][verticesCount + 1][verticesCount + 1];
            
            for (int i = 1; i <= verticesCount; i++) {
                for (int j = 1; j <= verticesCount; j++) {
                    if (i == j || Edges.containsKey(i + "," + j)) {
                        T[0][i][j] = 1;
                    } else {
                        T[0][i][j] = 0;
                    }
                }
            }
            
            for (int k = 1; k <= verticesCount; k++){
                for (int i = 1; i <= verticesCount; i++) {
                    for (int j = 1; j <= verticesCount; j++) {
                        T[k][i][j] = T[k-1][i][j] | (T[k-1][i][k] & T[k-1][k][j]);
                    }
                }
            }
            
            /* step.3 find the pairs of unconnected edges by using the condition of tk[i][j] = tk[j][i] = 0 */
            int concurrentEventsCount = 0;
            
            for (int i = 1; i <= verticesCount; i++) {
                for (int j = 1; j <= verticesCount; j++) {
                    if (T[verticesCount][i][j] == 0 &&  T[verticesCount][j][i] == 0) {
                        concurrentEventsCount ++;
                    }
                }
            }
            concurrentEventsCount /= 2;
            
            System.out.println(concurrentEventsCount);
            
            System.exit(0);
        } catch (Exception e) {
            // catch the exception
            e.printStackTrace();
        }
    }
    
    private static Map getContentsFromInputFile(String[] args) throws Exception {
        
        Map Edges = new HashMap();
        Map Vertices = new HashMap();
        
        if (args.length < 1) {
            throw new RuntimeException("the parameter is not correct!");
        }
        
        List contentList;
        try {
            contentList = FileUtil.GetFileData(args[0]);
        } catch (Exception e) {
            throw(e);
        }
        
        int countSequentialEvents = Integer.parseInt((String) contentList.get(0));
        for (int i = 1; i < 1 + countSequentialEvents; i++) {
            String content = (String) contentList.get(i);
            String[] eventLinks = content.split(" ");
            for (int j = 1; j < eventLinks.length - 1; j++) {
                Edges.put(eventLinks[j] + "," + eventLinks[j+1], significantValue);
                Vertices.put(eventLinks[j], significantValue);
                Vertices.put(eventLinks[j+1], significantValue);
            }
        }
        
        int countMessageEvents = Integer.parseInt((String) contentList.get(countSequentialEvents + 1));
        for (int i = countSequentialEvents + 2; i < contentList.size(); i++) {
            String content = (String) contentList.get(i);
            String[] eventLinks = content.split(" ");
            for (int j = 0; j < eventLinks.length - 1; j++) {
                Edges.put(eventLinks[j] + "," + eventLinks[j+1], significantValue);
                Vertices.put(eventLinks[j], significantValue);
                Vertices.put(eventLinks[j+1], significantValue);
            }
        }
        
        Edges.put(keyOfVerticeCount, String.valueOf(Vertices.size()));
            
        return Edges;
    }
}