|
Scheindorf |
Posté le 30 Mar 2009 à 01:06 |

Messages : 77
|
Je crois voir ou tu veux en venir, ça me semble une implémentation simple d'un topsort qui ne correspond donc pas entièrement a ce que je recherche. Mais bon, je crois que je vais finir par laisser tomber les assertions after/before pour le moment, si j'arrive a coder la génération du graphe et le sorting sans, peut etre la pilule passeras mieux avec...
En attendant, si quelqu'un d'autre a des conseils ou de la doc, je suis toujours preneur
|
|
Mod |
Posté le 29 Mar 2009 à 18:58 |

Messages : 4954
|
Pour résoudre ce genre de problèmes, en partant du principe que tu n'as pas des milliers d'éléments à charger, je prendrais une solution proche de celle des graphes, avec une résolution à coups de fonction récursive.
Et je commencerais par simplifier au maximum le problème en supprimant l'assertion "avant", qui est inutile à un problème de dépendance, du moins si j'ai bien saisi le tien dans sa totalité.
Je prendrai une fonction récursive servant au tri, et que j'appelerai "ModuleOrder". Celle-ci prend en entrée un paramètre : un objet de la classe Module.
Dans cette fonction :
Code :
Pour chaque dépendance du module courant :
Si la dépendance n'est pas chargée :
On appelle LoadModule avec pour paramètre la dépendance.
Une fois toutes les dépendances évaluées, on place le module dans la liste de tri.
Ca devrait, à première vue, être suffisant.
En PHP, ça devrait donner quelque chose de ce genre (je n'ai pas testé, mais l'idée est là) :
Code : PHP
/*
En début de code, créer toutes tes instances de la classe Module, en ajoutant leurs dépendances au fur et à mesure.
Créer en dernier un objet Module qui servira à lister tous les modules à trier (dépendances à un niveau fichier ou programme. Le module de base, en quelque sorte.
Créer un tableau global $ordered_list qui stockera la liste ordonnée des modules.
*/
class Module
{
private $dependencies;
public function AddDependency($dependency)
{
array_push($dependencies,$dependcy);
}
public function GetDependencies()
{
return $dependencies;
}
/*
Reste de la classe Module avec les informations dont tu as besoin...
*/
}
// Quelque part dans le code, lancer la fonction ModuleOrder avec le module de base.
function ModuleOrder($module)
{
foreach ($module->GetDependencies()) as $dependency)
if (!in_array($dependency, $ordered_list))
ModuleOrder($dependency);
array_push($ordered_list);
}
|
|
Scheindorf |
Posté le 29 Mar 2009 à 01:09 |

Messages : 77
|
hmm, voila, je voudrai vous soumettre un problème, pour le quel l'on m'a donné deux solutions, mais malgré tout, je bloque dessus. Je n'arrive pas a les implémenter, je ne trouve pas de documentation, j'ai du mal a l'adapter a ce que je veux précisément...
Donc, mon problème est un problème de gestion de dépendances, je cherche a réaliser un systeme de chargement de modules pour une application php (et surement m'en resservir en ruby) un peu similaire au rc init de gentoo (dont j'ai vaguement consulter les sources sans rien y comprendre...).
J'ai donc un ensemble d'éléments ayant un nom, fournissant une liste de services, ayant besoin d'une liste de services, et ayant des assersions "avant / apres" tel ou tel autre modules, voire "before/after all" pour être chargé si possible avant ou après tout le reste.
Ce que j'aimerai c'est donc avoir un algorithme de tri qui ordonne ses éléments de manière a être exécutés dans un ordre correct en considérant que des priorités s'appliquent, par ordre croissant de priorité :
-si un élément n'a aucune assersions after/before, il est consideré comme un "before all" de moindre priorité.
-une assertion before all
-une assertion before
-une assertion after all
-une assertion after
-un service requis
de plus, ces priorités sont locales, c'est à dire par exemple que si un élément est à la fois "after all" et "before all", ne requière ni ne fournis rien , il seras placé au début des modules chargés tout a la fin.
Les deux débuts de pistes que l'on m'a donné sont soit
Méthode A
Générer un graphe orienté où les services sont traduits en modules correspondant, les before X en (X enfant de Y) et after X en (Y enfant de X) et les "all" comme deux nœuds spéciaux virtuels. Puis effectuer un trie topologique.
Ok, elle me parait bonne cette méthode, mais je n'arrive pas à l'implémenter, et je ne sais pas trop ce qui me bloque. De plus plusieurs points restent obscur a mes yeux, par exemple, comment gérer les priorités locales ?
Methode B
On assigne à chaque élément un identifiant unique puis on itere jusqu'a ce que chaqu'un soit à une place qui lui conviens. A chaque pas de la boucle, chaque élément va demander au éléments ayant un ID plus faible si ils ont besoin de lui avant eux. Si c'est le cas on permute l'ID de l'élément avec le premier élément antérieur ayant demander l'échange.
Là non plus, je bloque sur l'implémentation, même sur la théorie, je n'arrive à faire aucun des deux sur papier, et encore moins en code. Et comment ici aussi gérer les priorités locales?
Je crois que mes lacunes en maths et algorithmique avancés me rattrapent ici...
Si quelqu'un avait des conseils pour m'aider à m'en sortir sur ce problème, voire même une implémentation en pseudo code, C (bien commenté), ruby ou php je lui en serais éternellement ( non, quand même pas mais bon ) reconnaissant
|