Java中的最大流圖模擬

Question

我正在爲聯盟運動編寫Java程序，該程序會通過當前每個團隊玩過的遊戲集以及他們下一次遊戲的時間表，然後基於此我製作一個流量網絡模型。計劃的想法是找出哪些球隊已經被淘汰，並且沒有機會與任何其他球隊取勝或分享一個球員。在分析網絡（應用EdmondsKarp算法）之後，我發現團隊是否被淘汰。現在我也想模擬這個。我使用JGraphT作爲圖形庫，並且可能會使用JGraph進行可視化（原因是：一旦我創建了JGraphT對象，我就可以簡單地實例化JGraph對象並顯示圖形）。我昨天也發現了Jung的框架，看起來不錯。

主要問題是我從來沒有寫過模擬，這是我需要「Hello World」幫助的地方。當我說模擬時，我的意思是我想直觀地顯示算法執行的每個部分，下面是一個示例場景：算法必須找到擴充路徑，所以我想要顯示何時將每條新邊添加到擴充路徑。用戶將能夠播放和停止動畫。我也想在所有邊緣和類似的東西中顯示流量的變化。到目前爲止，我有算法的工作，但我不知道如何處理模擬。我應該使用單獨的線程進行模擬執行嗎？我應該編寫單獨的類，它可以作爲算法執行，但是不需要知道真實算法就可以記錄狀態（因爲我不想中斷真實算法的性能）。我是否應該使用當前的算法並在兩者之間添加一些行以保存某些數據結構中的執行狀態，以便稍後用於向用戶顯示模擬？任何想法可能會幫助..

Answer 1

如果我理解正確的話，你問的方式來動畫你的算法和動畫，這是不完全一樣的模擬中交互控制其執行（一仿真只是執行一個模型，通常在給定的時間間隔內 - 與用戶交互或動畫無關，但當然也可以與兩者結合使用）。

我建議你把問題分成兩個主要部分，交互和動畫。

• 要與你的算法進行交互，確定要區分，例如在「原子臺階」：兩者都可以通過應用model-view-controller辦法來解決邊緣添加到路徑。然後，您要麼擴展算法以逐步工作，要麼編寫一個包裝算法的額外類，併爲逐步執行提供必要的例程。

• 要動畫您算法是在當前狀態下，你應該使用observer pattern，其中動畫部分是觀察者和被通過算法時通知其狀態改變，例如邊緣被添加到路徑。您還可以通過傳遞提示（例如已添加到路徑中的邊緣對象）來描述實際狀態更改;這可能更容易看出舊狀態和新狀態之間的差異。

關於你線程問題：算法應在額外的線程可能運行（除非它是非常非常快的），你也可以把動畫以額外的線程（這可能已經讓JGraph提供無論如何，只需檢查文檔或按照建議使用他們的組件）。但是，您應該注意，即使在另一個線程中運行（因爲通知仍然需要由算法完成），您的算法的運行時性能幾乎肯定會受到信息的影響 - 所以請注意性能分析和使用這種研究的一個非動畫版本。