BGL（Boostグラフライブラリ）を使用してDAG内のすべてのトポロジカルソートを検索する

Question

ブーストグラフライブラリを使用して、特定のDAG Gのトポロジカルなソートをすべて見つける方法を教えてください。

これは可能であることを説明する理論的な参考文献をいくつか見つけました。実装があるのはcodeです。しかし、実際には最初からやりたいとは思っていません。BGLを使って計算したいと思います。

Answer 1

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トポロジカルソートを取得します