具有优先队列的 BGL DFS 访问者

Question

我有一个树（在图形意义上）表示一棵树（在物理意义上）。该树表示为 BGL 邻接列表，其中每个顶点包含半径和位置属性，即，我的图以

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

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

我希望在树上执行 DFS 的形式定义，以便创建分支列表。附加要求是，每当一个顶点有多个未探索的相邻顶点时，它就会选择半径最大的顶点。该规则确保图的遍历顺序代表物理树分支。

看来 DFS 访问者不支持优先级队列，所以我想知道是否有另一种搜索公式可以通过 A* 获取此信息？

或者，我可以通过对顶点进行排序来实现我自己的 DFS 算法，但如果可能的话，我宁愿利用 BGL 框架。

谢谢

-约翰

Answer 1

在DFS期间，boost::graph使用堆栈来压入相邻的顶点，这些顶点稍后将按照压入的顺序弹出。

std::vectorstack; //deep_first_search.hpp 的第 94 行 boost_1_47_0

作为解决方法，您可以使用相同的 push() 和 pop() 接口重新定义此stack以及什么您可以做的是，当任何 Vertex 被推入 stack 时，只需对 stack 的元素进行排序，方法是半径最大的顶点总是出现在 顶部。

换句话说，用您自己的优先级队列伪造堆栈接口。

这将减轻您编写自己的 DFS 的痛苦。

Answer 2

我最终遵循了 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按照半径，我简单地将边权重定义为源顶点和目标顶点的平均半径。

然而问题是，半径顶点属性是动态的，并且在创建图时是未知的，因此每当我更新边权重时，边顺序都不会改变。

有人知道替代方法吗？

谢谢

-约翰

Answer 3

BGL 中的广度优先搜索算法将更适合您的用例；它比名字所暗示的更通用。您可以使用 push、top 和 pop 方法插入自己的队列，执行您想要的任何排序。

Answer 4

您可以使用 setS 而不是 vecS 来指定按特定属性排序的容器。例如，如果您想对边进行排序，则可以使用 adjacency_list 并为 TreeVertexType 使用比较运算符。