Exception in thread "main" java.lang.StackOverflowError Arbol binario backtracking

Question

I have the next error:// Hola, tengo el siguiente error:

Note: I know that is memory error, but I wanna know how to fix it, thnx.

#javac Resol.java

#java Resol
Exception in thread "main" java.lang.StackOverflowError
    at Nodo.<init>(Nodo.java:17)
    at Nodo.<init>(Nodo.java:17)
    at Nodo.<init>(Nodo.java:17)
    at Nodo.<init>(Nodo.java:17)
    at Nodo.<init>(Nodo.java:17)
    at Nodo.<init>(Nodo.java:17)
    at Nodo.<init>(Nodo.java:17)
    at Nodo.<init>(Nodo.java:17)
    at Nodo.<init>(Nodo.java:17)... to inf...

this is the Resol class:

import java.util.*;
import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;
import java.util.Random;
import java.lang.Math;
import java.lang.*;

public class Resol{

    public static int cantVar;
    public static  int cantRest;
    public ArrayList<Nodo> lista;
    public static int[] costs = {65,55,60,45,40,50};
    public static int[][] matriz= {
    {1,1,0,0,0,0},
    {1,1,0,0,0,1},
    {0,0,1,1,1,0},
    {0,0,0,1,0,1},
    {0,1,0,0,1,1},
}; //matriz de restricciones

    public Resol(){
        this.cantVar=6;
        this.cantRest=5;
        this.lista = new ArrayList<Nodo>();
        this.costs=costs;
        this.matriz=matriz;

}


public static Nodo iniciarNodo(Nodo l, int i){
    if(l.inic==false){
        l.anterior=l;
        l.inic=true;
    }else{
        if(l.izq.inic==false){
            l.izq=new Nodo();
            l=l.izq;
            l.anterior=l.anterior.anterior;

        }
    }

    l.solucion.add(i);
    return l;
}

public static void esSolucion(Nodo l){
    Resol r = new Resol();
    r.lista.add(l);
    ListIterator it;
    it=l.solucion.listIterator();
    while(it.hasNext()){
        System.out.println("datos: "+ it.next());
    }

}




public static boolean esFactible(ArrayList<Integer> l){
    ListIterator it;
    //int suma;
    boolean cumple=false;

    for(int i = 0; i < cantVar; i++){
        it=l.listIterator();
        int j=0, suma=0;
        while(it.hasNext()){
            if(l.size() < cantVar){

                if((int)it.next()!=matriz[j][i]){
                    suma = suma +1;

                }
                j++;

            }
            if(suma==cantRest){
                break;

            }else{
                return false;
            }   

        }
    }

    return true;
}

public static void volver(Nodo l){
    if(l.der!=null){
        volver(l.anterior);
    }else{
        Backtrack(l.der, 1);
    }

    return;
}


public static void agregar(Nodo l, int i){
    if(l==null){
        agregar(iniciarNodo(l, i),i);
    }else{
        if(l.solucion.size()<1){
            l.solucion = l.anterior.solucion;
            l.solucion.add(i);
        }

    }
}

public static void Backtrack(Nodo l,int i){
    if(l != null && l.inic==false){
        Backtrack(iniciarNodo(l, i), i);

    }else{
        if(esFactible(l.solucion) && l.solucion.size()==cantVar){
            esSolucion(l);
            volver(l.anterior);
            return;
        }
        //l.solucion.add(0);
        //agregar(l, i);
        if(esFactible(l.solucion)){

            agregar(l, i);
        }else{
            //Backtrack(l.anterior.izq, 1);
            Backtrack(l.anterior.der, 1);
        }

    }


}

    public static void main(String[] args){
        //ArrayList<Integer> sol = new ArrayList<>();
        Nodo sol;
        sol = new Nodo();
        System.out.println("esto hay: "+ sol.inic);
        Resol resol;
        resol = new Resol();
        //SetCoverProblem scp = SetCoverProblem.getInstance();
        resol.Backtrack(sol, 0);

    }



}

And this is the Nodo class:

   import java.util.ArrayList;
   import java.util.List;
   import java.util.ListIterator;
   import java.util.Random;
   import java.lang.Math;
   import java.lang.*;

