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