Discussion :

[LionHaze]

Bonjour,

Je cherche à implémenter le tas de Fibonacci en Java avec les collections standards de Java mais je rencontre un problème avec la méthode consolider.

J'ai une erreur du type IndexOutOfBounds pour array;

Fibonacci.java

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
 
public class Fibonacci {
    private static final double oneOverLogPhi =
        1.0 / Math.log((1.0 + Math.sqrt(5.0)) / 2.0);
        private Noeud min;
    private ArrayList<Noeud> racines;
    private int taille;
 
    public Fibonacci (){
        super();
        min = null;
        racines = new ArrayList<Noeud> ();
    }
 
    public Noeud findMinimum (){
        return min;
    }
 
    public static Fibonacci union (Fibonacci a, Fibonacci b){
        Fibonacci t =  new Fibonacci ();
        t.min = a.min;
        t.racines.addAll(b.racines);
        t.racines.addAll(a.racines);
        if (a.min == null | b.min !=null &  b.min.getClé() < a.min.getClé()){
            t.min = b.min;
        }
        t.taille = a.taille + b.taille;
        a = null;
        b = null;
        return t;
    }
 
    public void inserer (Noeud n){
 
       if (min == null || n.getClé() < min.getClé()){
           min = n;
       }
       taille += 1;
      racines.add(n);
    }
 
    private void relier (Noeud y, Noeud x){
        racines.remove(y);
        y.setPere(x);
        x.getEnfants().add(y);
        y.setMarque (false);
    }
 
    public void couper (Noeud x, Noeud y){
       y.getEnfants().remove(x);
       racines.add(x);
       x.setPere(null);
       x.setMarque(false);
    }
 
    public void couperEnCascade (Noeud y){
        Noeud z = y.getPere ();
        if (z != null){
            if (!z.estMarque()){
                z.setMarque(true);
            }
            else {
                couper(y, z);
                couperEnCascade(z);
            }
        }
    }
 
    public void diminueCle (Noeud x, Integer valeur) {
        if (valeur > x.getClé()){
            throw new Error("new key is greater than current key");
        }
        x.setClé(valeur);
        Noeud y = x.getPere();
 
        if (y != null && x.getClé() < y.getClé()){
            couper(x, y);
            couperEnCascade(y);
    }
        if (x.getClé() < min.getClé()){
            min = x;
        }
    }
 
    private void consolider (){
        //System.out.println(taille);
        int degreMax = ((int) Math.floor(Math.log(taille) * oneOverLogPhi)) + 2;
        //System.out.println(((int) Math.floor(Math.log(taille) * oneOverLogPhi)) + 1);
        List<Noeud> array = new ArrayList<Noeud> (degreMax);
 
        for (int i = 0; i < degreMax; i++){
            array.add(null);
        }
 
        int numRoots = racines.size();
        Noeud x = min;
 
        while (numRoots > 0) {
            int d = x.getEnfants().size(); 
 
            Noeud next = racines.get(racines.indexOf(x) + 1 == racines.size() ? 0 : racines.indexOf(x) + 1);
 
 
            for (;;) {
                System.out.println ( x + " d : " + d);
                Noeud y = array.get(d);
                if (y == null) {
                    // Nope.
                    break;
                }
 
                if (x.getClé() > y.getClé()) {
                    Noeud temp = y;
                    y = x;
                    x = temp;
                }
 
                this.relier(y, x);
 
 
                array.set(d, null);
                d++;
            }
 
 
            array.set(d, x);
 
 
            x = next;
            numRoots--;
        } 
 
        min = null;
        for (int i = 0; i < array.size(); i++){
            if (array.get(i) != null){
                racines.add(array.get(i));
                if (min == null || array.get(i).getClé()  < min.getClé()){
                    min = array.get(i);
                }
            }
        }
    }
 
 
    private void echanger (Noeud x, Noeud y){
        Noeud tmp = x;
        x = y;
        y = tmp;
    }
 
    public Noeud extraireMinimum(){
        Noeud z = min;
        if (z != null){
                for (Noeud enfant : z.getEnfants()){
                    enfant.setPere(null);
                    racines.add(enfant);
                }
                z.getEnfants().clear();
        }
        int index = racines.indexOf(z);
        racines.remove(z);
 
        if (racines.size() == 0){
            min = null;
        }else {
            min = racines.get(index+1);
            consolider();
        }
        taille--;
        return z;
    }
 
    public void supprimer(Noeud n){
 
        diminueCle(n, Integer.MIN_VALUE);
        extraireMinimum();
 
}
    boolean isEmpty (){
        return min == null;
    }
}

