Utilisation de JGraphT pour gérer l'ordre des tâches dépendantes

Question

J'ai une liste de tâches qui ont des dépendances entre elles et je réfléchissais à la façon dont je pourrais utiliser JGraphT pour gérer l'ordre des tâches. Je voudrais mettre en place le graphique comme un graphe orienté et supprimer les sommets comme je les ai traités (ou devrais-je les masquer?). Je pourrais utiliser TopologicalOrderIterator si je n'allais exécuter qu'une tâche à la fois mais j'espère pouvoir paralléliser les tâches. Je pourrais obtenir TopologicalOrderIterator et vérifier Graphs.vertexHasPredecessors jusqu'à ce que je trouve autant que je veux exécuter comme une fois mais idéalement, il y aurait quelque chose comme Graphs.getVerticesWithNoPredecessors. Je vois que Netflix fournit un utilitaire pour obtenir les sommets des feuilles, donc je pourrais inverser le graphique et l'utiliser, mais ça ne vaut probablement pas le coup. Quelqu'un peut-il me diriger vers un meilleur moyen? Merci!

Answer 1

Un ordre topologique peut ne pas être nécessairement ce que vous voulez. Voici un exemple pourquoi pas. Compte tenu de l'ordre topologique suivant des tâches: [1,2,3,4], et les arcs (1,3), (2,3). Cela signifie que la tâche 1 doit être terminée avant la tâche 3, similaire pour 2 et 4. Supposons également que la tâche 1 prend beaucoup de temps à compléter. Nous pouvons donc commencer à traiter les tâches 1 et 2 en parallèle, mais vous ne pouvez pas démarrer 3 avant que 1 ne soit terminé. Même si la tâche 2 se termine, nous ne pouvons pas démarrer la tâche 4 car la tâche 3 est la tâche suivante de notre commande et cette tâche est bloquée par 1.

Voici ce que vous pourriez faire. Créez un tableau dep[] qui suit le nombre de dépendances non satisfaites par tâche. Donc dep[i]==0 signifie que toutes les dépendances pour la tâche i ont été remplies, ce qui signifie que nous pouvons maintenant effectuer la tâche i. Si dep[i]>0, nous ne pouvons pas encore effectuer la tâche i. Supposons qu'il existe une tâche j qui doit être effectuée avant la tâche i. Dès que nous terminons la tâche j, nous pouvons décrémenter le nombre de dépendances non satisfaites de la tâche i, c'est-à-dire dep[i]=dep[i]-1. Encore une fois, si dep[i]==0, nous sommes maintenant prêts à traiter la tâche i. Donc en bref, l'algorithme pseudo-code ressemblerait à ceci:

1. Initialiser tableau dep[].
2. traitement de démarrage en parallèle avec toutes les tâches idep[i]==0
3. si une tâche i finalise, décrémenter dep[j] pour toutes les tâches j qui dépendent de i. Si la tâche j a dep[j]==0, commencez le traitement.

Vous pouvez certainement utiliser un graphe orienté pour modéliser les dépendances. Chaque fois que vous terminez une tâche, vous pouvez simplement parcourir les voisins sortants (dans jgrapht, utilisez la fonction successorsOf (vertex)). Le DAG peut également être simplement utilisé pour vérifier la faisabilité: si le graphique contient un cycle, vous avez un problème dans vos dépendances. Cependant, si vous n'avez pas besoin de cette machinerie lourde, je créerais simplement un tableau bidimensionnel où pour chaque tâche i vous stockez les tâches qui dépendent de i.

L'algorithme résultant s'exécute en temps O (n + m), où n est le nombre de tâches et m le nombre d'arcs (dépendances). Donc c'est très efficace.