c++ - 基于最大深度迭代 boost 图顶点

Question

我想根据来自任何根顶点的顶点的最大深度迭代图形的顶点。

例如顶点的最大深度I是 3(并且在下图中用此值进行了注释)。因此，任何排序都是可以接受的:{A , B , C , D} , {E , F , G} , {H}, {I} , 其中花括号中的任何顶点 {}可以任意订购。

我遇到了一个有点 similar question但它旨在获得单个顶点的最大深度并且似乎假设单个根节点。



我对 boost 图很陌生，但这是我对解决方案可能类似于的微弱尝试

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>

using namespace boost;

class depth_visitor : public default_dfs_visitor
{
public:
    template <typename Vertex , typename Graph >
    void discover_vertex(Vertex v , const Graph & g) const
    {
        // update 'depth' of vertex 
    }
};


int main()
{
  enum { A , B, C, D, E, F, G , H , I , COUNT };
  const char* name[] = { "A" , "B" , "C" , "D" , "E" , "F" , "G" , "H" , "I" };

  typedef std::pair <int, int >Edge;
  Edge edge_array[] = { Edge(D, G), Edge(C, G), Edge(C, F), Edge(B, F), Edge(B, E), Edge(A, E),
                        Edge(G, H), Edge(F, I), Edge(E, H), Edge(H, I) };

    typedef adjacency_list < vecS, vecS, directedS > graph_t;
    graph_t g( edge_array , edge_array + sizeof(edge_array) / sizeof(E), COUNT );

    depth_visitor vis;
    depth_first_search( g , visitor( vis ) );
}

Answer 1

安迪说的:您可以手动遍历外边缘。

或者，您可以使用 BFS与自定义访问者。你已经有了类似的想法。

这是它的一个实现:

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <iostream>
#include <map>

现在，让我们定义我们的类型:

using Name   = char;
using Graph  = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, Name>;
using Edge   = Graph::edge_descriptor;
using Vertex = Graph::vertex_descriptor;

让我们创建我们自己的最大距离记录器。这大致基于 distance_recorder<> 来自 Boost 的类，它是一个 EventVisitor .

在我们的例子中，我们将过滤 on_tree_edge仅事件(因为我们不关心这里的非树图)。

using Depths = std::map<Vertex, size_t>;

struct Recorder : public boost::base_visitor<Recorder> {
    using event_filter = boost::on_tree_edge;

    Depths& _ref;
    Recorder(Depths& r):_ref(r){}

    void operator()(Edge e, const Graph& g) const {
        auto s = source(e, g), t = target(e, g);
        std::cout << "TREE EDGE " << g[s] << " -> " << g[t] << "\n";

        auto srcit = _ref.find(s);
        auto depth = srcit!=_ref.end()? srcit->second+1: 1;

        if (auto [it, isnew] = _ref.emplace(t, depth); !isnew) {
            it->second = std::max(it->second, depth);
        }
    }
};

你可以看到它基本上只是更新了一个 std::map但有以下特殊处理:

更新现有值时，它会更新 最大 当前距离和之前记录的距离。

它不会为树边缘未到达的顶点插入深度(基本上，它不使用 operator[source_vertex] 会插入深度为 0 的条目)

有了这个，我们所需要的就是调用算法:

std::vector roots { A, B, C, D };

Depths depths;
Recorder r{depths};

for (auto root : roots)
    boost::breadth_first_search(
        g, root,
        queue, boost::make_bfs_visitor(r), color_map);

for (auto [v,d] : depths)
    std::cout << g[v] << " at " << d << "\n";

Important Notes:

• use breadth_first_search as opposed to breadth_first_visit because otherwise the color_map would not be re-initialized on each root node. This would make already-discovered nodes always be skipped, which means we would not correctly get the maximum distance

• this is also the reason we couldn't use the multi-source overload like so:

  // WARNING BROKEN!
  boost::breadth_first_search(
          g, begin(roots), end(roots),
          queue, boost::make_bfs_visitor(r), color_map);
  

  the effect would be the same because there's no re-initialization of the color-map for each root node.

现场演示

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <iostream>
#include <map>

using Name   = char;
using Graph  = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, Name>;
using Edge   = Graph::edge_descriptor;
using Vertex = Graph::vertex_descriptor;

using Depths = std::map<Vertex, size_t>;

