圖：節點依賴關係

Question

我有這樣的圖表：

例如我想知道節點8的依賴關係：1,2,3,5。可以有些身體給我一些代碼或可能是僞代碼來解決這個問題？

由於

Answer 1

相關結構是partially ordered set。我有我覆蓋有2種方法（在python）類似的情況：

• nodes_to_update(to_proc)參數是一組節點的開始與（例如設置（[8]））。返回兩組節點：一組給定節點依賴的所有節點以及一組葉節點。想法是遞歸訪問依賴訪問節點的所有節點。
• 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