Results 1 to 13 of 13
  1. #1
    DeanMoriarty is offline Member
    Join Date
    Jul 2009
    Posts
    7
    Rep Power
    0

    Default number unstableness

    Hi, I'm relatively new to the world of java, but recently I've been working on a project which requires as final step the implementation of an algorithm.First of all I want to say that I only have to use this programme for this one application so I dont need it to be re used or called from some other class or anything else.
    So:
    I have created a class with some static class instances and a series of methods(all static) which i use in main that basically,starting from a matrix of values(which I initialize to values at the start of the main), "work" there way step by step (using among others the Floyd-Warshall algorithm that some of you may know)selecting the value that has to be eliminated and substituting it with another(following some criteria that I avoid to mention) and so on until the final matrix is accomplished. Now to avoid to bore you I wont explain in detail the whole process of data-using, being the whole thing long and quite complicated(as much as I'd love to post the whole programme here and hope for someones help!:)). So I'll stick to the subject of the topic.
    I have realized in my debug that after a certain number of iterations the values in the matrix start going crazy, changing from a certain value in memory to another value completely. Now the complexity of the the algorithm is n^3+ (being composed of three cycles plus a lot of other operations )and in this case n is 109.
    Considering that everytime the algorithm substitues a value it restarts from the beginning, overriding the old value in the matrix with the new one, could it be for some absurd reason that the Java Machine cannot handle these kind of numbers using static methods? or more likely does someone have any idea whats going on?

    Thanks for your time

  2. #2
    angryboy's Avatar
    angryboy is offline Senior Member
    Join Date
    Jan 2009
    Posts
    742
    Rep Power
    6

    Default

    most likely a logic error. mind posting the code?
    USE CODE TAGS--> [CODE]...[/CODE]
    Get NotePad++ (free)

  3. #3
    DeanMoriarty is offline Member
    Join Date
    Jul 2009
    Posts
    7
    Rep Power
    0

    Default

    Not at all, only its quite long.. plus the method and object names are in italian mostly, i hope its not to hard to interpret the meaning..

    to explain briefly I have imported from a File a matrix of thousands of rows and nine columns, of which only 5 are of interest.
    The first and fourth column values are the indexes of the new matrix(I already know that there are 109), and since they can reoccur it basically overrides the value in it if its minor than one found. I have created a boolean matrix to recognize if an arch is really 0 or if its just default.
    Each value is an arch,each index a node(it represents a graph).
    The crucial method FloydWarshall(D,B,pred) analizes the paths from node to node and if it finds a way to get from A to B going through C that costs less or even exits it will put the AB value to that cost.
    The problem is if it crosses some negative cost cycles(in the graph).
    Which is this case: (if(i==j)&&matrice[i][j]>matrice[i][k]+matrice[k][j])
    I have to find out with a complicated procedure that uses mostly the other values in the original matrix that i havent talked about,which value(arch) to substitute.
    Once I have found this value I put in the matrix and start the Floyd Warshall again, with the SAME matrix of values APART from the one i've decided to substitute.

    One of my main issues is to pass the starting matrix as a parameter with out it actually being changed, because all i want to change is the one value i only find when i cross that specific situation.Thats why I try copying it and the Boolean matrix into other objects B and D in main.

    I know, its complicated, i can perfectly understand if u cant be asked to work through it, thanks anyways...

    Anyway heres the code with some tags, the extra bits and pieces maybe from debugging :

    Java Code:
    import java.io.File;
    import java.io.FileNotFoundException;
    import java.util.Scanner;
    import java.util.logging.Level;
    import java.util.logging.Logger;
    
    
    public class LetturaMatrici {
    
    public static String[][] matriceImportata;
    public static int[][] matriceCreataD;
    public static int[][] matriceCreataT;
    public static File ts;
    public static int[][] matriceCreataP;
    public static boolean[][] matriceBooleana;
    public static int[][] predecessori;
    public static void main(String[] args){
    
        matriceBooleana = new boolean[109][109];
        matriceCreataD = new int[109][109];
        matriceCreataT = new int[109][109];
        matriceCreataP = new int[109][109];
        predecessori = new int[109][109];
    
        
        String nomefile = new String("C:\\Users\\Leo\\Desktop\\Lab OC\\GrafoFinaleI - SPD - MONTE MADONNA.tab");
        ts =new File(nomefile);
                
         importaMatrice();              //imports from file
        creaMatriceBooleana();     //initializes the Boolean to true on diagonal
        creaMatrice();        // creates the matrix we work on 
        predecessori();    //tells you if a two nodes are actually connected
        int[][]D=matriceCreataD;
        int[][]P=matriceCreataP;
        int[][]T=matriceCreataT;
        boolean[][]B=matriceBooleana;
        int[][]pred=predecessori;
       
       FloydWarshall(D,B,pred);
    for(int i=0;i<109;i++){
    System.out.println("il guadagno G"+i+"  "+matriceCreataD[0][i]);} 
    }
    
    public static void FloydWarshall(int[][] matrice,boolean[][] confronto,int[][] pred){//IMPORTANT
        int i,j,k;
       boolean ciclo=false;
        while(ciclo==false){
        read_data:
            for(k=0;k<109;k++){
            for(i=0;i<109;i++){
            for(j=0;j<109;j++){
                if(confronto[i][k]==true&&confronto[k][j]==true){
                if(i==j&&matrice[i][j]>matrice[i][k]+matrice[k][j]){ //crucial part!!!!
      int [] eliminare=new int[2];
        eliminare=sostituzione(i,k,j,pred,matrice,matriceCreataP,matriceCreataT);
    
    //finds the arch(value) to substitute or in case eliminate altogether..
    
    
    int arco0=getValueArch0(eliminare);
    int arco1=getValueArch1(eliminare);
    int cx=getValueCost(arco0,arco1,matriceCreataD);
    
    if(verificaArcoUnico(arco0,arco1,cx)==true){
        matriceBooleana[arco0][arco1]=false;
    confronto=matriceBooleana;
    predecessori();
    pred=predecessori;
    }
    else {
         creaMatriceAggiornata(arco0,arco1,cx,matrice,confronto);
       confronto=matriceBooleana;
    matrice=matriceCreataD;
    predecessori();
    pred=predecessori;}
     
               break read_data;
      }
       else {
            if(confronto[i][j]==false){
      matrice[i][j]=matrice[i][k]+matrice[k][j];
                   confronto[i][j]=true;
                   pred[i][j]=pred[k][j];
             }
           else{
                   if(matrice[i][j]>(matrice[i][k]+matrice[k][j])){
       matrice[i][j]=matrice[i][k]+matrice[k][j];
                   confronto[i][j]=true;
                   pred[i][j]=pred[k][j];
                   }
               }
               }
    
        }
       if(i==109&&k==109&&j==109)
        ciclo=true; }
        }  }}
     }
           }
    
    
    
    public static void creaMatriceAggiornata(int r,int c, int costo,int[][]matrice,boolean[][]b){
        int righe=getNumRighe();
        int valore0,valore3,valore6,valore7,valore8;
        boolean popolazioneZero;
        b[r][c]=false;
        for (int riga=0;riga<righe;riga++){
    
            popolazioneZero=false;
         
            valore0=getMatrixValue(matriceImportata,riga,0);
            valore3=getMatrixValue(matriceImportata,riga,3);
    
            valore6=getMatrixValue(matriceImportata,riga,6);
            valore7=getMatrixValue(matriceImportata,riga,7);
                    valore8=getMatrixValue(matriceImportata,riga,8);
    
           if (valore7==0 && valore8 != 0)
                popolazioneZero=true;
                    if(valore0==r&&valore3==c)
                {
                        if ((conditionsValidatorAggiornata(valore0,valore3,valore6,costo,matrice,b)==true)&& popolazioneZero==false) {
    
                setMatrixValue(matriceCreataD,valore0,valore3,valore6);
        setMatrixValue(matrice,valore0,valore3,valore6);
                matriceBooleana[valore0][valore3]=true;
                b[valore0][valore3]=true;
                setMatrixValue(matriceCreataP,valore0,valore3,valore7);
                setMatrixValue(matriceCreataT,valore0,valore3,valore8);
            }}
                  
            }
    }
    
    
    public static boolean conditionsValidatorAggiornata(int riga,int colonna,int nuovoValoreD,int costo,int[][]matrice,boolean[][]b){
        if(nuovoValoreD>costo){
        if (b[riga][colonna]==false){
            System.out.println("aggiorna boolean");
              return true;
         }
        else   if(matrice[riga][colonna] > nuovoValoreD){
            System.out.println("nuovo valore "+nuovoValoreD);
             return true;}
            else return false  ;  }
        else return false;}
    
    
    public static boolean conditionsValidator(int riga,int colonna,int nuovoValoreD,int nuovoValoreP){
        if (matriceBooleana[riga][colonna]==false) return true;
        else if(matriceCreataD[riga][colonna] > nuovoValoreD)return true;
            else {
            return(matriceCreataD[riga][colonna]==nuovoValoreD&&nuovoValoreP>matriceCreataP[riga][colonna]);}
        }
    public static int getMatrixValue(String[][] matrice,int riga,int colonna){
        return Integer.parseInt(matrice[riga][colonna]);
    }
    
    public static int setMatrixValue(int[][] matrice,int riga,int colonna,int valore){
        return matrice[riga][colonna] = valore;
    }
    public static void predecessori(){
    int i,j;
        for(i =0;i<109;i++){
        for(j=0;j<109;j++){
            if(matriceBooleana[i][j]==true)
            predecessori[i][j]=i;
          
        }}
    
    }
    public static int getValueArch0(int[]arco){
    int value=arco[0];
    return value;
    }
    public static int getValueArch1(int[]arco){
    int value=arco[1];
    return value;
    }
    public static int getValueCost(int i,int j,int[][]matrice){
    int value=matrice[i][j];
    return value;
    }
    
    
    
     public static int[] sostituzione(int i, int k,int j, int[][] pred,int[][]D,int[][]P,int[][]T){
     //System.out.println("manco arriva?");
        int[][]archiCicloIK=qualiArchi(i,k,pred);
     int[][]archiCicloKJ=qualiArchi(k,j,pred);
    
     if(contaRighe(archiCicloIK)==1&&contaZeri(i,k,archiCicloIK)==0){
    
     int[][]KJmenoZeri=eliminaZeri(k,j,archiCicloKJ,pred);
    
       
     int[][]KJ=eliminaTestpointZero(KJmenoZeri,T);
    
     int[][]IK=new int[0][2];
     int[]eliminalo=arcoEliminato(IK,KJ,D,P);
    // System.out.println("eliminalo:");
    // System.out.println(eliminalo[0]);
     //System.out.println(eliminalo[1]);
     return eliminalo;
     }
     else if(contaRighe(archiCicloKJ)==1&&contaZeri(k,j,archiCicloKJ)==0){
     //System.out.println("qua si kj"+k+""+j);
     int[][]IKmenoZeri=eliminaZeri(i,k,archiCicloIK,pred);
     int[][]IK=eliminaTestpointZero(IKmenoZeri,T);
     int[][]KJ=new int[0][2];
     int[]eliminalo=arcoEliminato(IK,KJ,D,P);
     return eliminalo;
     }else{
     int[][]IKmenoZeri=eliminaZeri(i,k,archiCicloIK,pred);
     int[][]KJmenoZeri=eliminaZeri(k,j,archiCicloKJ,pred);
     if(contaRighe(IKmenoZeri)==1&&contaTestpointZero(IKmenoZeri,T)==0){
            int[][]KJ=eliminaTestpointZero(KJmenoZeri,T);
     int[][]IK=new int[0][2];
     int[]eliminalo=arcoEliminato(IK,KJ,D,P);
     return eliminalo;
     }
     else if(contaRighe(KJmenoZeri)==1&&contaTestpointZero(KJmenoZeri,T)==0){
            int[][]IK=eliminaTestpointZero(IKmenoZeri,T);
    int[][]KJ=new int[0][2];
    int[]eliminalo=arcoEliminato(IK,KJ,D,P);
    return eliminalo;
    }else{
    //System.out.println("fin qui bene2");
    //System.out.println("fin qui bene3");
    //System.out.println("fin qui bene4");
    int[][]IK=eliminaTestpointZero(IKmenoZeri,T);
        int[][]KJ=eliminaTestpointZero(KJmenoZeri,T);
    //System.out.println("fin qui bene5");
    int[]eliminalo=arcoEliminato(IK,KJ,D,P);
    return eliminalo;
    }} }
    
    public static boolean verificaArcoUnico(int i, int j,int costo){
        int righe=getNumRighe();
        int valore0, valore3, valore6,valore7,valore8;
        boolean vero=true;
        boolean popolazioneZero;
        int contatore=0;
        for(int riga=0;riga<righe;riga++){
          popolazioneZero=false;
            valore0=getMatrixValue(matriceImportata,riga,0);
            valore3=getMatrixValue(matriceImportata,riga,3);
        valore6=getMatrixValue(matriceImportata,riga,6);
            valore7=getMatrixValue(matriceImportata,riga,7);
                    valore8=getMatrixValue(matriceImportata,riga,8);
            if (valore7==0 && valore8 != 0) popolazioneZero=true;
            if(i==valore0&&j==valore3&&popolazioneZero==false&&valore6>costo)
            contatore++;
        }
        if (contatore>0)
            vero=false;
        return vero;
    }
    public static int[] arcoEliminato(int[][]matrice1, int[][]matrice2,int[][]matriceD,int[][]matriceP){
    int z1=contaRighe(matrice1);
    int z2=contaRighe(matrice2);
    if(z2==0){
    float costoPesato1=0;
    float p;
    long pt1;
    pt1=totalePopolazione(matrice1,matriceP);
    float ct1;
    ct1=totaleCosto(matrice1,matriceD);
    int c;
    int i,j;
    int []arco1=new int[2];
    for(int u=0;u<z1;u++){
        i=matrice1[u][0];
        j=matrice1[u][1];
    p=matriceP[i][j];
    c=matriceD[i][j];
        if(u==0){
    arco1[0]=i;
    arco1[1]=j;
    costoPesato1=costoPesato(p,pt1,c,ct1);}
        else{if(costoPesato(p,pt1,c,ct1)<costoPesato1){
    arco1[0]=i;
    arco1[1]=j;
    costoPesato1=costoPesato(p,pt1,c,ct1);}}}
    return arco1;
    }else if(z1==0){ 
        float costoPesato2=0;
    float p;
    long pt2;
    pt2=totalePopolazione(matrice2,matriceP);
    float ct2;
    ct2=totaleCosto(matrice2,matriceD);
    int c;
    int i,j;
    int []arco2=new int[2];
    //boolean b=false;
    for(int u=0;u<z2;u++){
        i=matrice2[u][0];
        j=matrice2[u][1];
    p=matriceP[i][j];
    c=matriceD[i][j];
    if(u==0){
    arco2[0]=i;
    arco2[1]=j;
    costoPesato2=costoPesato(p,pt2,c,ct2);}
        else{
    if(costoPesato(p,pt2,c,ct2)<costoPesato2){
    arco2[0]=i;
    arco2[1]=j;
    costoPesato2=costoPesato(p,pt2,c,ct2);}}}
    return arco2;}
    else{
    float costoPesato1=0;
    float costoPesato2=0;
    float p;
    long pt1,pt2;
    pt1=totalePopolazione(matrice1,matriceP);
    pt2=totalePopolazione(matrice2,matriceP);
    long pt=pt1+pt2;
    int c;
    float ct;
    float ct1,ct2;
    ct1=totaleCosto(matrice1,matriceD);
    ct2=totaleCosto(matrice2,matriceD);
    ct=ct1+ct2;
    int i,j;
    int []arco1=new int[2];
    int []arco2=new int[2];
    for(int u=0;u<z1;u++){
        i=matrice1[u][0];
        j=matrice1[u][1];
    p=matriceP[i][j];
    c=matriceD[i][j];
        if(u==0){
    arco1[0]=i;
    arco1[1]=j;
    costoPesato1=costoPesato(p,pt,c,ct);}
        else{
    if(costoPesato(p,pt,c,ct)<costoPesato1){
    arco1[0]=i;
    arco1[1]=j;
    costoPesato1=costoPesato(p,pt,c,ct);}}}
    for(int u=0;u<z2;u++){
        i=matrice2[u][0];
        j=matrice2[u][1];
    p=matriceP[i][j];
    c=matriceD[i][j];
        if(u==0){
    arco2[0]=i;
    arco2[1]=j;
    costoPesato2=costoPesato(p,pt,c,ct);}
        else{
    if(costoPesato(p,pt,c,ct)<costoPesato2){
    arco2[0]=i;
    arco2[1]=j;
    costoPesato2=costoPesato(p,pt,c,ct);}}}
    if(costoPesato1<costoPesato2)
    return arco1;
    else return arco2;
    }}
    
    public static int[] confrontaArchi(float ciclo1,float ciclo2,int[] arco1,int[]arco2){
    if(ciclo1<ciclo2)
    return arco1;
    else
    return arco2;
    
    }
    public static float costoPesato(float p,long pt,float c, float ct){
    float d=p/pt;
        float costoPesato=(p/pt)*3+(c/ct);
    return costoPesato;
    }
    public static long totalePopolazione(int[][]matrice1,int[][]popolazione){
    int z1=contaRighe(matrice1);
    int i,j;
    long p1=0;
    for(int x=0;x<z1;x++){
    i=matrice1[x][0];
    j=matrice1[x][1];
    p1=p1 +popolazione[i][j];
    }
    return p1;}
    
    public static float totaleCosto(int[][]matrice1,int[][]costi){
    int z1=contaRighe(matrice1);
    int c1=0;
    int c1opposto=0;
    for(int x=0;x<z1;x++){
    int i=matrice1[x][0];
    int j=matrice1[x][1];
    if(costi[i][j]<0){
     //  System.out.println("arco negativo1");
        c1opposto=modulo(costi[i][j]);
    c1=c1+c1opposto;}
    else c1=c1 +costi[i][j];
       //System.out.println("il costo 1 in"+i+""+j+""+c1);
    }
    return c1;}
    public static int modulo(int cn){
    int c;
    c=-cn;
    return c;
    }
    public static int[][] eliminaTestpointZero(int[][] eliminaZeri,int[][]tp){
    int i,j;
    int contatore=0;
    int t=contaTestpointZero(eliminaZeri,tp);
    int [][] eliminaTestpointZero=new int[t][2];
    int z=contaRighe(eliminaZeri);
    for(int x=0;x<z;x++){
    i=eliminaZeri[x][0];
    j=eliminaZeri[x][1];
    if(tp[i][j]!=0){
    eliminaTestpointZero[contatore][0]=eliminaZeri[x][0];
    eliminaTestpointZero[contatore][1]=eliminaZeri[x][1];
    contatore++;}
    }
    
    return eliminaTestpointZero;}
    
    public static int contaTestpointZero(int[][]eliminaZeri,int[][] matrice){
    int i, j;
    int contatore=0;
    int z=contaRighe(eliminaZeri);
    
    for(int x=0;x<z;x++){
    i=eliminaZeri[x][0];
    j=eliminaZeri[x][1];
    if(matrice[i][j]!=0)
        contatore++;
    }
    
    //System.out.println("qua c'arriva");
            return contatore;}
    public static int[][] qualiArchi(int i, int j,int[][] pred){
        int n_archi=1+contaPredecessori(i,j,pred);
      //  System.out.println("il numero di archi "+n_archi);
        int arco=0;
        int[][]qp=new int[n_archi][2];
       for(int c=0;c<n_archi;c++){
       if(c==0){arco=getPredecessore(i,j,pred);
       qp[c][0]=arco;
       qp[c][1]=j;
       }
       else{qp[c][1]=arco;
       qp[c][0]=getPredecessore(i,arco,pred);
       arco=getPredecessore(i,arco,pred);
       }
       }
    //System.out.println("quali archi ");
      //  int x=contaRighe(qp);
        // int r,c;
        //for(r=0;r<x;r++){
       //for(c=0;c<2;c++){
       //System.out.print(qp[r][c]+"");}
       //System.out.println("");}
    
        return qp;
    }
    public static int getPredecessore(int i, int j,int[][] pred){
        int k=pred[i][j];
        return k;
    }
    public static int contaPredecessori(int i, int j,int[][] pred ){
    int d=0;
    int c=pred[i][j];
    //System.out.println("predecessore "+c);
    if(c!=i){
    d++;
    return(d+contaPredecessori(i,c,pred));
    }else
    {//System.out.println("d "+d);
    return d;}
    
    }
    public static int[][] eliminaZeri(int i, int k, int[][]cammino, int[][] pred){
    int righe=contaZeri(i,k,cammino);
    int contatore=0;
    int[][]zeriEliminati=new int[righe][2];
    int iterazioni=contaRighe(cammino);
    //System.out.println("l'iterazioni  :"+iterazioni);
    for(int z=0;z<iterazioni;z++){
    if (cammino[z][0]!=0){
      // System.out.println("cammino0:"+cammino[z][0]);
        //System.out.println("cammino1:"+cammino[z][1]);
       zeriEliminati[contatore][0]=cammino[z][0];
        zeriEliminati[contatore][1]=cammino[z][1];
        contatore++;
    
    }
    }
    //for(int z=0;z<contaRighe(zeriEliminati);z++){
    //System.out.println("zeriEliminati:"+zeriEliminati[z][0]);
      //  System.out.println("zeriEliminati:"+cammino[z][1]);}
    return zeriEliminati;
    }
    
    
    public static int contaZeri(int i, int k, int[][]cammino){
    int righe=0;
    int iterazioni=contaRighe(cammino);
    for(int z=0;z<iterazioni;z++){
    if (cammino[z][0]!=0)
        righe++;
    }
    return righe;
    }
    
    public static int contaRighe(int[][]matrice){
    int righe=matrice.length;
    return righe;
    }
    
    public static int getNumRighe(){
              return 10900;
    
    
    
    
    }
    
    public static void importaMatrice(){
            try {
    
                int righe = getNumRighe();
                String[][] matrice = new String[righe][9];
                int riga = 0;
                int colonna = 0;
                String valore;
                int count = -1;
                Scanner scanner = new Scanner(ts);
                while (scanner.hasNext()) {
    
                    count++;
    
                    riga = count / 9;
                    colonna = count - riga * 9;
                    valore = scanner.next();
    
    
                    matrice[riga][colonna] = valore;
    
                }
                matriceImportata=matrice;
    
            } catch (FileNotFoundException ex) {
                Logger.getLogger(LetturaMatrici.class.getName()).log(Level.SEVERE, null, ex);
            }
    }
    
    
    public static void creaMatriceBooleana(){
    for(int i=0;i<109;i++){
    for(int j=0;j<109;j++){
    if(i==j)
    matriceBooleana[i][j]=true;
    }
    }
    }
    public static boolean[][] creaMatriceBooleanaAggiornata(boolean[][]confronto){
    for(int i=0;i<109;i++){
    for(int j=0;j<109;j++){
    if(i==j)
    confronto[i][j]=true;
    
    else confronto[i][j]=false;}
    }
    return confronto;
    }
    public static void creaMatrice()
    {
    
        int righe=getNumRighe();
        int valore0,valore3,valore6,valore7,valore8;
        boolean popolazioneZero;
        for (int riga=0;riga<righe;riga++){
    
            popolazioneZero=false;
            valore0=getMatrixValue(matriceImportata,riga,0);
            valore3=getMatrixValue(matriceImportata,riga,3);
    
            valore6=getMatrixValue(matriceImportata,riga,6);
            valore7=getMatrixValue(matriceImportata,riga,7);
                    valore8=getMatrixValue(matriceImportata,riga,8);
    
            if (valore7==0 && valore8 != 0) popolazioneZero=true;
    
    
            if (conditionsValidator(valore0,valore3,valore6,valore7) && !popolazioneZero) {
    
                setMatrixValue(matriceCreataD,valore0,valore3,valore6);
                matriceBooleana[valore0][valore3]=true;
                setMatrixValue(matriceCreataP,valore0,valore3,valore7);
                setMatrixValue(matriceCreataT,valore0,valore3,valore8);
            }
    
        }
    
    }
    Last edited by Fubarable; 07-08-2009 at 12:56 AM. Reason: Moderator: added code tags

  4. #4
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,315
    Blog Entries
    1
    Rep Power
    26

    Default

    I didn't go through all that code, but I can see that it is all one great big huge God-class filled with nothing but static methods. I'd suggest that you divide and conquer here by creating deciding what nouns (objects) your project should have, and then re-writing this with smaller more manageable and more debuggable classes.

    Also, I added code tags to your post make the code more readable. You may wish to use these in future posts, as more will read your code if it is readable.

    Also, to answer:
    could it be for some absurd reason that the Java Machine cannot handle these kind of numbers using static methods?
    Doubtful unless your numbers are going beyond the bounds of their types.

    Best of luck.

  5. #5
    DeanMoriarty is offline Member
    Join Date
    Jul 2009
    Posts
    7
    Rep Power
    0

    Default

    okay thanks for the tip, just one more question. About initializing a matrix to certain values, then copying it into a another identical matrix and passing the latter as a parameter of a method that uses it and MODIFIES it. Once i isolate one value that i want to change(in the original matrix), i change it and i copy the original matrix into the second one and i restart the method with as a parameter the second matrix and carry on doing so, I should be changing the original matrix only one value at the time, while all the change implied by the method and the copying should occur on the latter.. is that logically correct would you say?

  6. #6
    emceenugget is offline Senior Member
    Join Date
    Sep 2008
    Posts
    564
    Rep Power
    7

    Default

    you should try to simplify everything you're trying to say. it seems like you're being way too verbose for what you're looking for and it's hard to understand.

    from what i can decipher from your post, it seems like you are confused if changes in your original propagate to your copy. if that is your question, the answer is no. you have to write code to modify the copy whenever the original is modified.

    i think that's what you were asking...

  7. #7
    angryboy's Avatar
    angryboy is offline Senior Member
    Join Date
    Jan 2009
    Posts
    742
    Rep Power
    6

    Default

    I tried to read it, but I got lost in the Italian factories.

    For this method, your comment says you are trying to set the diagonal to true. is that for both ways? because this is only one way: 1-1, 2-2, 3-3...
    Java Code:
    public static void creaMatriceBooleana(){
    for(int i=0;i<109;i++){
    for(int j=0;j<109;j++){
    if(i==j)
    matriceBooleana[i][j]=true;
    }
    }
    can you attatch the .tab file as well?
    USE CODE TAGS--> [CODE]...[/CODE]
    Get NotePad++ (free)

  8. #8
    DeanMoriarty is offline Member
    Join Date
    Jul 2009
    Posts
    7
    Rep Power
    0

    Default

    first of all sincerely thanks for even trying to read it..

    the method you quoted puts the main diagonal values in the boolean matrix to true, it basically means that its always true that there is a path from a node to itself of 0 cost.

    I tried attaching the tab file but unfortunately it exceeds the forum limit, I'll post a sample of rows:

    0 - - 103 110 31 0 0 0
    0 - - 104 110 32 0 0 0
    0 - - 105 110 33 0 0 0
    0 - - 106 110 34 0 0 0
    0 - - 107 110 35 0 0 0
    0 - - 108 110 36 0 0 0
    1 108 1 0 - - -26 1004 9928
    1 108 1 0 - - -23 804 9927
    1 108 1 0 - - -22 3559 10232
    1 108 1 0 - - -8 1373 12039
    1 108 1 0 - - -8 1365 11151
    1 108 1 0 - - -7 955 12332
    1 108 1 0 - - -7 976 11747
    1 108 1 0 - - -7 2150 11448
    1 108 1 0 - - -6 3267 12614
    1 108 1 0 - - -6 2593 10541
    1 108 1 0 - - -4 1672 10846
    1 108 1 0 - - -3 1529 12899
    1 108 1 0 - - -1 1161 1054

    These are the nine columns I was talking about, column 0 and 3 are the indexes of the matrixes I have to create(matriceCreataD,matriceCreataP, matriceCreataT)as u see they repeat in values(in the example above 1,0 for instance). I have to make sure that initially the minor value of column 6 for each pair of values is saved in matriceCreataD, so in this case for 1,0 it would be -26, and the correspondant row values in the other matrixes(column7->matriceCreataP,column8->matriceCreataT).

    I'd say this is the easy part. The hard part is that FloydWarshall(,,,) works on the matrix I pass as a parameter, and finds the value to substitute or eliminate(in the above example lets say it would have been 1,0 -26). What I want to do is restart from MatriceCreataD, being the same in every value apart from this one I have decided to subsitute(lets say from -26 to the next value -23), and do the same to the other two Matrixes, so on until the algorithm finds that all the values of the Matrix MatriceCreataD suit him.

    I'm not sure how clear I've been, thanks for trying to follow!

  9. #9
    DeanMoriarty is offline Member
    Join Date
    Jul 2009
    Posts
    7
    Rep Power
    0

    Default

    I'm not sure what happened when I copied the rows, consider the - - as two columns,
    the three--- as one column only.

  10. #10
    DeanMoriarty is offline Member
    Join Date
    Jul 2009
    Posts
    7
    Rep Power
    0

    Default

    Quote Originally Posted by emceenugget View Post
    you should try to simplify everything you're trying to say. it seems like you're being way too verbose for what you're looking for and it's hard to understand.

    from what i can decipher from your post, it seems like you are confused if changes in your original propagate to your copy. if that is your question, the answer is no. you have to write code to modify the copy whenever the original is modified.

    i think that's what you were asking...


    ok I will try and be more clear because I think this is actually the problem of my code:

    I have a matrix of integers lets call it A
    I have cloned it into another identical matrix: B

    I use B as a parameter of a method that changes some of B's values and finally realizes there is a value of position ij in B that has to be eliminated or it can not go on.

    I then eliminate this value of position ij FROM A which is the important starting matrix, again copy A(which is the same as the start apart from this ij value) into B, and apply the method again on B.

    This carries on till the method finds no values it "needs" to eliminate.

    What I'm trying to do is modify A only one value at the time, and not letting it being modified by the method in its search of a value to eliminate.

    What I'm afraid is happening is that the method is modifying both B and A.
    Why is that?

    I hope I've been clear.

    Thanks for any help

  11. #11
    angryboy's Avatar
    angryboy is offline Senior Member
    Join Date
    Jan 2009
    Posts
    742
    Rep Power
    6

    Default

    Firstly, from the OP, I thought you had a working program. But it seems that there are spaces in your variables. After fixing that, and trying the sample data out, I'm getting NumberFormatExceptions from the dashes (- -). Was this the program you were refering to in the OP? How were you testing this out before?

    Second, I understand what that method above does. I was asking you which direction are you trying to set to. Like an X pattern or just \ or maybe /?
    Java Code:
    +--------/------------------ 
    | ****   |        |        | 
    | ****** |        |        | 
    |   *****|        |        | 
    |    *****        |        | 
    |-------***----------------- 
    |        ****     |        | 
    |        |*****   |        | 
    |        |  ****  |        | 
    |        |   *****|        | 
    |        |     ****        | 
    /--------.------******------ 
    |        |        ******   | 
    |        |        | *****  | 
    |        |        |   ***  | 
    |        |        |        / 
    \--------\--------\--------\
    USE CODE TAGS--> [CODE]...[/CODE]
    Get NotePad++ (free)

  12. #12
    DeanMoriarty is offline Member
    Join Date
    Jul 2009
    Posts
    7
    Rep Power
    0

    Default

    it's the same program, I may have tried changing some things between the OP and when I posted the code to solve the problem, infact now I get Exceptions too so you were definetly right that its a logic problem.

    One thing I found out is that copying the matrixes at the start is the wrong way to do it, so instead of simply
    int [][]D=creaMatriceD;

    i now introduced:

    for(int i=0;i<109;i++){
    for(int j=0;j<109;j++){
    D[i][j]=matriceCreataD[i][j];
    }
    }
    and the same for the matrixes i clone at the start.

    the direction I try to get in the creaMatriceBooleana()is \, for the reasons I said earlier.

    Do you think the problem is in the substitution method?(sostituzione(i,k,j,pred)

  13. #13
    angryboy's Avatar
    angryboy is offline Senior Member
    Join Date
    Jan 2009
    Posts
    742
    Rep Power
    6

    Default

    Seems like you are reading the whole file into a String array of 10900 x 9, then parsing it into an int array of 109 x 109. Then there's another int array of 109 x 109, and a boolean array of 109 x 109. I'm surprised you didn't run out of memory. haha

    I'm guessing D is for distance and P is for previous?

    Anyways, I rewrote the FWA as follows:
    Java Code:
    public final class FloydWarshall {
      public static final int INF = Integer.MAX_VALUE; // for inifinity values
      
      private FloydWarshall(){}
      
      /** 
        Floyd-Warshall algorithm
        returns the predecessor matrix.
        @param dist - a matrix initialized w/ edge values.
      */
      public static int[][] get(int[][] dist){
        final int N = dist.length;
        
        int[][] pred = new int[N][N]; // the return value
        for(int i=0; i<N; ++i){ // init predecessor matrix
            for(int j=0; j<N; ++j)
              pred[i][j] = i; // row 0=0, r1=1, r2=2...
        }
        
        int sum=0; //temp
        for(int k=0; k<N; ++k){
          for(int i=0; i<N; ++i){
            for(int j=0; j<N; ++j){
              if(dist[i][k]==INF || dist[k][j]==INF){
                continue;
              }
              sum = dist[i][k] + dist[k][j];
              if(sum < dist[i][j]){
                dist[i][j] = sum;
                pred[i][j] = pred[k][j];
              }
            }
          }
        }
        return pred;
      }
    }
    Here's a Driver (SEE DIAGRAM BELOW):
    Java Code:
    public class FWTest {
      public static void main(String[] args){
        int X = Integer.MAX_VALUE;
        
        int[][] distance =
        {
          {0,X,X,X,5,12},
          {15,0,9,X,X,X},
          {X,X,0,5,X,X },
          {X,2,X,0,X,X },
          {X,X,10,X,0,4},
          {X,X,17,20,X,0}
        };
        
        int[][] previous = FloydWarshall.get(distance);
        System.out.println("\nDistances:");
        display('d', distance);
        System.out.println("\nPrevious:");
        display('p', previous);
      }
      
      public static void display(char type, int[][] matrix){
        for(int i=0; i<matrix.length; ++i){
          for(int j=0; j<matrix[i].length; ++j)
            if(type=='p'){
              System.out.print((char)(matrix[i][j]+'A') + "  ");
            }
            else System.out.print(matrix[i][j] + "  ");
          System.out.println();
        }
        System.out.println();
      }
    }
    and the output:
    Java Code:
    Distances:
    0  22  15  20  5  9
    15  0  9  14  20  24
    22  7  0  5  27  31
    17  2  11  0  22  26
    32  17  10  15  0  4
    37  22  17  20  42  0
    
    Previous:
    A  D  E  C  A  E
    B  B  B  C  A  E
    B  D  C  C  A  E
    B  D  B  D  A  E
    B  D  E  C  E  E
    B  D  F  F  A  F
    But I have no idea if this is correct since I don't have data to check against. I checked this against an applet from:
    Dijkstra's Shortest Path Algorithm
    and it seems correct, though I can't be certain...
    Attached Thumbnails Attached Thumbnails number unstableness-shortestpath.jpg  
    Last edited by angryboy; 07-13-2009 at 07:47 AM. Reason: renamed prev to pred, added comments
    USE CODE TAGS--> [CODE]...[/CODE]
    Get NotePad++ (free)

Similar Threads

  1. Replies: 1
    Last Post: 08-07-2009, 01:14 PM
  2. autogenerate the number
    By Shivraj in forum NetBeans
    Replies: 0
    Last Post: 03-17-2009, 05:57 PM
  3. why the number will not increase?
    By rayda in forum New To Java
    Replies: 3
    Last Post: 03-16-2009, 06:47 AM
  4. Replies: 1
    Last Post: 11-03-2008, 03:38 PM
  5. Random number
    By jithan in forum Advanced Java
    Replies: 1
    Last Post: 06-13-2008, 02:42 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •