Discussion :

[Raikyn]

Salut !

Dans le but de comprendre les graphes je suis à la recherche d'une implémentation "simple" d'un type Graphe (non orienté, sans cycles) en Java (c'est le seul langage que je maitrise ).
Aussi si vous avez une implémentation du parcours en profondeur, je serai ravis ^^
Ce que je cherche à faire avec ça c'est d'une part comprendre mieux les algo avec des exemples concrets et d'autre part tester plusieurs cas de figure afin de mieux appréhender certains exercices d'algo.


J'ai trouvé sur le net des implémentations mais elles sont soit très compliquées soit incomplètes.
Et j'ai moi-même essayé de programmer un type Graphe (une implémentation avec un tableau des successeurs pour chaque sommet, une autre avec des liste) mais quand je m'essaye au parcours en profondeur je me rend compte que mes structures ne marcheront pas...


Donc voilà, si vous avez l'implémentation que je recherche merci de me la faire partager ici !


Merci d'avance.

[tchize_]

Vu que ton graphe est non orienté, une implémentation basique d'un type Graphe ressemblerait à ça:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
public void Node {
   private Set<Node> liste = new HashSet<Node>();
   public Set<Node> getVoisins(){return Collections.unmodifiableSet(liste);}
   public void addVoisin(Node voisin){
       liste.add(voisin);
       voisin.liste.add(this);
   }
   public void removeVoisin(Node voisin){
       liste.remove(voisin);
       voisin.liste.remove(this);
   }
}

Après, bien sur, tu ajoute tout ce que tu veux pour y mettre des valeur, des poids sur les relations si tu veux un graphe avec des poids, etc.

[Raikyn]

Ce que tu propose c'est que chaque sommet a une liste d'autre sommet en gros ?
C'est ce que j'avais fais, sauf que j'ai utilisé des tableaux. Le truc c'est que pour parcourir ou pour trouver tout les chemins c'est un peu compliqué
Je dois surement mal m'y prendre...

Merci pour la réponse, je vais essayer de coder une implémentation du parcours de tout les chemins en utilisant cette structure qui m'a l'air plus "propre".

[thelvin]

Ben, c'est compliqué... Oui c'est un peu pour ça qu'on enseigne l'algorithmique des graphes. Pour apprendre à résoudre des problèmes qui ne sont pas a priori évidents...

[tchize_]

Le truc c'est que pour parcourir ou pour trouver tout les chemins c'est un peu compliqué

Ben, en mode naif, tu parcoure récusivement, en maintenant un Set des noeuds déjà visités pendant le parcours.

[thelvin]

Et quand on a pas encore appris à utiliser des sets :
on fait en sorte que chaque sommet d'un graphe a un numéro unique. De 0 à N-1, N étant le nombre de sommets dans le graphe. (Il faut donc ajouter ce numéro à la classe Node.)

Pour savoir quels sommets ont été visités, on garde un tableau de booléens de taille N, qui indique pour chaque indice i, si le sommet de numéro i a été visité ou pas.

[Raikyn]

Vous auriez un algo pour faire tout les chemins possibles dans un graphe ? J'ai essayé avec le parcours en profondeur mais ça ne marche pas très bien...

[tchize_]

Vous auriez un algo pour faire tout les chemins possibles dans un graphe ? J'ai essayé avec le parcours en profondeur mais ça ne marche pas très bien...

Ben montre nous ce que t'as fait. A priori, l'implémentation native est un simple algorithme récursif.

[Raikyn]

En fait, j'ai utilisé les List car je suis plus familier avec ce type qu'avec les Set. Mon programme marche bien, mais le seul soucis c'est que j’atteins le maximum dans ma liste ArrayList qui stocke tout les chemins possibles (sans cycles) à partir d'un certain sommet.
Je dois mettre 24 sommets dans mon graphe mais ça ne peut pas dépasser le sommet 15 :/

Devrais-je me pencher sur les Set où je dois-je séparer mon ArrayList en deux?

[tchize_]

Quel maximum? Les Listes n'ont pas de taille maximum. Si tu commençais par nous mettre le code que tu as utilisé et qui pose problème?

[Raikyn]

..

[tchize_]

ok, tu crée beaucoup trop de liste. En effet, tu stocke aussi toutes les listes intermédiaires, que tu duplique à chaque fois (afin d'en avoir d'autres). Du coup tu sature ta mémoire avec des tonnes de listes.


Première chose: évaluer la taille de mémoire dont tu as besoin. As-tu déjà regardé combien de chemin tu peux générer dans ce graphe? Au delà d'une certains quantité de sommet, ça va commencer à exploser.


Là je te renvoie à la théorie des graphes pour calculer combien ton graphe à de combinaisons de parcours possibles.

Ensuite, comme je le disais, tu crée trop de liste. Dès tu tombe sur un nouveau noeud, tu crée une nouvelle liste que tu stocke. Donc si on prend un graphe à 4 points, tous reliés entre eux, et en partant de A, tu va stocker

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
A
 A B
  A B C
   A B C D
  A B D
   A B D C
 A C
  A C B
   A C B D
  A C D
   A C D B
 A D
  A D B
   A D B C
  A D C
   A D C B

Alors que, a priori, ce qui t'intéresse, c'est
A B C D
A B D C
A C B D
A C D B
A D B C
A D C B


Donc 16 listes contre 6 listes recherchées ...

Je propose d'adapter ton code comme ceci, qui a en plus l'avantage de réutiliser la liste en cours de construction. C'est une implémentation de base, on peux aussi modifier la boucle pour détecter les "cul de sac" plutot que d'attendre d'y être

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
 
 
    public void examiner(List<Sommet> liste, List<List<Sommet>> total){
    if(!liste.contains(this)){
        liste.add(this);
 
        Iterator i = this.voisins.iterator();
 
        while(i.hasNext()){
          Sommet x = (Sommet)i.next();
          x.examiner(nouvelle,total);
        }
        liste.remove(this); // on a fini, on se retire avant de sortir de l'appel   
    } else if (liste.size() == tailleDuGraphe)
        // on est en fin de liste, Est-ce qu'elle est bonne?
        total.add(new ArrayList<Sommet>(liste));
    }

[tchize_]

JE rajoute aussi parce que j'avais pas tilté.
Tu as mis 24 sommet. Le parcours de tous les chemins possible ddans un graphe de N sommet où tous sont reliés entre eux, en y allant de manière naive, est de l'ordre de O(n!)


Autrement dit, tu va créer potentiellement avec ton code de l'ordre de 10^23 listes.

Bon ici, il n'y a pas autant de liaisons entre les sommet, mais ça peu être grand quand même... à garder à l'oeil.

[Raikyn]

En fait j'ai vraiment besoin de tout les chemins, même ceux de longueurs < à 24 :/
Le but final de mon projet c'est de trouver tout les vrais mots parmi cette liste.

Je suis conscient que c'est très volumineux, aussi je pense que je vais modifier mon programme tel que je supprime la liste quand je l'ai utilisée. Ou sinon j'utilise ton morceau de code et je vérifie les mots de longueurs 2 puis 3 etc... jusqu'à 24.

[tchize_]

Le but final de mon projet c'est de trouver tout les vrais mots parmi cette liste.

Alors, il faut le faire pendant ton parcours, pour ne pas avoir à stocker les résultat. Ca a plusieurs avantage:

si le chemin déjà parcouru ne correspond au début d'aucun mot -> tu peux arrêter sans aller au fond
tu n'a pas besoin de stockage

[Raikyn]

Oui bien vu, je vais procéder comme ça.

Merci pour l'aide !