JavaでのMax-Flowグラフシミュレーション

Question

私は、各チームの現在のプレイされたゲームのセットと次のゲームのスケジュールを通過するリーグスポーツ用のJavaプログラムを書いており、それに基づいてフローネットワークのモデルを作成しています。プログラムのアイデアは、どのチームがすでに排除されているかを見つけ、他のチームと1位を獲得したり共有したりする機会がないことです。ネットワークを分析した後（EdmondsKarpアルゴリズムを適用）、チームが削除されるかどうかを確認します。今、私もこれをシミュレートしたいです。 JGraphTをグラフライブラリとして使用しており、おそらく視覚化にJGraphを使用します（理由：JGraphTオブジェクトを作成したら、それらを使用してJGraphオブジェクトをインスタンス化し、グラフを表示できます）。昨日、Jungフレームワークを見つけたのも嬉しいようです。

主な問題は、シミュレーションを書いたことがないので、「Hello World」が必要な点です。助けて。シミュレーションとは、アルゴリズムの実行のすべての部分を視覚的に表示することを意味します。シナリオの例は次のとおりです。アルゴリズムは拡張パスを見つける必要があるため、拡張エッジに新しいエッジが追加されるタイミングを表示します。ユーザーはアニメーションを再生および停止できます。また、すべてのエッジのフローの変化などを示したいと思います。これまでのところ、アルゴリズムは機能していますが、シミュレーションへのアプローチ方法がわかりません。シミュレーションの実行に別のスレッドを使用する必要がありますか？アルゴリズムとして実行されるが、実際のアルゴリズムを知らなくても状態を記録する別のクラスを作成する必要があります（実際のアルゴリズムのパフォーマンスを中断したくないため）。現在のアルゴリズムを使用し、後でユーザーにシミュレーションを表示するために使用できるデータ構造の実行状態を保存するために、間にいくつかの行を追加する必要がありますか？どんなアイデアでも役立つかもしれません。

Answer 1

あなたが正しく理解しているなら、あなたはアルゴリズムをアニメーションし、アニメーション内からその実行をインタラクティブに制御する方法を求めています。これはシミュレーションとまったく同じではありません。通常、指定された時間間隔でモデルを実行します-これはユーザーの操作やアニメーションとは関係ありませんが、もちろん両方とも組み合わせることができます。

問題を2つの主要な部分、インタラクションとアニメーションに分割することをお勧めします。両方とも model-view-controller アプローチを適用することで解決できます。

• アルゴリズムと対話するには、区別したい「原子ステップ」を特定します。パスへのエッジの追加。次に、アルゴリズムを段階的に機能するように拡張するか、アルゴリズムをラップし、段階的な実行に必要なルーチンを提供する追加のクラスを記述します。

• アルゴリズムの現在の状態をアニメーション化するには、観測者パターンを使用する必要があります、アニメーションコンポーネントはオブザーバーであり、その状態が変更されるたびにアルゴリズムによって通知されます。たとえば、エッジがパスに追加されました。また、ヒント（パスに追加されたエッジオブジェクトなど）を渡すことで、実際の状態変化を記述することもできます。これにより、古い状態と新しい状態の違いを簡単に視覚化できます。

スレッドの質問について：アルゴリズムはおそらく（非常に高速でない限り）追加のスレッドで実行する必要があり、アニメーションを追加のスレッドに配置することもできます（これはおそらくJGraphによって既に提供されています。またはアドバイスに従ってコンポーネントを使用します）。ただし、アルゴリズムが別のスレッドで実行されている場合でも、アルゴリズムの実行時のパフォーマンスはアニメーションの影響をほぼ確実に受けることに注意する必要があります（通知はアルゴリズムによって行われる必要があるため）。パフォーマンス分析を行い、そのような研究にはアニメーション化されていないバージョンを使用します。