基于最大深度迭代提升图顶点

Question

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

例如顶点的最大深度 I 是 3（在下图中用这个值注释）。因此任何排序都是可以接受的：{A , B , C , D} , {E , F , G} , {H}, {I}，其中花括号 {} 中的任何顶点都可以任意排序。

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

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

#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

Andy 所说：您可以手动遍历出边。

或者，您可以将 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<> class from Boost, which is an 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

更新

稍微改动以检测根 "by brute force":

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

基于最大深度迭代提升图顶点

Iterating over boost graph vertexes based on maximal depth

c++

boost

boost-graph

现场演示

更新