使用BGL（Boost圖庫）查找DAG中的所有拓撲排序

Question

如何使用Boost圖庫來查找給定DAG的所有拓撲排序G？

我發現了一些理論上的參考資料，說明這是可能的，也有這個code哪裏有一個實現。但我並不想從頭開始，我想用BGL來計算它們。

Answer 1

一種策略是獲得所有沒有前輩的頂點（沒有有向邊）。並且將基於頂點的矢量相乘而不需要前輩。如果你有一個C++來做，請分享。

代碼即可獲得depth_first拓撲排序：

給定一個DAG 與頂點類型vertex_t：

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; 
} 

沒有自定義頂點：

deque<int> topologicalSorted; 

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