0

私はツリー（グラフの意味で）ツリー（物理的な意味で）の表現を持っています。ツリーは、各頂点に半径と位置のプロパティが含まれる BGL 隣接リストとして表されます。つまり、グラフは次の形式で定義されます。

struct TreeVertexType {
  double radius;
  double position[3]; 
}

typedef adjacency_list<vecS, vecS, undirectedS, TreeVertexType> Tree;

ブランチのリストを作成するために、ツリーで DFS を実行したいと考えています。追加の要件は、頂点に複数の未探索の隣接頂点がある場合は常に、最大の半径を持つ頂点を選択することです。このルールにより、グラフの走査順序が物理的なツリー ブランチを表すようになります。

DFS ビジターはプライオリティ キューをサポートしていないようです。そのため、おそらく A* 経由でこの情報を取得する別の検索方式があるかどうか疑問に思っていました。

別の方法として、頂点をソートして独自の DFS アルゴリズムを実装することもできますが、可能であれば BGL フレームワークを活用したいと考えています。

ありがとう

-ジョン

4

4 に答える 4

3

DFS の間、boost::graph はスタックを使用して隣接する頂点をプッシュします。これらの頂点は、プッシュされる順序で後でポップされます。

std::vector<VertexInfo> stack;//depth_first_search.hpp の 94 行 boost_1_47_0

回避策として、同じ push() および pop() インターフェースを使用してこれを再定義できます。できることは、半径が最大の頂点が常に上になるように要素を並べ替えるだけです。 .stackVertexstackyour stack

つまり、独自のプライオリティ キューを使用してスタック インターフェイスを偽装します。

これにより、独自の DFS を作成する苦痛から解放されます。

于 2011-08-15T22:35:28.963 に答える
1

私はhttp://www.boost.org/doc/libs/1_34_0/libs/graph/example/ordered_out_edges.cppで提供されているロジックに従うことになりました。

template <class StoredEdge>
struct weight : public std::binary_function<StoredEdge, StoredEdge, bool>
{
    bool operator()(const StoredEdge &lhs, const StoredEdge &rhs) const {
        return boost::get(boost::edge_weight, lhs) > 
            boost::get(boost::edge_weight, rhs);
    }
};

struct weightS {};

namespace boost {
    template <class ValueType>
    struct container_gen<weightS, ValueType> {
        typedef std::multiset<ValueType, weight<ValueType> > type;
    };

    template <>
    struct parallel_edge_traits<weightS> {
        typedef disallow_parallel_edge_tag type;
    };
}

typedef adjacency_list<weightS, vecS, undirectedS, TreeVertexType> Tree;

out_edgesが半径に従って順序付けられていることを確認するために、エッジの重みをソース頂点とターゲット頂点の平均半径として定義しました。

ただし、問題は、半径の頂点プロパティが動的であり、グラフの作成時に不明であるため、エッジの重みを更新するたびにエッジの順序が変更されないことです。

誰かが別のアプローチを知っていますか？

ありがとう

-ジョン

于 2011-10-24T21:33:00.547 に答える
1

BGL の幅優先検索アルゴリズムは、ユース ケースにより適しています。名前が示すよりも一般的です。push、top、およびメソッドを使用して独自のキューをプラグインし、pop任意の順序付けを行うことができます。

于 2012-02-09T05:50:53.870 に答える