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() 接口重新定义它stack，您可以做的是，当任何Vertex被推入时，stack只需对元素进行排序your stack，使半径最大的顶点始终位于顶部.

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

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

于 2011-08-15T22:35:28.963 回答
1

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

于 2012-02-09T05:50:53.870 回答
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 回答
0

您可以使用setS而不是vecS指定具有对该特定属性的排序的容器。例如，如果您想对边进行排序，您将使用adjacency_list<setS, ...>and 有一个比较运算符TreeVertexType。

于 2011-08-15T21:47:03.587 回答