그래프 : 노드 의존성

Question

나는 그래프 같이 있습니다 : 1,2,3,5 : 예를 들어

내가있는 노드 (8)의 의존성을 알고 싶어요. 어떤 신체가 나에게 어떤 코드를 주거나이 문제를 푸는 의사 코드 일 수 있습니까?

감사

Answer 1

종속 구조는 partially ordered set이다. 난 (파이썬) 2 개 방식으로 덮여 있었다 유사한 경우 : 시작하는

• 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