Tri topologique de graphes - trouver et autocorriger les cycles

Bonjour,

Dans une application, j'ai une partie de la configuration qui permet de configurer une liste de composants. Un composant est décrit en résumé comme ceci :

• un identifiant obligatoire
• un identifiant faculatif de composant avant lequel ce composant doit s'exécuter
• un identifiant facultatif de composant après lequel ce composant doit s'exécuter
• accessoirement, un identifiant de composant que ce composant remplace, mais j'élimine ce cas par substitution

Pour exécuter les composants dans le bon ordre, je désire trier ma liste de composants. On peut considérer qu'il n'y a pas de problèmes du type identifiant qui ne correspond à aucun composant, de composant qui se référence lui-même, certains types de cycles faciles à détecter, etc (j'élimine ou autocorrige ces cas dans une première passe).

Au départ, j'étais parti sur des méthodes empiriques, mais vu que j'avais toujours des cas complexes à traiter, dont la résolution multipliait les passes et transformait un algorithme simple au début en usine à gaz, j'ai fini par rechercher un algorithme standard qui pouvait s'appliquer à mon problème et j'ai trouvé le tri topologique de graphe qui me semble bien adapté. Ce n'est peut-être pas le meilleur système adapté à mon problème, mais j'ai pu au moins le faire fonctionner (et comme mes graphes sont très petits, je ne me pose pas vraiment de problème de complexité et de performances). A noter, que j'ai des composants isolés, mais je les retire au départ, et les remets dans le résultat après le tri, donc aucun problème de ce côté.

Seulement, comme d'ailleurs pour les méthodes empiriques que j'avais essayées au préalable, j'ai le problème des cycles. Dans les méthodes empiriques, j'arrivais assez facilement à les autocorriger pendant le tri (en tout cas la plupart), en choisissant de privilégier le lien "avant", par rapport le lien "après", simplement en invalidant un lien, "cassant" ainsi le cycle.

Dans l'algorithme que j'ai implémenté, je peux détecter s'il existe ou pas des cycles, mais je ne trouve pas de moyen de les isoler, afin de casser l'un de leur lien. En cherchant un peu j'ai trouvé sur un forum la mention d'un algorithme à base de matrice, pas super clairement expliqué (il est surtout question de complexité d'algorithmes et de performances, et c'est probablement normal qu'ils ne s'étendent pas sur l'implémentation détaillée). Je ne sais si je m'oriente vers la bonne solution ou pas du tout. J'ai trouvé également quelque chose appelé "Feedback arc set", puis de "Minimal Spanning Forest" (ou Arbre couvrant de poids minimal, en français, si j'ai bien suivi), et d'algorithmes appelés Borůvka, Prim ou Kruskal. Le Kruskal étant le plus compréhensif pour moi, bien que tout n'y est pas explicite (en tout cas sur wikipedia), je tenterais bien celui-là : suis-je sur la bonne voie ? Ce qui me gène dans cet algorithme, c'est que, si j'ai bien compris, je vais obtenir en résultat un seul graphe non cyclique, alors que je cherche simplement à obtenir un maximum de graphes, en coupant un minimum de lien (mon but étant de ne pas perdre de composant). Mais je suppose, qu'en plusieurs passes, et par différence entre résultat et graphe de départ, je devrais obtenir la liste des noeuds vers lesquels (ou depuis lesquels) j'aurais un lien à couper.

Merci d'avance pour vos conseils et éclaircissements.

Dans un exemple :
Si t'as les tâches A, B, C, D :
A n'a besoin de rien
B a besoin de A
C a besoin de B et A
D a besoin de C et A

Ton ordre d'exécution sera ABCD. Et ton graphe simplifié dira :
A n'a besoin de rien
B a besoin de A
C a besoin de B (et de ses dépendances)
D a besoin de C (et de ses dépendances)

Sachant que dire qu'après avoir lancer A, B dois se lancer. Revient à dire avant de lancer B, je dois avoir lancer A.

Je ne comprends pas pourquoi tu aurai besoin de plusieurs graph en résultat. Sachant que tu cherche seulement un ordre valide de lancement. L'important d'ordre de lancement, c'est que l'élément que tu lance n'ai soit pas de parent, soit que son ou ses parent ai été lancer. Ce qui doit être relativement simple a vérifier dans un graph orienté.

Cordialement,
Patrick Kolodziejczyk.

Je ne cherche pas à avoir plusieurs graphes, je cherche bien à trier mes composants, pour les exécuter dans le bon ordre. Le problème à la base est qu'il s'agit d'une configuration : je programme l'interprétation de la configuration (pour être précis, c'est un point d'extension Eclipse RCP, donc en couche, un nombre de 0 à n, par plugin, dont l'ordre naturel est l'ordre de démarrage des plugins), mais ce n'est pas moi qui vais faire cette configuration. Donc, il est possible qu'après que la configuration ait été modifiée, il y ait des cycles, qui rendent donc impossible de trier, donc d'exécuter. Et je ne veux pas empêcher d'exécuter : je veux pouvoir exécuter tous les composants dans dans tous les cas, au pire en signalant dans le log que l'ordre de démarrage demandé par la configuration ne peut être respecté complètement. Or, dans le cas général, je peux avoir plusieurs cycles, et je peux pouvoir respecter au maximum la configuration demandée, donc ignorer le moins de contrainte possible. C'est sûr que si je soulevais une exception au moindre problème, ce serait facile. Par contre, ça introduirait un autre problème : en fait, il y’a plusieurs points d'extensions et l'un d'eux permet de configurer des callbacks appelé à la fermeture. Si je soulève une exception à la fermeture de l'application, certains services risquent d'être mal fermés, et je ne veux pas introduire des dysfonctionnements annexes sur une simple erreur de configuration : je préfère que le composant le plus touché soit celui qu'on configure.*

[EDIT]
Voici plutôt le type de configuration (ce n'est pas une histoire de dépendance, mais c'est à la fois plus simple, et plus compliqué (pour un problème de démarrage par dépendance, je procéderais probablement différemment, par map, en 2 passes, ce que j'ai déjà fait par ailleurs) :

Code:

---

1 2 3 4 5 6 7 8 9

[A, doit s'exécuter après D] [B] [C, doit s'exécuter avant A] [D] [E, doit s'exécuter après D] [F, doit s'exécuter après E] [G, doit s'exécuter avant D, mais après A] // introduit un cycle, le bon paramétrage étant[G, doit s'exécuter avant D, mais après B] [H, doit s'exécuter avant E, mais après D]

---

Citation:

---

Si je soulève une exception à la fermeture de l'application, certains services risquent d'être mal fermés, et je ne veux pas introduire des dysfonctionnements annexes sur une simple erreur de configuration : je préfère que le composant le plus touché soit celui qu'on configure.

---

On ne va pas débattre du problème de conception évidant. Pas là pour ça...

Citation:

---

Et je ne veux pas empêcher d'exécuter : je veux pouvoir exécuter tous les composants dans dans tous les cas, au pire en signalant dans le log que l'ordre de démarrage demandé par la configuration ne peut être respecté complètement.

---

Dans tout les cas tu te retrouve avec un graph orienté. Sachant que chaque nœud point vers ses nœuds parents.
Si tu ajout à chaque nœud un état (exécuter ou non), alors ton problème est relativement simple.

Tu parcours la liste de tes nœuds, tu exécute ceux-ci n'ont pas de parent non exécuté. (Réduction) Jusqu'à ne plus avant de nœuds à exécuter ou ne plus avoir de nœuds valide pour l’exécution. (Peu importe ta méthode de parcours, car tu va exécuter un nœud seulement si il est "valide")

Si tu es dans le premier cas, tu es dans une configuration "valide".

Dans le second, cas tu es dans une configuration "invalide".
Et il va falloir que tu "exécute"(ou tu casse la ) l'un des nœuds sans satisfaire ses dépendances (et faire ton log de warning.) Ou que tu casse la dépendance vers celui-ci.
Potentiellement, il faut que tu soit capable de détecté les nœuds impliqué dans la dépendance circulaire par rapport à ceux qui ne sont pas impliqué. En gros parcourir l'ensemble des parents d'un nœud retrouver le nœud ou avoir parcouru tout les parents.

Perso, je préfère casser la dépendance.

Cordialement,
Patrick Kolodziejczyk.

Edit :
Si on transforme ta config avec seulement des après

Code:

---

1 2 3 4 5 6 7 8

[A, doit s'exécuter après D, C] [B] [C] [D, doit s'exécuter après G] [E, doit s'exécuter après D, H] [F, doit s'exécuter après E] [G, doit s'exécuter après A] [H, doit s'exécuter après D]

---

Avec notre résolution,

Citation:

---

1. Je lis la liste depuis de début. Si je vois un élément exécutable, je le lance et je refait 1.
2. Si tout les éléments n'ont pas été lancer, je trouve le premier éléments inclus dans un cycle et je casse les dépendances vers celui-ci. Et je refait 1.
3. FIN

---

1. On lance B, puis C
2. On a un cycle qu'on :
On casse la dépendance de G par rapport à A (avec un log). Car A dépend de D qui dépends de G qui dépends de A.
1. On lance G, puis D, puis A, puis H, puis E.
3. FIN

Citation:

---

Envoyé par kolodz

On ne va pas débattre du problème de conception évidant. Pas là pour ça...

---

Je ne te suis pas là...

Citation:

---

Potentiellement, il faut que tu soit capable de détecté les nœuds impliqué dans la dépendance circulaire par rapport à ceux qui ne sont pas impliqué. En gros parcourir l'ensemble des parents d'un nœud retrouver le nœud ou avoir parcouru tout les parents.

---

C'est justement après avoir essayé différentes méthodes classiques (genre parcourt de liste, map de marquage, etc...) que j'ai fini par me dire qu'il valait mieux que je cherche un algorithme : j'avais toujours un jeu d'essai avec un cas particulier à traiter par un code particulier.

Du coup, çà me semble bien plus simple de trier ma liste : ensuite, je n'ai pas de question à me poser ou de parcourt en plusieurs passes à faire,.
Surtout que la notion de parent dans un arbre cyclique où j'ai plusieurs parents possibles pour un noeud me semble justement difficilement à déterminer, sans utiliser un tel algorithme (en tout cas tous les essais à base de parcourt et de map de marquage donnent des usines à gaz à la fin, avec pleins de cas particuliers à gérer).



En tout cas, je viens de terminer mes tests avec le Kruskal, et j'arrive bien à ce que je veux, ou presque. Presque, parce que je n'ai pas forcément le composant que j'ai introduit volontairement pour faire un cycle qui est altéré, mais je pense que je ne peux pas en attendre plus : n'ayant aucun système de poids (aucun composant n'est plus important qu'un autre), et je ne peux pas déterminer quels sont les derniers ajoutés à une configuration correcte (sans tester toutes les combinaisons). Mais pour le coup, celui qui fait la configuration doit bien se douter que c'est son composant qui change quelque chose au point que l'ordre ne peut plus être respecté. Donc ça me suffit pour un premier jet et je verrais ensuite si j'ai moyen de faire mieux.

Donc pour moi, mon problème est résolu.

Citation:

---

Envoyé par joel.drigo

Je ne te suis pas là...

---

Logiquement chaque modules doit pouvoir planter fonctionnellement provoquer de problème majeur sur les autres composants.
Si ce n'est pas possible avant d'être lancer le module doit vérifier si celui-ci ne va pas planter. Par exemple exiger une configuration valide pour se lancer.
C'est préférable à faire avec une erreur et avoir faut. C'est le principe du "Fail-Fast". C'est un peu comme la gestion des erreurs de compilation. Si t'as une erreur, tu va pas plus loin. Ça sert à rien de tout façon c'est faut...

Cordialement,
Patrick Kolodziejczyk.

source :
http://en.wikipedia.org/wiki/Fail-fast

Citation:

---

Envoyé par kolodz

C'est le principe du "Fail-Fast".

---

C'est vrai pour un développeur, moins pour un intégrateur. Or, ce sont des intégrateurs qui font les configurations, et je ne peux exiger d'eux qu'ils soient aussi rigoureux, mais plutôt leur fournir le maximum d'informations pour qu'ils soient conscients qu'il y a un problème quelque part, s'ils ne s'en aperçoivent pas d'eux même en testant leur configuration, et ce, sans risquer une conséquence sur autre chose qu'ils ne connaissent pas forcément. Ainsi, je ne plante pas, je ne gère pas d'état (déjà exécuté, pas exécuté), je dis simplement que leur composant ne s'exécute pas au moment où il le voudrait. Enfin c'était mon but : là, effectivement, un autre composant peut être impacté, mais c'est également le cas avec ta méthode (qui est bien celle que j'applique habituellement en cas de gestion de dépendances).