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

Question

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

Answer 1

两种方法分别求传递闭包，全部自己实现，没有用到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();
}

}