1

次のコードはコンパイルされません。

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/topological_sort.hpp>
#include <boost/function_output_iterator.hpp>

typedef boost::adjacency_list<
    boost::setS, // outedge list
    boost::setS, // vertex list
    boost::directedS, // undirected 
    boost::no_property, // vertex prop
    boost::no_property, // edge prop
    boost::no_property, // graph prop
    boost::setS // edgelist
> Graph;

bool hasCycle(const Graph& aG) 
{
    try {
        boost::topological_sort(
            aG, 
            boost::make_function_output_iterator([](int){}));
    } catch(boost::not_a_dag const&)
    {
        return true;
    }
    return false;
 }

頂点リストを vecS http://coliru.stacked-crooked.com/a/abeb9e3f96e92af0に変更した後に機能します。

DFS が確定的なアクセスを必要とするため、この制限はありますか?

ありがとうございました、

4

1 に答える 1

3

「制限」は、頂点インデックスの必要性として文書化されています。1つ追加するか（ にも置き換える必要があることに注意してくださいint）Graph::vertex_descriptor、グラフタイプを調整して1つを含めることができます。

外部インデックス プロパティ マップの追加

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/topological_sort.hpp>
#include <boost/function_output_iterator.hpp>

typedef boost::adjacency_list<
    boost::setS, // outedge list
    boost::setS, // vertex list
    boost::directedS, // undirected 
    boost::no_property, // vertex prop
    boost::no_property, // edge prop
    boost::no_property, // graph prop
    boost::setS // edgelist
> Graph;

bool hasCycle(const Graph& aG)
{
    try {
        std::map<Graph::vertex_descriptor, size_t> index;
        auto pmap = boost::make_assoc_property_map(index);

        for (auto vd : boost::make_iterator_range(boost::vertices(aG)))
            index[vd] = index.size();

        boost::topological_sort(
            aG,
            boost::make_function_output_iterator([](Graph::vertex_descriptor){}),
            boost::vertex_index_map(pmap));
    }
    catch (boost::not_a_dag const&)
    {
        return true;
    }
    return false;
}

int main() {
}

内部インデックス プロパティ マップの追加

これは、発信者に負担を転嫁することになります。これは、アプリケーションのパフォーマンス要件によっては (かなり) 理にかなっている場合があります。

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/topological_sort.hpp>
#include <boost/function_output_iterator.hpp>

typedef boost::adjacency_list<
    boost::setS, // outedge list
    boost::setS, // vertex list
    boost::directedS, // undirected 
    boost::property<boost::vertex_index_t, int>, // vertex prop
    boost::no_property, // edge prop
    boost::no_property, // graph prop
    boost::setS // edgelist
> Graph;

bool hasCycle(const Graph& aG)
{
    try {
        boost::topological_sort(
            aG,
            boost::make_function_output_iterator([](Graph::vertex_descriptor){})
        );
    }
    catch (boost::not_a_dag const&)
    {
        return true;
    }
    return false;
}

#include <boost/graph/random.hpp>
#include <random>

int main() {
    std::mt19937 prng{ std::random_device{}() };
    Graph g;
    boost::generate_random_graph(g, 100, 200, prng);
    auto index = boost::get(boost::vertex_index, g);

    int gen_id = 0;
    for (auto vd : boost::make_iterator_range(boost::vertices(g))) {
        boost::put(index, vd, gen_id++);
        std::cout << "Vertex " << boost::get(index, vd) << "\n";
    }

    bool check = hasCycle(g);
}
于 2015-08-04T21:26:14.943 に答える