数学问题，通过矩阵求关系闭包。

用Warkshallde 算法实现求关系的传递闭包。谢谢了

两种方法分别求传递闭包，全部自己实现，没有用到JAVA提供的类

package relations;

public class Main {
public static void main(String args[]){
long time1_star = System.currentTimeMillis();

System.out.println("--- R1∪R2∪R3∪....Rn --- ");
new Relations();
System.out.println();
long time1_end = System.currentTimeMillis();
System.out.println("耗时:"+String.valueOf(time1_end-time1_star)+"毫秒");

long time2_star = System.currentTimeMillis();
System.out.println("--- Warkshallde --- ");
new Warkshallde();
System.out.println();
long time2_end = System.currentTimeMillis();
System.out.println("耗时:"+String.valueOf(time2_end-time2_star)+"毫秒");

}
}

package relations;

public class BiList{
private Object[] data=new Object[3];
private int index=0;
private void expand(){
Object[] data2=new Object[data.length*2];
System.arraycopy(data,0,data2,0,data.length);
data=data2;
}
public void add(Object o){
if (data.length==index) expand();
data[index]=o;
index++;
}
public void add(int pos,Object o){
if (data.length==index) expand();
for(int i=index;i>pos;i--){
data[i]=data[i-1];
}
data[pos]=o;
index++;
}
public Object remove(int pos){
Object o=data[pos];
index--;
for(int i=pos;i<index;i++){
data[i]=data[i+1];
}
return o;
}
public int size(){
return index;
}
public Object get(int pos){
return data[pos];
}
public void clear(){
index=0;
}
public boolean isEmpty(){
return index==0;
}
public Object[] toArray(){
return data;
}
}

package relations;

public class Binary {
private String one;
private String two;
public Binary(){}
public Binary(String one,String two){
this.one = one;
this.two = two;
}
public String getOne() {
return one;
}
public void setOne(String one) {
this.one = one;
}
public String getTwo() {
return two;
}
public void setTwo(String two) {
this.two = two;
}

}

package relations;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;

