graph - グラフ: ノードの依存関係

Question

次のようなグラフがあります。

たとえば、1,2,3,5 であるノード 8 の依存関係を知りたいとします。この問題を解決するために、誰かが私にいくつかのコードを与えることができますか、それとも疑似コードである可能性がありますか?

ありがとう

Answer 1

依存構造は部分的に順序付けられたセットです。私は2つの方法でカバーした同様のケースを持っていました(Pythonで):

• nodes_to_update( to_proc )パラメータは、開始するノードのセットです (例: set([8]))。指定されたノードが依存するすべてのノードのセットとリーフ ノードのセットの 2 つのノード セットを返します。アイデアは、訪問したノードに依存するすべてのノードを再帰的に訪問することです。
• sequence_to_update( to_proc )パラメータは上記の通りです。リスト内のノードがリスト内の前のノードのみに依存するように、ノードの (順序付けられた) リストを返します。これは、順序付きリストにリーフ ノードを追加し、処理するノードのセット (すべておよびリーフ ノード) を更新することによって行われます。

依存ノードはメソッドdown_nodes(o_id)で取得され、依存するノードは で取得されup_nodes(o_id)ます。

def nodes_to_update(self, to_proc):
    all_to_update, first_to_update = set(), set()
    while to_proc:
        n = to_proc.pop()
        all_to_update.add(n)
        ds = self.down_nodes(n)  # nodes on which n depends
        if not ds:
            first_to_update.add(n)
        else:
            to_proc.update(ds)
    return all_to_update, first_to_update

def sequence_to_update(self, to_proc):
    all_to_update, first_to_update = self.nodes_to_update(to_proc)
    update_in_order = []
    while first_to_update:
        n_id = first_to_update.pop()
        all_to_update.discard(n_id)
        update_in_order.append(n_id)
        # nodes which depend on n_id (intersection of upper nodes and all nodes to update)
        for up_id in (self.up_nodes(n_id) & all_to_update):
            if all(d not in all_to_update for d in self.down_nodes(up_id)):
                first_to_update.add(up_id)
    return update_in_order