BGL DFS Visitor with Priority Queue

I have a tree (in the graph sense) representation of a tree (in the physical sense). The tree is represented as a BGL adjacency list where each vertex contains radius and position properties, i.e., my graph is defined in the form

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

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

I would like to perform a DFS on the tree in order to create a list of branches. The additional requirement is that whenever a vertex has more than one unexplored adjacent vertices that it chooses the vertex with the greatest radius. This rule ensure that the traversal order of the graph is representative of physical tree branches.

It seems that the DFS visitor does not support a priority queue and so I was wondering whether there's an alternative search formulation of obtaining this information maybe via开发者_如何转开发 A*?

Alternatively I can implement my own DFS algorithm by sorting vertices, but would rather leverage the BGL framework if possible.

Thanks

-John

During the DFS boost::graph uses a stack to push the adjacent vertices which will be popped later in the order that they are pushed.

std::vector<VertexInfo> stack; //line 94 boost_1_47_0 of depth_first_search.hpp

as a workaround you can redefine this stack with the same push() and pop() interface and what you can do is when any Vertex is pushed into the stack just sort the elements of your stack in a way that the vertex with the greatest radius always comes on the top.

In other words fake a stack interface with your own priority queue.

This will relieve you of the pain of writing your own DFS.

I ended up following the logic provided at http://www.boost.org/doc/libs/1_34_0/libs/graph/example/ordered_out_edges.cpp, i.e.,

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;

To ensure that the out_edges were ordered according to the radius, I simply defined the edge weight as the average radius of the source and target vertices.

The issue however is that the radius vertex property is dynamic and unknown at the time the graph is created, hence the edge ordering is unchanged whenever I update the edge weights.

Is anyone aware of an alternative approach?

Thanks

-John

The breadth-first search algorithm in BGL would fit your use case better; it is more general than the name implies. You can plug in your own queue with push, top, and pop methods that do whatever ordering you want.

You can use setS instead of vecS to specify a container with ordering on that particular attribute. E.g., if you wanted to order edges, you would use adjacency_list<setS, ...> and have a comparison operator for TreeVertexType.