public class Relations { //二元关系
private static BiList A = new BiList();
private static BiList R = new BiList();
private static int n=0;

public Relations(){
BiList copy = new BiList();
readInput();
for(int i=0 ; i<R.size(); i++){
Binary b=(Binary)R.get(i);
copy.add(new Binary(b.getOne(),b.getTwo()));
}
System.out.print("t(R)={");
operate(copy);
System.out.print("}");
}

public static void initA(String s,int line){
if(line==1){
String type=s.replace(" ","").replace("{", "").replace("}","");
String[] a = type.substring(2,type.length()).split(",");
for(String a1:a){
A.add(new Binary(a1,a1));
}
n=A.size();

}
}

public static void initR(String s,int line){
if(line==2){
String type=s.replace(" ","").replace("}", "").replace("<", "").replace(",", "");
String[] a = type.substring(3,type.length()).split(">");

for(String a1:a){
R.add(new Binary(a1.substring(0,1),a1.substring(1,2)));
}

System.out.print("R={");
for(int i=0 ; i Binary b=(Binary)R.get(i);
System.out.print("");
}
System.out.println("}");
}
}

private static BiList operate(BiList list){
BiList type1 = new BiList();
if(n==0){
for(int i=0; i<R.size(); i++){
Binary r=(Binary)R.get(i);
list.add(new Binary(r.getOne(),r.getTwo()));
}
print(list);
return list;
}

for(int i=0; i<list.size(); i++){
Binary r=(Binary)list.get(i);
type1.add(new Binary(r.getOne(),r.getTwo()));
}
list.clear();
for(int i=0; i<R.size();i++){
for(int j=0; j<type1.size(); j++){
Binary r=(Binary)R.get(i);
Binary r1=(Binary)type1.get(j);
if(r.getTwo().equals(r1.getOne())){
list.add(new Binary(r.getOne(),r1.getTwo()));
}
}
}
print(list);
for(int i=0; i<list.size();i++){
for(int j=0; j<list.size(); j++){
Binary r=(Binary)list.get(i);
Binary r1=(Binary)list.get(j);
if(r.getOne().endsWith(r1.getOne())&&r.getTwo().equals(r1.getTwo())){
list.remove(j);
}
}
}
for(int i=0; i<list.size();i++){
for(int j=0; j<list.size(); j++){
Binary r=(Binary)list.get(i);
Binary r1=(Binary)list.get(j);
if(r.getOne().endsWith(r1.getOne())&&r.getTwo().equals(r1.getTwo())){
list.remove(j);
}
}
}
n--;
return operate(list);
}

public static void print(BiList<?> li){

for(int i=0 ; i

Binary b=(Binary)li.get(i);
System.out.print("");
}

}

public static void readInput(){
try{
BufferedReader br = new BufferedReader(
new FileReader("d:\input.txt"));
String line="";
int i=0;
while((line=br.readLine()) !=null){
i++;
initA(line,i);
initR(line,i);
}
} catch(FileNotFoundException e){
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
}

public static void main(String args[]){
new Relations();
}

}

package relations;

public class Util {
public static int praseToDigit(String s){
if(s.equals("a")){
return 1-1;
}
if(s.equals("b")){
return 2-1;
}
if(s.equals("c")){
return 3-1;
}
if(s.equals("d")){
return 4-1;
}
if(s.equals("e")){
return 5-1;
}
return -1;
}
public static String praseToABC(int i){
if(i==0){
return "a";
}
if(i==1){
return "b";
}
if(i==2){
return "c";
}
if(i==3){
return "d";
}
if(i==4){
return "e";
}
return null;
}
}

package relations;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;

public class Warkshallde { // Warkshallde算法
private static BiList A = new BiList();
private static BiList R = new BiList();
private static int[][] matrix;
public Warkshallde(){
readInput();
matrixOperation();
System.out.print("t(R)={");
for(int i=0; i for(int j=0; j if(matrix[i][j]==1){
System.out.print("");
}
}
}
System.out.print("}");
}

public static void initA(String s,int line){
if(line==1) {
String type=s.replace(" ","").replace("{", "").replace("}","");
String[] a = type.substring(2,type.length()).split(",");
for(String a1:a){
A.add(new Binary(a1,a1));
}
matrix = new int[A.size()][A.size()];
}
}

public static void initR(String s,int line){
if(line==2){
String type=s.replace(" ","").replace("}", "").replace("<", "").replace(",", "");
String[] a = type.substring(3,type.length()).split(">");
for(String a1:a){
R.add(new Binary(a1.substring(0,1),a1.substring(1,2)));
int row = Util.praseToDigit(a1.substring(0,1));
int col = Util.praseToDigit(a1.substring(1,2));
matrix[row][col]=1;
}
}
}

public static void print(BiList<?> list){
System.out.print("A={");
for(int i=0 ; i Binary b=(Binary)list.get(i);
System.out.print("");
}
System.out.println("}");
}

public static void matrixOperation(){
for(int i=0; i<matrix.length-1;i++){
for(int j=0; j<matrix[i].length-1; j++){
if(matrix[j][i]==1){
operate(i,j);
}
}
}
for(int i1=0; i1<matrix.length;i1++){
for(int j=0; j<matrix[i1].length; j++){
System.out.print(matrix[i1][j]+" ");
}
System.out.println();
}
}

public static void operate(int index,int add ){
int i=matrix.length-1;
while(i>=0){
if(matrix[index][i]==matrix[add][i]&& matrix[index][i]==0){
matrix[add][i]=0;
}
matrix[add][i]=1;
i--;
}
}

public static void readInput(){
try{
BufferedReader br = new BufferedReader(
new FileReader("d:\input.txt"));
String line="";
int i=0;
while((line=br.readLine()) !=null){
i++;
initA(line,i);
initR(line,i);
}
} catch(FileNotFoundException e){
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
}

public static void main(String args[]){
new Warkshallde();
}

}

以文件的形式读取集合及集合上的关系：
文件格式如下:input.txt
code="java"]A={a,b,c,d}
R={,,,,}[[/code]
程序如下，显示结果有两种形式：控制台打印和输出文件
[code="java"]
package study;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;

/**

• 测试Warshall算法生成关系闭包

• @author mrcio_s
  */
  public class TestClosure {

  private static final String fileName = "d:\input.txt";//读取文件地址
  private static final String outputFileName = "d:\output.txt";//写入文件地址
  private static final String separator = ";";//分隔符
  private static final int CLFS_JH = 0;//处理方式-集合
  private static final int CLFS_GX = 1;//处理方式-关系

  /**

  • 测试Warshall算法生成关系闭包
  • @author mrcio_s
  • @param args */ public static void main(String[] args) { // 定义开始时间 long start = System.currentTimeMillis(); // 定义打印字符串 StringBuffer sb = new StringBuffer(); // 读取集合关系txt文件 String str = readText(fileName); sb.append("\n读取到的集合及集合上的关系为："); sb.append("\n" + str); // 得到集合上的元素 String[] element = (String[]) dealStr(str, CLFS_JH); // 得到集合上的关系 String[][] relation = (String[][]) dealStr(str, CLFS_GX); // 将关系转换为矩阵 int[][] M = conversionMatrix(relation, element); sb.append("\n初始化关系矩阵为："); sb.append("\n" + display(M, element.length)); // 得到传递闭包 M = genClosure(M, element.length); // 打印传递闭包 sb.append("\n生成关系闭包矩阵为："); sb.append("\n" + display(M, element.length)); // 将闭包矩阵转换为关系 String returnStr = conversionRelations(M,element); // 得到要写入的文件 sb.append("\n闭包关系为："); sb.append("\n" + returnStr); // 写入文件 writeText(sb.toString(),outputFileName); // 定义结束时间 long end = System.currentTimeMillis(); sb.append("\n执行时间为:" + (end-start) + "毫秒"); // 打印文件 System.out.println(sb.toString()); }

  /**

  • 读取txt文件
  • @param fileName
  • @return */ public static String readText(String fileName) { // 接收读取的字符串 StringBuffer sb = new StringBuffer(); // 定义管道流 BufferedReader in; try { in = new BufferedReader(new FileReader(fileName)); String line; while ((line = in.readLine()) != null) { // 集合和关系字符串以";"分割,便于后面的解析 sb.append(line).append(separator); } // 关闭管道流 in.close(); } catch (FileNotFoundException e) { System.err.println("找不到对应的文件,请检查：" + e.getMessage()); } catch (IOException e) { System.err.println("读取文件失败,请检查：" + e.getMessage()); } // 返回读取到的字符串信息 return sb.toString(); }

  /**

  • 根据处理方式处理读取到的字符串信息
  • clfs为0：将集合中的元素放入一维数组中返回
  • clfs为1：将集合上的关系中每个有序对放入二维数组中返回
  • @param str
  • @param clfs

  • @return
    */
    public static Object dealStr(String str, int clfs) {
    String[] returnObj = null; // 返回字符串数组
    String[][] returnObjs = null; // 返回字符串二维数组

    String[] strs = str.split(separator);
    String[] temp = null;
    if (CLFS_JH == clfs) { // 处理集合中的元素
    temp = strs[clfs].split("=");
    returnObj = temp[1].substring(1, temp[1].length() - 2).split(",");
    } else if (CLFS_GX == clfs) { // 处理集合上的关系
    temp = strs[clfs].split("=");
    String[] tempStr = temp[1].substring(2, temp[1].length() - 3)
    .split(">,<");
    returnObjs = new String[tempStr.length][2];
    for (int i = 0; i < tempStr.length; i++) {
    String s = tempStr[i];
    returnObjs[i][0] = s.split(",")[0];
    returnObjs[i][1] = s.split(",")[1];
    }
    }
    // 返回处理结果
    return clfs == 0 ? returnObj : returnObjs;
    }

  /**

  • 将关系转换为矩阵
  • @param relation
  • @param element */ public static int[][] conversionMatrix(String[][] relation, String[] element) { // 定义矩阵 int[][] M = new int[element.length][element.length]; // 将关系转换为矩阵 for (int k = 0; k < relation.length; k++) { int i = 0, j = 0; boolean isExistRow = false; boolean isExistColumn = false; for (int l = 0; l < element.length; l++) { // 找到对应的行 if (relation[k][0].equals(element[l])) { i = l; isExistRow = true; } // 找到对应的列 if (relation[k][1].equals(element[l])) { j = l; isExistColumn = true; } } // 只有存在行,列时才置值为1 if (isExistRow && isExistColumn) { M[i][j] = 1; } } // 返回矩阵 return M; }

  /**

  • 得到传递闭包
  • @param str

  • @param num
    */
    public static int[][] genClosure(int[][] M, int N) {
    //Warshall算法
    for (int k = 0; k < N; k++) {
    for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
    M[i][j] = M[i][j] + M[i][k] * M[k][j];
    }
    }
    }

    //将矩阵关系中非零的数值置为1
    for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
    if (M[i][j] == 0) {
    continue;
    } else {
    M[i][j] = 1;
    }
    }
    }
    //重新返回矩阵关系
    return M;
    }

  /**

  • 显示矩阵关系
  • @param M
  • @param N */ public static String display(int[][] M, int N){ StringBuffer sb = new StringBuffer(); // 显示关系矩阵 for (int i = 0; i < N; i++) { sb.append("\t"); for (int j = 0; j < N; j++) { sb.append(M[i][j]+ " "); } sb.append("\n"); } return sb.toString(); }

  /**

  • 将矩阵转换为关系
  • @param relation

  • @param element
    */
    public static String conversionRelations(int[][] M, String[] element) {
    // 定义连接字符串
    StringBuffer sb = new StringBuffer();
    sb.append("t(R)={");
    String relata = "";
    String relatb = "";

    //遍历矩阵,拼接返回关系
    for (int i = 0; i < element.length; i++) {
    for (int j = 0; j < element.length; j++) {
    if (M[i][j] == 0) {
    continue;
    } else {
    relata = element[i];
    relatb = element[j];
    }
    sb.append("<").append(relata).append(",").append(relatb).append(">").append(",");
    }
    }
    int index = sb.lastIndexOf(">,");
    //删除最后的逗号
    if(index > -1) {
    sb.deleteCharAt(index+1);
    }
    // 返回关系
    return sb.append("}").toString();
    }

  /**

  • 写txt文件
  • @param str
  • @param outputFileName */ public static void writeText(String str, String outputFileName) { File f = new File(outputFileName); try { f.createNewFile();//创建文件 // 定义管道流 BufferedWriter output = new BufferedWriter(new FileWriter(f)); // 写入文件 output.write(str); // 关闭管道流 output.close(); } catch (IOException e) { e.printStackTrace(); } } } [/code]