Найти все топологические сортировки в DAG, используя BGL (библиотека графов Boost)
Как использовать библиотеку графов повышения, чтобы найти все топологические виды данного DAG G?
Я нашел некоторые теоретические ссылки, объясняющие, что это возможно, есть также это код где есть реализация. Но на самом деле я не хочу начинать с нуля, и я хочу использовать BGL для их вычисления.
Решение
Одной из стратегий было бы получить все вершины без предшественников (без направленных ребер к нему). И умножение векторов на основе вершин без предшественников. Если у вас есть C ++ для этого, пожалуйста, поделитесь.
Код для получения топологической сортировки глубины:
Учитывая DAG graph с типом вершины 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;
}
Другие решения
Других решений пока нет …