Discussion :

[shawn12]

Bonsoir à tous
Je voudrais rechercher un cycle dans un arbre
J'ai une liste parent/enfant dans Excel. Comment dois-je faire pour détecter une boucle ?

[Sylvain Togni]

Par définition un arbre ne possède pas de cycle. Il doit donc plutôt s'agir d'un graphe. Dans ce cas un simple parcours en largeur ou en profondeur permet de savoir s'il y a un cycle, en marquant les noeuds visités.

[ToTo13]

Bonjour,

par définition un arbre est connexe minimal et acyclique maximal. C'est-à-dire que si tu enlèves n'importe quelle liaison, ce n'est plus un arbre, car une partie est détachée et si tu ajoutes une liaison cela devient un graphe.
Ca c'était pour la définition d'un arbre.

Pour ce qui est de ton problème, je te conseille de faire une recherche récursive. Tu parcours tous les nœuds et le feuilles de l'arbre en les marquant. Si tu parcours quelque chose déjà marqué, c'est que tu n'as pas un arbre, mais un graphe.

[millie]

Je te redis ce que j'avais dit hier. Tu parles de relation père/fils dans le fichier ce qui fait penser que tu as affaire à un graphe orienté et non à un arbre (graphe non orienté sans cycle). Ici tu parles de boucle, mais je pense que tu veux parler de cycle.

Au début, tu dois constuire le graphe à partir du fichier Excel.

Une méthode simple consiste à avoir une table d'association (genre table de hachage) qui contient en clef un sommet et en élément l'ensemble de ses enfants.

Ceci se faisant simplement avec un algorithme du type :

Code :

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

1
2
3
4
5
6
 
Map m : table d'association
Pour chaque L ligne du fichier
   Si(m.get(L.parent) == null) 
       m.put(L.parent, nouvel ensemble);
   m.get(L.parent).ajouter(L.fils);

Ensuite, tu as ton graphe entier et tu peux commencer le parcours de tous les sommets sur chaque sommet => il est possible d'être malin en retirant les sommets déjà visités pour éviter de reparcourir les sommets qui ont été inclus dans des parcours précédents.

Pour chaque tentative, il faut mémoriser le sommet de départ et si tu tombes dessus, tu arrêtes => c'est qu'il y a eu un cycle.

[SpiceGuid]

Dans ce cas un simple parcours en largeur ou en profondeur permet de savoir s'il y a un cycle, en marquant les noeuds visités.

Oui, mais il faut retirer le marquage quand tu quittes un chemin, sinon un simple parcours en profondeur avec marquage systématique ne permet que de savoir si tu as affaire à un arbre ou bien une forêt (un noeud partagé).

Pour chaque tentative, il faut mémoriser le sommet de départ et si tu tombes dessus, tu arrêtes => c'est qu'il y a eu un cycle.

[shawn12]

Mon problème n'est pas en soit de construire un arbre ou un graphe.

Je vous l'explique concrètement : j'ai une liste de programmes présentée de la manière suivante :

Code :

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

1
2
3
4
5
6
7
 
APPELANT     APPELE
2BSL201     0BDOSS
2BSL201     2BSL204
2BSL204     2BSL207
2BSL207     2BSL201
....           ....

Cette indique quels programmes sont appelés par un programme.

Il faut que je trouve s'il y a un cycle : ici par exemple 2BSL201-->2BSL204-->2BSL207--->2BSL201

Mais la liste peut etre longue.

Si j'ai bien compris, il faut que je parcoure à partir de chaque appelant la liste de ses appelés puis ainsi de suite, récursivement, jusqu'à retomber sur un programme déjà parcouru ?

[millie]

Je paris que c'est des programmes COBOL déployé sur des mainframes ?

[shawn12]

Oui, bravo ! Ce sont bien des programmes COBOL, déployé sur Mainframe et aussi sur serveurs UNIX.
Comment as-tu deviné ?

[millie]

Oui, bravo ! Ce sont bien des programmes COBOL, déployé sur Mainframe et aussi sur serveurs UNIX.
Comment as-tu deviné ?

J'ai bossé sur une application Web Java EE qui permettait de visualiser les graphes de dépendances (soit sous forme d'arbre, soit sous forme de graphe généré automatiquement) de programme mainframe à partir d'une base de donnée qui contenait des couples (enfant, parent, type d'appel (CALL-DYNA etc.)), et le but était de visualiser l'impact d'un programme sur un autre et de détecter des erreurs possibles de dépendances cycliques entre les programmes.

Mais il y avait toujours une entrée saisi par l'utilisateur (un programme à vérifier) car il y avait de l'ordre de 100.000 programmes cobol.

Indépendemment de ça, j'ai également bossé sur une appli Web qui devait compiler des programmes de manière distribué (donc il était nécessaire de définir les graphes de dépendances pour savoir quel module compiler avant les autres et de refuser la compilation en cas de dépendances cycliques)