public class Nodo{
    public Nodo izq;
    public Nodo der;
    public Nodo anterior;
    public long fitness;
    public boolean inic;
    public ArrayList<Integer> solucion;

public Nodo(){
    izq = new Nodo();
    der = new Nodo();
    this.fitness = 0;
    this.inic = false;
    this.solucion = new ArrayList<Integer>();

}

public Nodo getIzq(){
    return izq;
}

public Nodo getDer(){
    return der;
}

public Nodo getAnt(){
    return anterior;
}

public void setIzq(){
    this.izq=izq;
}

public void setDer(){
    this.der=der;
}

public void setAnt(){
    this.anterior=anterior;
}

}

every help will be usefull

yes, i already change it, thnx – Gonzalo Adolfo Simpson Arancib Jun 30 '17 at 19:27 — Gonzalo Adolfo Simpson Arancib, Jun 30 '17 at 19:27
Nodo creates a Nodo, which creates a Nodo, .... etc – Mark Rotteveel Jul 01 '17 at 07:08 — Mark Rotteveel, Jul 01 '17 at 07:08

score 2 · Answer 1 · answered Jun 30 '17 at 19:21

2

Look at your constructor for the Nodo class.

public Nodo(){
    izq = new Nodo();
    der = new Nodo();
    this.fitness = 0;
    this.inic = false;
    this.solucion = new ArrayList<Integer>();

}

Do you notice that in the first two lines, you are again calling the same constructor? In other words, every constructor call first has to resolve a constructor call. That's an endless process; that's why you are getting a StackOverflowError. The stack trace points this out clearly by even telling you the line number.

Exception in thread "main" java.lang.StackOverflowError
    at Nodo.<init>(Nodo.java:17)
                              ^ Line number

answered Jun 30 '17 at 19:21

Kon

10,702
6
41
58

@Gonzalo I suggest you start here https://stackoverflow.com/questions/218384/what-is-a-nullpointerexception-and-how-do-i-fix-it – Kon Jun 30 '17 at 19:35
yes, I noticed that, btw, if I change the inicialitation of `izq=new Nodo();` to `this.izq=izq;` shows me this error: ` #java Resol esto hay: false Exception in thread "main" java.lang.NullPointerException at Resol.Backtrack(Resol.java:123) at Resol.Backtrack(Resol.java:135) at Resol.Backtrack(Resol.java:120) at Resol.main(Resol.java:151)` thnx btw @Kon – Gonzalo Adolfo Simpson Arancib Jun 30 '17 at 19:37
I replied before you deleted your comment, see the first comment in this chain. – Kon Jun 30 '17 at 19:37
thnx a lot @Kon – Gonzalo Adolfo Simpson Arancib Jun 30 '17 at 19:38

score 0 · Answer 2 · answered Jun 30 '17 at 19:39

I repeatedly see redundancies throughout your code, like the following constructor:

public Resol() {
    this.cantVar = 6;
    this.cantRest = 5;
    this.lista = new ArrayList<Nodo>();

    this.costs = costs;   // what's the point of this?
    this.matriz = matriz; // again, why?
}

I believe you're confused, or might not know, about parameters. For instance the above code would make since if the Resol constructor were:

public Resol(int[] costs, int[][] matriz) {
    this.cantVar = 6;
    this.cantRest = 5;
    this.lista = new ArrayList<Nodo>();

    this.costs = costs;   // set the class member 'costs' to the parameter 'costs'
    this.matriz = matriz; // set the class member 'matriz' to the parameter 'matriz' 
}

Similarly with the mutators in your Nodo class:

// what is the following setting izq to other than what it already is?
public void setIzq() {
    this.izq = izq;
}

Mutators are meant to mutate the members of a class, not reassign them to the same thing. For instance:

public void setIzq(Nodo izq) {
    this.izq = izq; // set the class member 'izq' to the parameter 'izq'
}

Would make more sense as a mutator. Then you can remove the assignments of izq = new Nodo() in your constructor, alleviating the StackOverflowError.

thnx, but that makes me do another solution, do it all again xd, but thnx very much — Gonzalo Adolfo Simpson Arancib, Jun 30 '17 at 20:55
@GonzaloAdolfoSimpsonArancib It's better to do it all again now, rather than later. You should really look into [data encapsulation](https://docs.oracle.com/javase/tutorial/java/concepts/object.html), it's an all around better approach compared to having everything public. — Jonny Henly, Jun 30 '17 at 21:08

Exception in thread "main" java.lang.StackOverflowError Arbol binario backtracking

2 Answers2