次の状況のデータ構造を考え出そうとしています。
グラフ構造
重み付けされていない有向エッジを持つノードのグラフを作成する予定です。Graph = [Node]
各ノードには次のものがあります。
- いくつかの TBD 内部 (永続的) 状態
- 着信メッセージのキュー
- 現在のノード状態を受け入れる関数によって決定される、送信できるメッセージのタイプ (失敗の可能性あり)
- エッジのリスト
Node { nodeState :: NodeState, inbox :: Queue NodeMessage, nodeMessage :: (NodeState -> Maybe NodeMessage), connections::[NodeEdge] }
各エッジは、ターゲット ノードの保留中のメッセージをキャプチャする中間ステップです。
NodeEdge { pendingMessage:: Maybe NodeMessage, targetNode :: Node }
メッセージパッシング
メッセージの受け渡しは段階的に発生し、同時ではありません (ただし、計算時間を短縮するためにキューを並行して処理することはできます)。
- フェーズ 1: すべてのノードの受信トレイを確認し、メッセージを処理し
NodeState、関連する場合は更新します。 - フェーズ 2: すべてのノードを実行
nodeMessageし、結果が の場合はJust NodeMessage、すべての接続に NodeMessage を送信します ([NodeEdge]) - フェーズ 3: すべてのノード エッジをチェックし、メッセージがある場合は、それをターゲット ノードのメッセージ キューに追加します。
モナト/ST
私の最初の計画は、すべてのノードに ID (おそらく単純な Int) を割り当て、各ノードを Map Int Node に格納することでした。ST Monad は試したことがありませんが、 のようなものが使えると思いましST s (M.Map Int Node)た。任意のフェーズで、各ノードのメッセージ送信アクティビティは O(k log N) で処理できます。
一方、ノード/エッジがエッジ/ノードの変更可能な状態を更新できた場合、任意の単一のキューを O(k) で処理できます。
ST/Map メソッドはかなり直観的に見えますが、グラフ全体を変更可能にすることは私には理解できません。
提案/ヒント/推奨読書はありますか?