//AVTOR: Boštjan Kač 27005020 (druga seminarska naloga pri predmetu R2)

public class TestBellmanFord{
  
  public static void main(String[] args)throws Exception{
    
    try{
      
    System.out.println();
    System.out.println("******************************");
    System.out.println();
    
    //PRIMER 1:
    //vhodni podatki:
    Povezava e1 = new Povezava (1,4,2);
    Povezava e2 = new Povezava (3,1,1);
    Povezava e3 = new Povezava (1,3,2);
    Povezava e4 = new Povezava (0,1,-1);
    Povezava e5 = new Povezava (0,2,4);
    Povezava e6 = new Povezava (3,2,5);
    Povezava e7 = new Povezava (1,2,3);
    Povezava e8 = new Povezava (4,3,-3);
    
    int m1 = 8;
    
    Povezava [] e = new Povezava [m1];
    
    e[0] = e1;
    e[1] = e2;
    e[2] = e3;
    e[3] = e4;
    e[4] = e5;
    e[5] = e6;
    e[6] = e7;
    e[7] = e8;
        
    int s1 = 0;
    
    int [] v1 = {0,1,2,3,4};
    
    int n1 = v1.length;
    
    System.out.println("VHODNI PODATKI:");
    for(int i = 0; i < n1; i++){
      System.out.print(v1[i] + " ");    
    } System.out.println(" ...  vozlisca v1,v2,...,vn");
    
    System.out.println(s1+ " ... izhodniscno vozlisce s"); 
    
    for(int i = 0; i<e.length; i++){
      System.out.print(e[i]);
    }System.out.println("...mnozice utezenih usmerjenih povezav e1,e2,...,em");
    
    System.out.println();
    
    //izhodni podatki:
    System.out.println("IZHODNI PODATKI:");
    System.out.println("Prva vrstica izhodne matrike predstavlja dolzine najkrajsih poti od izhodiscnega vozlisca s do vozlisc v1,v2,...,vn"); 
    System.out.println("Druga vrstica izhodne matrike predstavlja optimalne predhodnike vozlisc v1,v2,...,vn ");
    int [][] izhodna1 = new int [2][n1];
    izhodna1 = BellmanFord.resi(v1,e,s1);
    BellmanFord.izpisiResitev(izhodna1);
     
    System.out.println();
    System.out.println("******************************");
    System.out.println();
    
    //PRIMER 2:
    //vhodni podatki:
    Povezava d1 = new Povezava (4,5,23);
    Povezava d2 = new Povezava (19,17,6);
    Povezava d3 = new Povezava (11,10,20);
    Povezava d4 = new Povezava (0,1,5);
    Povezava d5 = new Povezava (0,11,2);
    Povezava d6 = new Povezava (11,1,1);
    Povezava d7 = new Povezava (0,16,3);
    Povezava d8 = new Povezava (13,12,7);
    Povezava d9 = new Povezava (14,13,2);
    Povezava d10 = new Povezava (5,14,8);
    Povezava d11 = new Povezava (1,2,3);
    Povezava d12 = new Povezava (11,3,9);
    Povezava d13 = new Povezava (2,12,34);
    Povezava d14 = new Povezava (16,5,1);
    Povezava d15 = new Povezava (17,19,4);
    Povezava d16 = new Povezava (8,18,3);
    Povezava d17 = new Povezava (5,8,7);
    Povezava d18 = new Povezava (3,4,12);
    Povezava d19 = new Povezava (14,4,1);
    Povezava d20 = new Povezava (5,4,6);
    Povezava d21 = new Povezava (9,6,5);
    Povezava d22 = new Povezava (8,7,2);
    Povezava d23 = new Povezava (14,17,9);
    Povezava d24 = new Povezava (14,15,8);
    Povezava d25 = new Povezava (8,9,8);
    Povezava d26 = new Povezava (7,17,3);
     
    int m2 = 26;
    
    Povezava [] d = new Povezava [m2];
    
    d[0] = d1;
    d[1] = d2;
    d[2] = d3;
    d[3] = d4;
    d[4] = d5;
    d[5] = d6;
    d[6] = d7;
    d[7] = d8;
    d[8] = d9;
    d[9] = d10;
    d[10] = d11;
    d[11] = d12;
    d[12] = d13;
    d[13] = d14;
    d[14] = d15;
    d[15] = d16;
    d[16] = d17;
    d[17] = d18;
    d[18] = d19;
    d[19] = d20;
    d[20] = d21;
    d[21] = d22;
    d[22] = d23;
    d[23] = d24;
    d[24] = d25;
    d[25] = d26;
    
    int s2 = 0;
    
    int [] v2 = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19};
    
    int n2 = v2.length;
    
    System.out.println("VHODNI PODATKI:");
    for(int i = 0; i < n2; i++){
      System.out.print(v2[i] + " ");    
    } System.out.println(" ...  vozlisca v1,v2,...,vn");
    
    System.out.println(s2+ " ... izhodniscno vozlisce s"); 
    
    for(int i = 0; i<d.length; i++){
      System.out.print(d[i]);
    }System.out.println("...mnozice utezenih usmerjenih povezav e1,e2,...,em");
    
    System.out.println();
    
    //izhodni podatki:
    System.out.println("IZHODNI PODATKI:");
    System.out.println("Prva vrstica izhodne matrike predstavlja dolzine najkrajsih poti od izhodiscnega vozlisca s do vozlisc v1,v2,...,vn"); 
    System.out.println("Druga vrstica izhodne matrike predstavlja optimalne predhodnike vozlisc v1,v2,...,vn ");
    int [][] izhodna2 = new int [2][n2];
    izhodna2 = BellmanFord.resi(v2,d,s2);
    BellmanFord.izpisiResitev(izhodna2);
      
    System.out.println();
    System.out.println("******************************");
    System.out.println();
      
    //PRIMER 3:
    //vhodni podatki:
    Povezava f1 = new Povezava (0,1,2);
    Povezava f2 = new Povezava (1,2,1);
    Povezava f3 = new Povezava (0,2,4);
    Povezava f4 = new Povezava (2,3,5);
    Povezava f5 = new Povezava (3,4,7);
    
    int m3 = 5;
    
    Povezava [] f = new Povezava [m3];
    
    f[0] = f1;
    f[1] = f2;
    f[2] = f3;
    f[3] = f4;
    f[4] = f5;
   
    int s3 = 0;
    
    int [] v3 = {0,1,2,3,4};
    
    int n3 = v3.length;
    
    System.out.println("VHODNI PODATKI:");
    for(int i = 0; i < n3; i++){
      System.out.print(v3[i] + " ");    
    } System.out.println(" ...  vozlisca v1,v2,...,vn");
    
    System.out.println(s3+ " ... izhodniscno vozlisce s"); 
    
    for(int i = 0; i<f.length; i++){
      System.out.print(f[i]);
    }System.out.println("...mnozice utezenih usmerjenih povezav e1,e2,...,em");
    
    System.out.println();
    
    //izhodni podatki:
    System.out.println("IZHODNI PODATKI:");
    System.out.println("Prva vrstica izhodne matrike predstavlja dolzine najkrajsih poti od izhodiscnega vozlisca s do vozlisc v1,v2,...,vn"); 
    System.out.println("Druga vrstica izhodne matrike predstavlja optimalne predhodnike vozlisc v1,v2,...,vn ");
    int [][] izhodna3 = new int [2][n3];
    izhodna3 = BellmanFord.resi(v3,f,s3);
    BellmanFord.izpisiResitev(izhodna3);
       
    System.out.println();
    System.out.println("******************************");
    System.out.println();
    
    //PRIMER 4:
    //vhodni podatki: 
    Povezava h1 = new Povezava (0,1,4);
    Povezava h2 = new Povezava (1,2,7);
    Povezava h3 = new Povezava (2,3,2);
    Povezava h4 = new Povezava (3,1,3);
      
    int m4 = 4;
    
    Povezava [] h = new Povezava [m4];
    
    h[0] = h1;
    h[1] = h2;
    h[2] = h3;
    h[3] = h4;  
   
    int s4 = 0;
    
    int [] v4 = {0,1,2,3};
    
    int n4 = v4.length;
    
    System.out.println("VHODNI PODATKI:");
    for(int i = 0; i < n4; i++){
      System.out.print(v4[i] + " ");    
    } System.out.println(" ...  vozlisca v1,v2,...,vn");
    
    System.out.println(s4+ " ... izhodniscno vozlisce s"); 
    
    for(int i = 0; i<h.length; i++){
      System.out.print(h[i]);
    }System.out.println("...mnozice utezenih usmerjenih povezav e1,e2,...,em");
    
    System.out.println();
  
    //izhodni podatki:
    System.out.println("IZHODNI PODATKI:");
    System.out.println("Prva vrstica izhodne matrike predstavlja dolzine najkrajsih poti od izhodiscnega vozlisca s do vozlisc v1,v2,...,vn"); 
    System.out.println("Druga vrstica izhodne matrike predstavlja optimalne predhodnike vozlisc v1,v2,...,vn ");
    int [][] izhodna4 = new int [2][n4];
    izhodna4 = BellmanFord.resi(v4,h,s4);
    BellmanFord.izpisiResitev(izhodna4);
     
    System.out.println();
    System.out.println("******************************");
    System.out.println();
    
    //PRIMER 5:
    //vhodni podatki:
    Povezava t1 = new Povezava (0,1,7);
    Povezava t2 = new Povezava (0,4,3);
    Povezava t3 = new Povezava (0,3,9);
    Povezava t4 = new Povezava (4,3,11);
    Povezava t5 = new Povezava (1,3,1);
    Povezava t6 = new Povezava (1,2,13);
    Povezava t7 = new Povezava (3,2,1);
    
    int m6 = 7;
    
    Povezava [] t = new Povezava [m6];
    
    t[0] = t1;
    t[1] = t2;
    t[2] = t3;
    t[3] = t4;
    t[4] = t5;
    t[5] = t6;
    t[6] = t7;
    
    int s6 = 0;
    
    int [] v6 = {0,1,2,3,4};
    
    int n6 = v6.length;
    
    System.out.println("VHODNI PODATKI:");
    for(int i = 0; i < n6; i++){
      System.out.print(v6[i] + " ");    
    } System.out.println(" ...  vozlisca v1,v2,...,vn");
    
    System.out.println(s6+ " ... izhodniscno vozlisce s"); 
    
    for(int i = 0; i<t.length; i++){
      System.out.print(t[i]);
    }System.out.println("...mnozice utezenih usmerjenih povezav e1,e2,...,em");
    
    System.out.println();
    
    //izhodni podatki:
    System.out.println("IZHODNI PODATKI:");
    System.out.println("Prva vrstica izhodne matrike predstavlja dolzine najkrajsih poti od izhodiscnega vozlisca s do vozlisc v1,v2,...,vn"); 
    System.out.println("Druga vrstica izhodne matrike predstavlja optimalne predhodnike vozlisc v1,v2,...,vn ");
    int [][] izhodna6 = new int [2][n6];
    izhodna6 = BellmanFord.resi(v6,t,s6);
    BellmanFord.izpisiResitev(izhodna6);
       
    System.out.println();
    System.out.println("******************************");
    System.out.println();
    
    
    //PRIMER 6:
    //vhodni podatki:
    //(graf vsebuje negativni cikel)
    Povezava g1 = new Povezava (0,1,3);
    Povezava g2 = new Povezava (1,2,-1);
    Povezava g3 = new Povezava (2,3,-2);
    Povezava g4 = new Povezava (3,1,-3);
      
    int m5 = 4;
    
    Povezava [] g = new Povezava [m5];
    
    g[0] = g1;
    g[1] = g2;
    g[2] = g3;
    g[3] = g4;  
   
    int s5 = 0;
    
    int [] v5 = {0,1,2,3};
    
    int n5 = v5.length;
    
    System.out.println("VHODNI PODATKI:");
    for(int i = 0; i < n5; i++){
      System.out.print(v5[i] + " ");    
    } System.out.println(" ...  vozlisca v1,v2,...,vn");
    
    System.out.println(s5+ " ... izhodniscno vozlisce s"); 
    
    for(int i = 0; i<g.length; i++){
      System.out.print(g[i]);
    }System.out.println("...mnozice utezenih usmerjenih povezav e1,e2,...,em");
    
    System.out.println();
    
    //izhodni podatki:
    System.out.println("IZHODNI PODATKI:");
    System.out.println("Prva vrstica izhodne matrike predstavlja dolzine najkrajsih poti od izhodiscnega vozlisca s do vozlisc v1,v2,...,vn"); 
    System.out.println("Druga vrstica izhodne matrike predstavlja optimalne predhodnike vozlisc v1,v2,...,vn ");
    int [][] izhodna5 = new int [2][n5];
    izhodna5 = BellmanFord.resi(v5,g,s5);
    BellmanFord.izpisiResitev(izhodna5);
    
    System.out.println();
    System.out.println("******************************");
    System.out.println();

    
    
    } catch (Exception ex){
            System.out.println(ex.getMessage());
        }
    
  }
}

/* "Izjavljam, da sem nalogo opravil samostojno in da sem njen avtor. Zavedam se, da v primeru,
če izjava prvega stavka ni resnična, kršim disciplinska pravila Fakultete za matematiko in fiziko." */