Max-Flow graph simulation in Java

Question

Hello

I am writing Java program for league sports that goes through current set of played games of each team and their schedules of next games, and then based on that I make a model of flow network. The idea of program is to find which teams are already eliminated and have no chances of wining or sharing 1 place with any other team. After analyzing network (applying EdmondsKarp algo.) I find out if team get's eliminated or not. Now I also want to simulate this. I am using JGraphT as graph library, and will probably be using JGraph for visualization (reason: once I create JGraphT objects I can simply instantiate JGraph objects with them and display graph). I also found out for Jung framework yesterday, seems nice.

Main problem is I never wrote simulation and it's the point where I need "Hello World" help. When I say simulation I mean I want to visually show every part of algorithm execution, and here is example scenario: algorithm has to find augmenting paths, so I want to show when every new edge is added to augmenting path. User will be able to play and stop animation. I also want to show changes in flow in all edges and things like that. So far, I have algorithm working but I don't know how to approach simulation. Should I be using separate thread for simulation execution? Should I write separate class that would be executed as algorithm but with states recording without even knowing for real algorithm (because I don't want to interrupt performance of real algorithm). Should I use current algorithm and add some lines in between for saving execution states in some data structures that I could use later for displaying simulation to user? Any ideas might help..

Answer 1

If I do understand you correctly, you're asking for a way to animate your algorithm and control its execution interactively from within the animation, which is not quite the same as simulation (a simulation just executes a model, usually over a given time interval - which has nothing to do with user interaction or animation, but of course could be combined with both as well).

I would suggest you split the problem into the two main parts, interaction and animation. Both can be solved by applying a model-view-controller approach:

• To interact with your algorithm, identify the 'atomic steps' you want to distinguish, e.g. the addition of an edge to a path. Then you either extend your algorithm to also work step-wise or write an extra class that wraps the algorithm and provides the necessary routines for a stepwise execution.

• To animate the current state you algorithm is in, you should use the observer pattern, where your animation component is the observer and gets notified by the algorithm whenever its state changed, e.g. an edge was added to a path. You could also describe the actual state change by passing a hint (such as the edge object that has been added to the path); this might make it easier to visualize the difference between old and new state.

Regarding you threading questions: the algorithm should probably run in an extra thread (unless it's very very fast), and you could also put the animation in an extra thread (this is probably already provided by JGraph anyway, just check the docs or use their components as advised). You should note, however, that your algorithm's runtime performance is almost certainly affected by the aninmation, even if it is running in another thread (since notification still has to be done by the algorithm) - so be careful with performance analysis and use an un-animated version for such studies.