Discussion :

[francois83]

Bonjour,

alors je vous expose mon problème, dans le logiciel sur lequel je travaille nous traitons des données (jobs) qui peuvent être affiliées entre elles. Or je rencontre un soucis, sur certaines données les filiations sont incorrectes et provoquent des boucles infinies. La solution la plus simple serait de supprimer ces boucles mais le but de mon programme n'est pas là, dans mon cas je veux simplement ignorer les données où il y des boucles.
J'ai fait plusieurs tentatives mais je ne rentre pas dans tous les cas.

Voici un exemple de données :
Cas 1 : (Boucle entre JOB1 et JOB2)
JOB1 : JOB2 | JOB3
JOB2 : JOB1 | JOB3

Cas 2 : (double Boucle entre JOB4 et JOB1 et job 4 et job 2)
JOB1 : JOB2|JOB3
JOB2 : JOB4|JOB5
JOB4 : JOB1|JOB2

Cas 3 : (Pas de boucle)
JOB 1 : JOB2|JOB3
JOB 2 : JOB4|JOB5
JOB 3 : JOB6|JOB7
JOB 4 : JOB3

Je vous joins un schéma pour bien comprendre le système de hiérarchie.
Le boucles apparaissent en rouge. (voir pièces jointes)


Le but est donc de déterminer s'il existe au moins une boucle dans ces filiations.

Je vous remercie d'avance pour votre aide !

[kwariz]

Bonjour,

pour détecter une boucle dans ton graphe le plus simple est d'en faire un parcours en profondeur d'abord (par exemple) en marquant chaque noeud visité, si tu rencontres un noeud marqué alors il y a une boucle.

[francois83]

Bonjour,

pour détecter une boucle dans ton graphe le plus simple est d'en faire un parcours en profondeur d'abord (par exemple) en marquant chaque noeud visité, si tu rencontres un noeud marqué alors il y a une boucle.

OK je vois bien pour les cas 1 et 2 où j'ai des boucles, par contre pour le cas 3 où je n'en ai pas, si je parcours ma hiérarchie, je vais passer deux fois sur le JOB3 et pourtant je n'ai pas de boucle...

[kwariz]

J'ai effectivement répondu un peu vite ...
Dans le cas orienté on peut utiliser un algorithme du type, avec L la liste des jobs :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
cycle_existe(L)
début
  tant que L n'est pas vide
    si L contient une feuille F // = un job sans fils
      supprimer F et tous les liens entrants
    sinon
      retourner Vrai // il y a au moins un cycle
    fin si
  fin tant que
  retourner Faux // il n'y a aucun cycle
fin

[pseudocode]

OK je vois bien pour les cas 1 et 2 où j'ai des boucles, par contre pour le cas 3 où je n'en ai pas, si je parcours ma hiérarchie, je vais passer deux fois sur le JOB3 et pourtant je n'ai pas de boucle...

Il faut traiter chaque parcours indépendamment.

Il y a une boucle si et seulement si, pour un parcours donné, tu repasses par un noeud déjà marqué. Si le noeud a été marqué par un autre parcours, ca ne compte pas.