비순환 지향 그래프가 주어지면 "동일한 레벨에있는"노드 컬렉션 모음을 반환합니까?

Question

첫째, 어떤 알고리즘이 호출되는지, 우선적 인 문제인지는 확실하지 않습니다. 질문의 첫 번째 부분은이 알고리즘이 무엇입니까? [[1, 2, 4, 6], [3], [5], [7], [8, 9, 10]]

편집 : : 저를 추가하자 기본적으로

내가 노드 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]과 가장자리이에서 ([1,3],[2,3],[3,5],[4,5],[5,7],[6,7],[7,8],[7,9],[7,10])

는 다음과 같이 컬렉션을받을 수 있는지 궁금 해요를 삽입하는에 DiGraph()이 도움이된다면 약간의 제약. 이 -이이 보장, 더 사이클이 없습니다 - 아무도 그래프에 대한 포인트를 시작하지 있습니다

난 할 노력하고있어, 자신의 처리를 병렬화 할 수 있도록 동일한 수준에서 노드를 수집하는 것입니다하지만, 외부 컬렉션 내에서 처리는 연속적입니다.

EDIT2 : "레벨"을 표현하는 가장 쉬운 방법은 의 가장 깊은 전임자인데, 전임자와 동일한 깊이를 가진 모든 노드입니다. 따라서 위의 목록에서 첫 번째 항목은 가장 깊은 선행자로 0을 갖고 두 번째 노드는 1을 가지며 세 번째 노드는 두 개를 갖는 노드입니다. 각 목록 내에서 형제 인의 순서는 병행 처리되므로 관련이 없습니다.

Answer 1

이 그래프의 출력을 [[1, 2, 4, 6], [3], [5], [7], [8, 9, 10]]으로 지정하고 싶습니다. IIUC의 패턴은 다음과 같습니다.

• [1, 2, 4, 6]은 가장자리가없는 노드입니다.

• [3]은 모든 이전 노드가 삭제되었다고 가정하고 가장자리에 없음이없는 노드입니다.

• [4]은 모든 이전 노드가 삭제되었다고 가정 할 때 가장자리에 없음이없는 노드입니다.

• 등 (모든 노드가 삭제 될 때까지)

우리가 그런

g = networkx.DiGraph() 
g.add_edges_from([[1,3],[2,3],[3,5],[4,5],[5,7],[6,7],[7,8],[7,9],[7,10]]) 

로 시작하는 말 우리가 할 수있는

def find_levels(g): 
    levels = [] 
    while g.nodes(): 
     no_in_nodes = [n for (n, d) in g.in_degree(g.nodes()).items() if d == 0] 
     levels.append(no_in_nodes) 
     for n in no_in_nodes: 
      g.remove_node(n) 
    return levels 

우리가 실행하는 경우처럼 코드이 결과는 다음과 같습니다.

>>> find_levels(g) 
[[1, 2, 4, 6], [3], [5], [7], [8, 9, 10]] 

여기서 복잡도는 Θ (| V | + | E |). Fibonnacci Heap을 사용하면 다소 복잡한 버전을 구축 할 수 있습니다.기본적으로 모든 꼭지점은 힙에 배치해야하며 각 레벨은 0 도의 꼭지점으로 구성됩니다. 하나가 터지면 다른 꼭지점의 가장자리가 제거 될 때마다 힙 감소 키 작업으로 변환 할 수 있습니다 (나머지 꼭지점의 도수가 감소됨). 이렇게하면 실행 시간이 Θ (| V | log (| V |) + | E |)으로 줄어 듭니다.

Answer 2

왜 bfs가이를 해결하지 못합니까? bfs 알고리즘은 광폭 트래버 설 알고리즘, 즉 트리 레벨을 가로 지르는 알고리즘이다. 이것은 또한 같은 레벨에있는 모든 노드가 한 번에 탐색된다는 것을 의미합니다. 이는 원하는 출력입니다. 주석에서 지적했듯이 이것은 그래프의 시작점을 가정합니다.

Answer 3

토폴로지 정렬은 Ami 상태와 같이이를 달성합니다. 다음은 컨텍스트가없는 부스트 그래프 라이브러리 구현이지만 의사 코드는 추출 할 수 있습니다. toporder 객체는 토폴로지 순서에 반복기를 제공합니다. 원하는 경우 일반 알고리즘을 추출 할 수 있습니다.

template<typename F> 
void 
scheduler<F>::set_run_levels() 
{ 

    run_levels = std::vector<int>(tasks.size(), 0); 
    Vertexcont toporder; 

    try 
    { 
     topological_sort(g, std::front_inserter(toporder)); 
    } 
    catch(std::exception &e) 
    { 
     std::cerr << e.what() << "\n"; 
     std::cerr << "You most likely have a cycle...\n"; 
     exit(1); 
    } 

    vContIt i = toporder.begin(); 

    for(; 
     i != toporder.end(); 
     ++i) 
    { 
     if (in_degree(*i,g) > 0) 
     { 
      inIt j, j_end; 
      int maxdist = 0; 
      for(boost::tie(j,j_end) = in_edges(*i,g); 
       j != j_end; 
       ++j) 
      { 
       maxdist = (std::max)(run_levels[source(*j,g)], maxdist); 
       run_levels[*i] = maxdist+1; 
      } 
     } 
    } 
} 

같은 문제에이 문제를 적용한 다음 불필요하다고 생각했습니다. 모든 작업이 자신의 부양 가족에게 완료를 알리면 (condition_variable, promise에 의해) 헤어 트리거에 대한 작업을 설정하기 만하면됩니다. 따라서 필요한 것은 각 작업의 종속성을 파악하고 초기 작업을 찾은 다음에 시작하는 것입니다. 귀하의 경우에는 run_level의 전체 사양이 필요합니까?