Boost.Graph トポロジカルソート

閉路を持たない有向グラフ(DAG : Directed Acyclic Graph)に順序を付けるトポロジカルソートのために、Boost.Graphにboost::topological_sort()関数が用意されています。
topological_sort()関数は、グラフに対するconst参照と、結果を返すためのOutput Iteratorを引数にとります。

以下の有向グラフに、トポロジカルソートを適用してみます：

#include <iostream>
#include <vector>
#include <iterator>
#include <utility>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/topological_sort.hpp>
#include <boost/range/algorithm/for_each.hpp>
#include <boost/range/adaptor/reversed.hpp>

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS> Graph;
typedef std::pair<int, int> Edge;

Graph make_graph()
{
    const std::vector<Edge> edges = {
        {0, 1}, {2, 4},
        {2, 5},
        {0, 3}, {1, 4},
        {4, 3}
    };
    return Graph(edges.begin(), edges.end(), 6);
}

int main()
{
    const Graph g = make_graph();

    std::vector<int> result;
    boost::topological_sort(g, std::back_inserter(result));

    boost::for_each(result | boost::adaptors::reversed, [](int vertex) {
        std::cout << vertex << std::endl;
    });
}

2
5
0
1
4
3

2 → 5 → 0 → 1 → 4 → 3の順に並びました。
boost::topological_sort()は、トポロジカルソートされた頂点を逆順で返すので、boost::adaptors::reversedなどで正順に直して使います。

ちなみに、閉路のあるグラフを渡すとboost::not_a_dag例外が投げられます。

#include <iostream>
#include <vector>
#include <iterator>
#include <utility>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/topological_sort.hpp>
#include <boost/range/algorithm/for_each.hpp>
#include <boost/range/adaptor/reversed.hpp>

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS> Graph;
typedef std::pair<int, int> Edge;

Graph make_graph()
{
    const std::vector<Edge> edges = {
        {0, 1}, {2, 4},
        {2, 5},
        {3, 0}, {1, 4}, // 0, 3を3, 0に変更
        {4, 3}
    };
    return Graph(edges.begin(), edges.end(), 6);
}

int main()
{
    const Graph g = make_graph();

    try {
        std::vector<int> result;
        boost::topological_sort(g, std::back_inserter(result));

        boost::for_each(result | boost::adaptors::reversed, [](int vertex) {
            std::cout << vertex << std::endl;
        });
    }
    catch (boost::not_a_dag& e) {
        std::cout << e.what() << std::endl;
    }
}

The graph must be a DAG.

参照：
boost::topological_sort() - Boost Graph Library
boost::not_a_dag exception - Boost Graph Library
トポロジカル・ソートとは