Discussion :

[allserv]

Bonjour,

Je sais que vu le titre cela n'est pas très explicite, je vais essayer de vous détailler mon problème.
Tout cela correspond à un programme qui doit donner le plus court chemin entre deux sommets d'un graphe valué .

Ma structure est ceci :

Code :

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

private HashMap<Sommet,TreeSet<Arc>> graphe;

J'ai donc une classe Sommet qui contient :

Code :

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

1
2
private String nom; 
	private int plusCourt; // valuation associé au sommet

Et une classe Arc :

Code :

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

1
2
private Sommet arrivee;
	private int poids;

J'ai crée tous les sommets et tous les arcs. J'ai entré dans la hashmap pour chaque sommet les arcs associés.
Tout cela fonctionne à merveille !

Maintenant je souhaite modifier l'attribut plusCourt pour tous les sommets contenus dans le hashmap.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
for(Sommet s: graphe.keySet()){
 
			if(s.getNom()==depart)
			{
				sommetDepart = s;
				s.setPlusCourt(0);
 
			}
			else
			{
				s.setPlusCourt(3000);	
			}
		}

Et en fait après avoir executé ce code, lorsque je parcours toutes les clés pour afficher la valeur, je n'ai que des null ?!? Logiquement si je modifie une clé elle devrait garder sa valeur associé dans le hashmap ?

Merci de m'éclairer la dessus.

Louis

[®om]

Code :

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

if(s.getNom()==depart)

o_O

Pas de comparaison == sur des chaînes

Ton "null" tu l'as où précisément?

[allserv]

En fait j'ai mis ce bout de code avant et après le traitement :

Code :

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

1
2
3
4
5
6
7
TreeSet<Arc> tmp;
		for(Sommet s:  graphe.keySet()){
 
 
			tmp =graphe.get(s);	
					System.out.println(tmp);
		}

Il s'avere que avant tout est correct, et après j'ai un affichage avec des null !

[adiGuba]

Salut,


Les objets utilisé en clef dans les Map devraient être immuable : si leurs valeurs changent il y a de forte chance qu'il soit impossible de les retrouver...

C'est d'ailleurs indiqué dans la javadoc : http://javasearch.developpez.com/j2s.../util/Map.html

Note: great care must be exercised if mutable objects are used as map keys. The behavior of a map is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is a key in the map.

C'est comme si tu change de clef : tu ne peux plus ouvrir ta porte

a++

[allserv]

Merci pour ta réponse,

j'ai donc décider de modifier mon code pour supprimer l'entrée associée à l'ancienne clé et ajouter la nouvelle de cette manière

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
for(Sommet s: lesKey){
			Sommet tmpSomm = s;
			TreeSet<Arc> tmpTree = graphe.get(s);
 
			if(s.getNom().equals(depart))
			{
				sommetDepart = s;
				s.setPlusCourt(0);
				graphe.remove(tmpSomm);
				graphe.put(s, tmpTree);
 
			}
			else
			{
				s.setPlusCourt(3000);
				graphe.remove(tmpSomm);
				graphe.put(s, tmpTree);
			}
		}

Mais là j'ai une belle erreur :
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.HashMap$HashIterator.nextEntry(Unknown Source)
at java.util.HashMap$KeyIterator.next(Unknown Source)
at Graphe.calcul(Graphe.java:74)
at Application.main(Application.java:82)

La je dois avouer que c'est la première fois que je la rencontre et je suis perdu ! Est-ce la bonne méthode à faire ?

Merci encore pour votre aide

[adiGuba]

Lorsque tu parcours une collections avec un itérateur (ce qui est utilisé lorsque tu utilises la boucle for étendu), tu ne dois pas modifier la collection en même temps (sauf si tu passe par les méthodes de l'itérateur).

Donc utilise une Map temporaire

a++

[allserv]

D'accord, mais meme en rajoutant cela ca ne fonctionne pas :

Code :

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

1
2
3
 
HashMap<Sommet,TreeSet<Arc>> mapTmp = graphe;
Set<Sommet> lesKey = mapTmp.keySet();

Cela vient du fait que ca référence les memes objets en mémoire ?
Il faudrait que j'en crée de nouveau ?

Merci d'avance pour ton aide précieuse

[adiGuba]

Cela vient du fait que ca référence les memes objets en mémoire ?
Il faudrait que j'en crée de nouveau ?

Oui et oui : tu ne crée pas une Map temporaire mais une seconde référence sur la même Map...

a++

[allserv]

Désolé c'est encore moi, en, fait je viens de me rendre compte que après je remodifie encore les sommets :

Code :

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

1
2
3
4
5
6
7
8
9
 
TreeSet<Arc> tmp=graphe.get(sommetDepart);	
 
		for(Arc a: tmp){
 
			if(sommetDepart.getPlusCourt()+a.getPoids()<a.getArrivee().getPlusCourt()){					
				a.getArrivee().setPlusCourt(sommetDepart.getPlusCourt()+a.getPoids());
			}
		}

EN effet dans les arc cela contient un sommet qui est l'attribut arriive et je modifie l'attribut plusCourt.

Le mieux dans ce cas ne serait pas que je fasse un tableau avec les noms des sommets et leur valeur plusCourt ?

Comment faire un tableau avec une colonne de String et en valeur des int ?

Merci encore

[allserv]

C'est bon mon problème est resolu, il suffisait d'adapter le bon hashcode sur le nom et non sur les deux attributs comme ca ca ne le prenait pas come une nouvelle clé

Un autre petit problème tout bete mais dont je ne trouve pas la solution

Dans mon TreeSet d'arc, lorsque j'ai deux Arc différents mais avec le meme poids, le dernier arc n'est pas ajouté :

Code :

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

1
2
3
4
5
6
7
8
 
Arc AB = new Arc(B,1);
Arc AD = new Arc(D,2);
Arc AC = new Arc(C,1);
 
monGraphe.ajoutArc(A,AB);
monGraphe.ajoutArc(A,AD);
monGraphe.ajoutArc(A,AC);

Dans cet exemple je n'ai pas l'arc AC par exemple !

Pourtant j'ai defini le hashcode sur le sommet d'arrivée qui diffère donc devrait pas y avoir de problème :

Code :

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

1
2
3
4
5
6
7
 public int hashCode() {
	        return arrivee.hashCode();
	 }
 
	 public boolean equals(Arc monArc){
		 return (monArc.arrivee.equals(this.arrivee) && monArc.getPoids()==this.poids);
	 }

Et le hashcode du sommet est :

Code :

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

1
2
3
4
5
6
7
 public int hashCode() {
	       return nom.hashCode();
	    }
 
	 public boolean equals(Sommet otre){
		 return otre.getNom().equals(this.nom);
	 }

Comment faire pour résoudre ce dernier problème ?

Je te remercie encore pour tes reponses