public class GraphT {
	                                             
                            
    static boolean [][] graph = {
                            {false, false,  true, false},
                            {false, false, false,  true},
                            {false, true, false, false},
                            {false, false, false, false},
                            };	
   
   /*
   static boolean [][] graph2 = {
                            {false, false,  false, false},
                            {false, false, false,  false},
                            {false, false, false, false},
                            {false, false, false, false},
                            };	
                            
    static boolean [][] graph2 = {
                            {false, true,  false, false},
                            {false, false, true,  false},
                            {false, false, false, true},
                            {false, false, false, false},
                            };
     */                       	
                                                                     

    public static void main(String ... args) {
        System.out.println("Warshall Tester");
        
        System.out.println("graph");
        Warshall w = new Warshall(graph);
        w.wt();
        
        
        System.out.println("Ende Warshall Tester");
        
    }
}


class Warshall{
    boolean [][] graph, table1, table2; 
    int dim;
    
    Warshall(boolean [][] a){
    	graph = a;
    	dim = a.length;
    	int max = dim;
    	table1 = new boolean [max][max];
    	table2 = new boolean [max][max];
    	for (int i=0; i<max; i++)
    	  for (int j=0; j<max; j++) 
    	     table2[i][j] = table1[i][j] = graph[i][j];
    	}
    	
    void testOut(boolean [][] a){
    	System.out.println("------------------------");
    	for (int i=0; i<dim; i++){
    	  for (int j=0; j<dim; j++) 
    	     if (a[i][j]) System.out.print("1 "); else System.out.print("0 ");
    	  System.out.println();
    	  }   
    	 System.out.println("------------------------"); 
    	} 	     

    void warshallAlgYX(){
        int max = dim;
        for (int y = 0; y < max; y++)
            for (int x = 0; x < max; x++)
                for (int z = 0; z < max; z++)
                    table1[x][z] |= table1[x][y] && table1[y][z];
        }
        
    void warshallAlgXY(){
        int max = dim;
        for (int x = 0; x < max; x++)
            for (int y = 0; y < max; y++)
                for (int z = 0; z < max; z++)
                    table2[x][z] |= table2[x][y] && table2[y][z];
        }    

     void wt(){
     	System.out.println("graph :");
    	testOut(graph);
    	System.out.println("Richtige T-Hülle :");
    	warshallAlgYX();
    	testOut(table1);
    	System.out.println("XY-T-Hülle :");
    	warshallAlgXY();
    	testOut(table2);
    	} 
}