Détection boucle filiation

Version imprimable

02/11/2012, 15h02
francois83

1 pièce(s) jointe(s)

Détection boucle filiation

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 !
02/11/2012, 15h34
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.
02/11/2012, 15h58
francois83

Citation:

Envoyé par 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.

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...

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:

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

02/11/2012, 16h16
pseudocode

Citation:

Envoyé par francois83

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.