Boost Graph Library:防止DFS访问未连接的节点 [英] Boost Graph Library: Prevent DFS from visiting unconnected nodes

问题描述

我有一个双向图.一些顶点是未连接的.我使用 boost :: depth_first_search 遍历顶点.我还提供了起始源节点.我看到在连接节点完成后，未连接的顶点也会被处理.如何防止访问此类节点?实际上，如何告诉DFS仅访问源节点可访问的那些节点，而不访问其他节点?

I have a bidirectional graph. Some of the vertices are unconnected. I use boost::depth_first_search to traverse the vertices. I also supply the starting source node. I see that the unconnected vertices are also processed after the connected nodes are done. How can I prevent visiting such nodes? In fact, how can I tell DFS to only visit those nodes reachable from the source node and don't visit anything else?

我有以下代码:

/// Define vertex properties.
struct NodeProperty
{
    unsigned     id;              /// Id.
    unsigned     kind;            /// Kind.
    unsigned     depth;           /// Depth.
    unsigned     layer_color;     /// Layer color.
    unsigned     signal_color;    /// Signal color.
    unsigned     sch_color;       /// Sch color.
    CBoundingBox bounds;          /// Bounds of polygon.

    NodeProperty()
        : id(0), kind(0), depth(0), layer_color(0), signal_color(0), sch_color(0), bounds(0,0,0,0)
    {
        ;
    }
};
/// Define net topology graph.
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, NodeProperty> Graph;

class receiver_visitor : public boost::default_dfs_visitor
{
    public:
        receiver_visitor(std::vector<Vertex>& r)
            : res(r)
        {
            ;
        }

        void discover_vertex(Vertex v, Graph const& g) const
        {
            std::cout << "Visit: " << v << std::endl;
            if (g[v].sch_color) {
                res.push_back(g[v].sch_color);
            }
        }

        std::vector<Vertex>& res;
 };

 std::vector<std::size_t>
 NetTopology::getReceivers(std::size_t src) const
 {
     std::vector<Vertex> r;
     receiver_visitor vis(r);
     boost::depth_first_search(data_->g, boost::visitor(vis).root_vertex(src));

     return r;
}

推荐答案

您要使用depth_first_visit，而不是depth_first_search.

这篇关于Boost Graph Library:防止DFS访问未连接的节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！