Construction d'une arborescence

Récursivité

Sujet résolu

Anonyme

24 juin 2008 à 14:46:43

Bonjour !

Je viens ici pour vous exposer mon problème actuel. Celui-ci consiste en la construction d'une arborescence. Je m'explique !

L'application que je suis en train de développer implante un système de produits liés, c'est à dire que pour pouvoir fabriquer un produit on a besoin d'autres produits. La structure de la table de ma base de données stockant ces liaisons est la suivante :

produit_id_est_compose : l'identifiant du produit "final"
produit_id_compose : l'identifiant du sous produit

Il faut savoir que cette liaison peut s'effectuer sur plusieurs niveaux. Un premier sous produit peut également avoir des sous produits, par exemple :

1 -- 2
1 -- 3
3 -- 4
4 -- 5
3 -- 6
1 -- 7

Vous l'aurez probablement compris mon problème viens du fait que je n'arrive pas à récuperer l'arborescence des produits. J'ai essayé de définir une méthode récursive mais cela ne fonctionne pas et malgré les heures que j'ai passé à essayer de comprendre je n'ai pas trouvé comment mettre en place cette méthode. A moins que je soit obligé de passer par une autre méthode ?

Je viens donc vous demander votre aide. Et je remercie d'avance les personnes qui pourront m'aider à résoudre ce problème.

millie

24 juin 2008 à 16:41:24

Tu t'y connais en théorie des graphes ?

C'est en fait très proche d'un parcours de graphe avec comme entrée l'ensemble des dépendances (sommet, ensemble des fils)

Par contre, il est nécessaire d'effectuer une requête au minimum par sommet du graphe, donc si le graphe est très gros, les performances peuvent être plombées rapidement.

QuentinC 2

24 juin 2008 à 16:57:34

Peut-être que tu aurais intérêt à utiliser la représentation intervalaire pour ta table. Tuto php sur le site mais le principe est le même, fais une recherche.

Anonyme

24 juin 2008 à 17:04:28

@millie : je fais exactement ce que tu me dis. Je prends le premier sommet, je récupère ses fils et sur chaque fils (qui deviens un sommet) je relance la méthode. Avec donc utilisation d'une méthode récursive. Mais je ne pas pourquoi cela ne fonctionne pas. Et je sais que si le graphe est conséquent les performances seront plombées, mais ça n'est pas un souci pour l'instant.

@QuentinC 2 : le problème c'est que je n'ai pas le temps de me pencher sur la représentation intervallaire. On m'a demandé d'ajouter cette fonctionnalité pour demain donc je n'ai pas trop de temps à me consacrer à cette étude.

millie

24 juin 2008 à 17:38:34

Citation : Sulimo

<position valeur="justifie">@millie : je fais exactement ce que tu me dis. Je prends le premier sommet, je récupère ses fils et sur chaque fils (qui deviens un sommet) je relance la méthode. Avec donc utilisation d'une méthode récursive. Mais je ne pas pourquoi cela ne fonctionne pas. Et je sais que si le graphe est conséquent les performances seront plombées, mais ça n'est pas un souci pour l'instant.

Attention, il faut utiliser des sommets marqués pour savoir si le sommet a déjà été visité ou non.

Imaginons que tu disposes d'une fonction recupererEnfant(S) qui donne l'ensemble des ensembles d'un sommet. L'algorithme pourrait être le suivant :

/**
 * L'algorithme pourrait même supprimer sommetsVisite et utiliser uniquement mapSommet)
 */
void visiterSommet(Sommet s, Map<Sommet, Set<Sommet>> mapSommet, Set<Sommet> sommetsVisite) {
  if(sommetsVisite.get(s) ==null) //si déjà visité, on ne visite pas une nouvelle fois
     return;
  sommetsVisite.add(s);
  
  Set<Sommet> fils = recupererEnfant(s);
  mapSommet.put(s, fils);
  
  for(Sommet enfant : fils)
    visiterSommet(enfant, mapSommet, sommetsVisite);  
}

Le Map mapSommet contient l'ensemble des associations (pere, ensemble des fils).

A appeler avec : visiterSommet(unsommet, new HashMap<Sommet>(), new HashSet<Sommet>()) par exemple

Il y a d'autres méthodes où l'on construit directement l'arborescence, dans ce cas la map disparait mais l'ensemble des sommets visités restes.

Anonyme

25 juin 2008 à 18:49:01

Je passe mon problème en résolu car j'ai réussit à définir correctement ma méthode récursive.