2

グラフ内のすべての頂点にアクセス、フィルタリング、インデックス付けなどを行わずに、BGLの頂点からある程度の距離まで、深さまたは幅の最初の検索/訪問を実行することは可能ですか？

私が何とか書いた最も近いものは（グラフ0 <-> 1 <-> 2 <-> 3 <-> 4 <-> 5を作成しますが、頂点0から3にのみアクセスします）：

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>

using namespace std;

struct custom_dfs_visitor : public boost::default_dfs_visitor {
    template < typename Vertex, typename Graph >
    void discover_vertex(const Vertex& v, const Graph& g) const {
        std::cout << v << std::endl;
    }
};

struct Terminator {
    template<class Vertex, class Graph>
    bool operator()(const Vertex& v, const Graph& g) {
        return v > 2;
    }
};

int main()
{
    typedef boost::adjacency_list<
        boost::vecS,
        boost::vecS,
        boost::undirectedS
    > Graph_T;

    Graph_T g(6);
    boost::add_edge(0, 1, g);
    boost::add_edge(1, 2, g);
    boost::add_edge(2, 3, g);
    boost::add_edge(3, 4, g);
    boost::add_edge(4, 5, g);

    std::vector<boost::default_color_type> color_map(boost::num_vertices(g));
    boost::depth_first_visit(
        g,
        boost::vertex(0, g),
        custom_dfs_visitor(),
        boost::make_iterator_property_map(
            color_map.begin(),
            boost::get(boost::vertex_index, g),
            color_map[0]
        ),
        Terminator()
    );

    return 0;
}

これは、すべての頂点にアクセスする代わりに0 1 2 3のみを出力しますが、コードには、グラフ全体と同じ大きさのカラーマップが必要です（boost :: num_vertices（g））。検索の複雑さをグラフのエッジ/頂点の総数とまったく比較できないようにする方法はありますか？

グラフのさまざまな部分で多くの検索が行われるため、バンドルされた色を使用することは許容されますが、O（number_of_vertices）から同じグラフでの個々の検索の複雑さを軽減することは可能ですか？ターミネーターがtrueに戻ったときに、頂点の初期カラーリングも停止することを願っていますが、それはすでに処理されているようです。おそらく関連する質問：グラフがvecS以外のものを使用している場合、インデックス付けはどうですか？その場合、BFS / DFSはインデックス付けなしで実行できますか？助けてくれてありがとう。

4

1 に答える 1

0

これを実現する最も簡単な方法は、バンドルされたプロパティを使用することです。colorプロパティがすべての頂点に含まれているという事実は、dfsが実行されるたびに各頂点のcolorプロパティを作成するよりも優れています。グラフの種類は次のようになります

typedef boost::adjacency_list<
    boost::vecS,
    boost::vecS,
    boost::undirectedS,
    property<vertex_color_t, boost::default_color_type>
> Graph_T;

dfvの呼び出しは

depth_first_visit(
    g,
    vertex(0, g),
    custom_dfs_visitor(),
    get(vertex_color_t(), g),
    Terminator()
);

上記の場合、100 Mの頂点を持つグラフで制限されたdfsを実行しても、メモリ消費量（合計メモリの76.2％）は増加しませんが、色の外部ベクトルを使用すると、検索中のメモリ使用量は76.2％から78.5％に増加します。

于 2013-07-05T18:43:17.763 に答える