BGL (부스트 그래프 라이브러리)을 사용하여 DAG의 모든 토폴로지 정렬 찾기

Question

부스트 그래프 라이브러리를 사용하여 주어진 DAG의 모든 토폴로지 종류를 어떻게 찾을 수 있습니까 G?

가능한 이론적 인 언급을 발견했습니다. 여기에 구현이있는 code도 있습니다. 하지만 처음부터 실제로 시작하고 싶지는 않습니다. BGL을 사용하여 계산하고 싶습니다.

Answer 1

하나의 전략은 전임자없이 모든 정점을 얻는 것입니다 (방향이없는 모서리 없음). 선행 작업없이 정점을 기반으로 벡터를 곱합니다. 만약 당신이 할 C++ 그것을 공유하시기 바랍니다. 사용자 정의 정점없이

deque<vertex_t> topologicalSorted; 

//perform topological sort 
if (topologicalSort(graph, topologicalSorted)) { 
    cout << "The graph is directed acyclic!" << endl; 
    cout << "Topological order: "; 
    for (int i = 0; i < topologicalSorted.size(); i++) { 
     cout << graph[topologicalSorted.at(i)].label << " "; 
    } 
    cout << endl; 
} 


bool topologicalSort() 
{ 
    try 
    { 
     boost::topological_sort(graph, front_inserter(topologicalSorted)); 
    } 
    catch (boost::not_a_dag) 
    { 
     cout << "not a dag\n"; 
     return false; 
    } 
    cout << "top sort OK\n"; 

    return true; 
} 

: 정점 유형 vertex_t와 DAG 을 감안할 때

:

deque<int> topologicalSorted; 

if (topologicalSort()) { 
     // Print the results. 
     for (int i = 0; i < topologicalSorted.size(); i++) { 
      cout << topologicalSorted.at(i) << ","; 
     } 
     cout << endl; 
    } 

코드는 depth_first 위상 종류를 얻을 수