struct Recorder : public boost::base_visitor<Recorder> {
    using event_filter = boost::on_tree_edge;

    Depths& _ref;
    Recorder(Depths& r):_ref(r){}

    void operator()(Edge e, const Graph& g) const {
        auto s = source(e, g), t = target(e, g);
        std::cout << "TREE EDGE " << g[s] << " -> " << g[t] << "\n";

        auto srcit = _ref.find(s);
        auto depth = srcit!=_ref.end()? srcit->second+1: 1;

        if (auto [it, isnew] = _ref.emplace(t, depth); !isnew) {
            it->second = std::max(it->second, depth);
        }
    }
};

int main() {
    enum : Vertex { A, B, C, D, E, F, G, H, I, COUNT };
    Graph g(COUNT);

    // give names
    for (auto v : boost::make_iterator_range(vertices(g)))
        g[v] = 'A' + v;

    // add edges
    for (auto [s,t] : {
            std::pair(D,G), {D, G}, {C, G}, {C, F}, {B, F}, {B, E}, {A, E},
            {G, H}, {F, I}, {E, H},
            {H, I} })
    {
        add_edge(s, t, g);
    }

    std::vector roots { A, B, C, D };
    boost::queue<Vertex> queue;
    std::vector<boost::default_color_type> colors(num_vertices(g));
    auto color_map = boost::make_iterator_property_map(begin(colors), get(boost::vertex_index, g));

    Depths depths;
    Recorder r{depths};

    for (auto root : roots)
        boost::breadth_first_search(
            g, root,
            queue, boost::make_bfs_visitor(r), color_map);

    for (auto [v,d] : depths)
        std::cout << g[v] << " at " << d << "\n";
}

哪个打印

TREE EDGE A -> E
TREE EDGE E -> H
TREE EDGE H -> I
TREE EDGE B -> F
TREE EDGE B -> E
TREE EDGE F -> I
TREE EDGE E -> H
TREE EDGE C -> G
TREE EDGE C -> F
TREE EDGE G -> H
TREE EDGE F -> I
TREE EDGE D -> G
TREE EDGE G -> H
TREE EDGE H -> I
E at 1
F at 1
G at 1
H at 2
I at 3

更新

稍微改变以“通过蛮力”检测根:

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <iostream>
#include <map>

using boost::make_iterator_range;
using Name   = char;
using Graph  = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, Name>;
using Edge   = Graph::edge_descriptor;
using Vertex = Graph::vertex_descriptor;

using Depths = std::map<Vertex, size_t>;

struct Recorder : public boost::base_visitor<Recorder> {
    using event_filter = boost::on_tree_edge;

    Depths& _ref;
    Recorder(Depths& r):_ref(r){}

    void operator()(Edge e, const Graph& g) const {
        auto depth = 1 + _ref[source(e, g)];

        if (auto [it, isnew] = _ref.emplace(target(e, g), depth); !isnew) {
            it->second = std::max(it->second, depth);
        }
    }
};

int main() {
    enum : Vertex { A, B, C, D, E, F, G, H, I, COUNT };
    Graph g(COUNT);

    // give names
    for (auto v : make_iterator_range(vertices(g)))
        g[v] = 'A' + v;

    // add edges
    for (auto [s,t] : {
            std::pair(D,G), {D, G}, {C, G}, {C, F}, {B, F}, {B, E}, {A, E},
            {G, H}, {F, I}, {E, H},
            {H, I} })
    {
        add_edge(s, t, g);
    }

    boost::queue<Vertex> queue;
    std::vector<boost::default_color_type> colors(num_vertices(g));
    auto color_map = boost::make_iterator_property_map(begin(colors), get(boost::vertex_index, g));

    Depths depths;
    Recorder r{depths};

    for (auto v : make_iterator_range(vertices(g))) {
        boost::breadth_first_search(g, v, queue, boost::make_bfs_visitor(r), color_map);
    }

    std::map<size_t, std::set<Vertex> > by_depth;
    for (auto [v,d] : depths)
        by_depth[d].insert(v);

    for (auto& [d,vs] : by_depth) {
        std::cout << "depth:" << d;
        for (auto v : vs) std::cout << " " << g[v];
        std::cout << "\n";
    }
}

打印

depth:0 A B C D
depth:1 E F G
depth:2 H
depth:3 I