c++ - 有向无环图 : Updating the vertex property of a parent node by comparing the property of the child nodes.

Question

我在 DAG 中的节点之间有这样的连接。

1 --> 7
2 -->
3 --> 4 5
4 --> 6
5 --> 
6 --> 
7 -->

我必须在此图上执行一些任务。 1) 找到所有没有后继的顶点。 2) 为没有后继的顶点赋值。 (我可以用顶点属性来做到这一点)。 3) 回溯图，用子节点的最小值更新每一层的所有父节点(甚至中间父节点)。

例如，

根据上述 DAG，顶点 {2,5,6,7} 没有任何后继或出边。 假设我将值 {3,2,4,6} 分别分配给顶点 {2,5,6,7}。

由于顶点 4 是 5 和 6 的父节点，我必须将值 min{2,4} = 2 添加到顶点 4。 同样，1 是 7 的父节点。所以我必须将值 6 添加到节点 1。

我可以知道每个步骤可以使用哪些函数，以便“搜索”时间最少。

我也想知道，在使用 boost 的 DAG 中是否可以实现上述内容。

Answer 1

为了好玩:

I have the connections between nodes in a DAG like this.

using G = boost::adjacency_list<>;
G g(8);
add_edge(1, 7, g);
add_edge(3, 4, g);
add_edge(3, 5, g);
add_edge(4, 6, g);

Assume I will assign values {3,2,4,6} to vertices {2,5,6,7} respectively.

auto p = boost::make_vector_property_map<int>(id);
p[2] = 3; p[5] = 2; p[6] = 4; p[7] = 6;

3) Back trace the graph [...]

std::vector<V> order;
topological_sort(g, back_inserter(order));

[...] and update all the parent node (Even the intermediate parent node) at each level with the minimum value of the children.

auto getter = [&p](V vd) { return p[vd]; };
for (V vd : order) {
    auto child = make_iterator_range(adjacent_vertices(vd, g));
    if (child.size())
        p[vd] += *min_element(child | transformed(std::cref(getter)));
}

您没有指定它，但您可能希望看到结果:

print_graph(g, boost::make_transform_value_property_map(
                [&](V vd) { return "vertex #" + std::to_string(vd) + " (" + std::to_string(p[vd]) + ")"; }, id
            ));

演示

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/topological_sort.hpp>
#include <boost/property_map/transform_value_property_map.hpp>
#include <boost/range/adaptors.hpp>
#include <boost/range/algorithm/min_element.hpp>

using boost::adaptors::transformed;

int main() {
    using G = boost::adjacency_list<>;
    using V = G::vertex_descriptor;
    /*
     *1 --> 7
     *2 -->
     *3 --> 4 5
     *4 --> 6
     *5 --> 
     *6 --> 
     *7 -->
     */
    G g(8);
    add_edge(1, 7, g);
    add_edge(3, 4, g);
    add_edge(3, 5, g);
    add_edge(4, 6, g);

    // {3,2,4,6} to vertices {2,5,6,7}
    auto id = get(boost::vertex_index, g);
    auto p = boost::make_vector_property_map<int>(id);
    p[2] = 3; p[5] = 2; p[6] = 4; p[7] = 6;

    std::vector<V> order;
    boost::topological_sort(g, back_inserter(order));

    auto getter = [&p](V vd) { return p[vd]; };
    for (V vd : order) {
        auto child = make_iterator_range(adjacent_vertices(vd, g));
        if (child.size())
            p[vd] += *min_element(child | transformed(std::cref(getter)));
    }

    print_graph(g, boost::make_transform_value_property_map(
                    [&](V vd) { return "vertex #" + std::to_string(vd) + " (" + std::to_string(p[vd]) + ")"; },
                    id));
}

输出:

vertex #0 (0) --> 
vertex #1 (6) --> vertex #7 (6) 
vertex #2 (3) --> 
vertex #3 (2) --> vertex #4 (4) vertex #5 (2) 
vertex #4 (4) --> vertex #6 (4) 
vertex #5 (2) --> 
vertex #6 (4) --> 
vertex #7 (6) --> 

注意

将此视为问题的答案“我也想知道，上面提到的事情在使用 boost 的 DAG 中是否可行。”。不要将此作为您的解决方案。

我特意以一些天赋和简洁的方式编写了这个解决方案。它将帮助您入门，但请确保您了解其中的每一步。事实上，使用适当的 bundled properties 重写它、正确的顶点 ID 映射、正确的输出等。

买者自负。你的教育是你自己的责任。学习是他们所有人中最伟大的技能。

奖励:可视化

使用 graphviz 并过滤零顶点:

struct NotZero { bool operator()(V vd) const { return 0 != vd; } };
using F = boost::filtered_graph<G, boost::keep_all, NotZero>;

boost::dynamic_properties dp;
dp.property("node_id", id);
dp.property("shape", boost::make_constant_property<V>(std::string("Mrecord")));
dp.property("label", label);

write_graphviz_dp(std::cout, F(g, {}, {}), dp);

Live On Coliru