Simulation graphique Max-Flow en Java

Question

J'écris le programme Java pour les sports de ligue qui passe par l'ensemble actuel des jeux joués de chaque équipe et leurs horaires des prochains jeux, puis basé sur cela je fais un modèle de réseau de flux. L'idée du programme est de trouver quelles équipes sont déjà éliminées et n'ont aucune chance de gagner ou de partager une place avec une autre équipe. Après avoir analysé le réseau (en appliquant EdmondsKarp algo.), Je découvre si l'équipe est éliminée ou non. Maintenant, je veux aussi simuler cela. J'utilise JGraphT comme bibliothèque de graphes, et j'utiliserai probablement JGraph pour la visualisation (raison: une fois que je crée des objets JGraphT, je peux simplement instancier des objets JGraph avec eux et afficher un graphique). J'ai aussi découvert le framework Jung hier, ça me semble bien.

Le principal problème est que je n'ai jamais écrit de simulation et c'est le point où j'ai besoin de l'aide "Hello World". Quand je dis simulation je veux dire que je veux montrer visuellement chaque partie de l'exécution de l'algorithme, et voici un exemple de scénario: l'algorithme doit trouver des chemins d'augmentation, donc je veux montrer quand chaque nouveau bord est ajouté au chemin d'augmentation. L'utilisateur pourra jouer et arrêter l'animation. Je veux aussi montrer des changements de flux dans tous les bords et des choses comme ça. Jusqu'à présent, j'ai un algorithme qui fonctionne mais je ne sais pas comment aborder la simulation. Dois-je utiliser un thread séparé pour l'exécution de la simulation? Dois-je écrire une classe séparée qui serait exécutée en tant qu'algorithme mais avec des états enregistrant sans même savoir pour l'algorithme réel (parce que je ne veux pas interrompre la performance de l'algorithme réel). Devrais-je utiliser l'algorithme actuel et ajouter quelques lignes entre les deux pour sauvegarder les états d'exécution dans certaines structures de données que je pourrais utiliser plus tard pour afficher la simulation à l'utilisateur? Toutes les idées pourraient aider ..

Answer 1

Si je vous comprends bien, vous demandez un moyen de Animer votre algorithme et contrôler son exécution de manière interactive à partir de l'animation, ce qui est pas tout à fait la même chose que la simulation (un la simulation exécute simplement un modèle, généralement sur un intervalle de temps donné - ce qui n'a rien à voir avec l'interaction ou l'animation de l'utilisateur, mais bien sûr, pourrait aussi être combiné avec les deux).

Je vous suggère de diviser le problème en deux parties principales, l'interaction et l'animation. Les deux peuvent être résolus en appliquant une approche model-view-controller:

• Pour interagir avec votre algorithme, identifier les « étapes atomiques » que vous souhaitez distinguer, par exemple l'ajout d'un bord à un chemin. Ensuite, vous étendez votre algorithme pour qu'il fonctionne également par étapes ou écrivez une classe supplémentaire qui enveloppe l'algorithme et fournit les routines nécessaires pour une exécution par étapes. Pour animer l'état actuel de votre algorithme, vous devez utiliser le observer pattern, où votre composant d'animation est l'observateur et est notifié par l'algorithme chaque fois que son état change, par ex. un bord a été ajouté à un chemin. Vous pouvez également décrire le changement d'état actuel en transmettant un indice (tel que l'objet de contour qui a été ajouté au chemin); cela pourrait faciliter la visualisation de la différence entre l'ancien et le nouvel état.

En ce qui concerne vous des questions threading: l'algorithme devrait probablement fonctionner dans un fil supplémentaire (à moins qu'il est très très rapide), et vous pouvez aussi mettre l'animation dans un fil supplémentaire (ce qui est probablement déjà fourni par JGraph de toute façon, il suffit de vérifier les documents ou d'utiliser leurs composants comme indiqué). Vous devez noter, cependant, que la performance d'exécution de votre algorithme est presque certainement affectée par l'analyse, même si est fonctionnant dans un autre thread (puisque la notification doit encore être faite par l'algorithme) - alors soyez prudent avec l'analyse des performances et l'utilisation une version non animée pour de telles études.