Noeud.java

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public class Noeud {
 
    private boolean marque;
    private Noeud pere;
    private LinkedList<Noeud> enfants;
 
    private Integer clé;
    private Integer donnée;
 
    public Noeud (int sommet,int valeur ){
        this.clé = valeur;
        this.marque = false;
        this.pere = null;
        enfants  = new LinkedList<> ();
        this.donnée = sommet;
    }
 
    public Integer getClé (){
        return clé;
    }
 
    public LinkedList<Noeud> getEnfants() {
        return enfants;
    }
 
    public void setMarque(boolean b) {
        this.marque = b;
    }
 
    public void setPere(Noeud pere) {
        this.pere = pere;
    }
 
    public Noeud getPere (){
        return pere;
    }
 
    public boolean estMarque (){
        return marque;
    }
 
    public void setClé(Integer valeur) {
        this.clé = valeur;
    }
 
   public Integer getDonnée (){
       return donnée;
   }
 
    @Override
   public String toString (){
       return new String (this.donnée+ " " + this.clé);
   }
}

Quelqu'un saurait-il m'indiquer d'où peut venir l'erreur ?

Merci d'avance pour votre aide.

[kinaesthesia]

Bonjour,

Peux-tu nous donner la stacktrace entière s'il te plait ?

Merci d'avance,

Kinaesthesia

[LionHaze]

Merci de t’intéresser à mon problème, kinaesthesia.

Voici la stack trace demandée :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 11, Size: 11
	at java.util.ArrayList.rangeCheck(ArrayList.java:604)
	at java.util.ArrayList.get(ArrayList.java:382)
	at nf20.graphe.Fibonacci.consolider(Fibonacci.java:113)
	at nf20.graphe.Fibonacci.extraireMinimum(Fibonacci.java:174)
	at nf20.graphe.Graphe.PrimFIbonnachi2(Graphe.java:676)
	at nf20.graphe.Graphe.main(Graphe.java:743)
Java Result: 1

Je précise que j'utilise le tas de Fibonacci pour faire un arbre couvrant avec algorithme de Prim dont voici l'algorithme

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 
  Graphe retour = new Graphe ();
            retour.sommets.addAll(this.sommets);
            Fibonacci f = new Fibonacci ();
 
            HashMap<Integer,Noeud> aTraité = new HashMap<> ();
            Integer pere[] = new Integer [this.sommets.size()];
 
 
            for (int s : retour.getSommets()){
                Noeud n = new Noeud(s, Integer.MAX_VALUE);
                if (s == sommet){
                    n.setClé(0);
               }
                f.inserer(n);
 
                aTraité.put(s,n);
            }
 
 
            while (!f.isEmpty()){
                Noeud s = f.extraireMinimum();
 
                aTraité.remove(s.getDonnée());
                for (int z : this.adjacent(s.getDonnée())){
                    Arete a = find(s.getDonnée(),z);
                    if (aTraité.get(z) != null && a.getPoids() < aTraité.get(z).getClé() ){
                        f.diminueClé(aTraité.get(z) , a.getPoids());
                        pere[z] = new Integer(s.getDonnée());
                    }
                }
            }
 
            for (int i = 0; i < pere.length; i++){ 
 
                if (pere[i] != null) {
                    retour.aretes.add(this.find(i, pere[i]));
                }
            }
            return retour;
        }

[kinaesthesia]

Merci.

Le problème vient de cette ligne : Noeud y = array.get(d);

En effet vu que tu boucle avec un for(;;) { ... } (et c'est trèèèèèèsss mal ), tu essayes d'accéder a un espace mémoire non autorisé car ta liste n'est pas illimitée.

Ici tu devrais plutôt changer par ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
for ( ;;) {
  System.out.println ( x + " d : " + d);
  if(d >= array.size()) {
    break
  }
  Noeud y = array.get(d);
  if (y == null) {
    // Nope.
    break;
  }

Attention, je ne corrige que ton erreur et non pas ton algorithme ni même le code qui est vraiment laid (mais je suppose que tu débute en Java ^^ ).

[LionHaze]

Malheureusement, cela ne marche pas (Même avec le point virgule).

Je me suis basé sur l'implémentation du tas de Fibonacci qui est faite avec dans JGraphT.

Voici les liens vers les fichier qui concerne mon problème
Leur tas de Fibonacci

Les noeuds composants leur tas de fibonacci

Pour information voici comment je stocke le graphe

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
public class Graphe {
	private TreeSet<Arete> aretes;
 
 
	private boolean oriente;
 
	private TreeSet<Integer> sommets;
}