有向无环图：通过比较子节点的属性来更新父节点的顶点属性。

Question

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

我必须在这个图上执行一些任务。1）找到所有没有后继的顶点。2）给没有后继的顶点赋值。（我可以用顶点属性来做这件事）。3）回溯图并用子节点的最小值更新每一层的所有父节点（甚至是中间父节点）。

例如，

根据上面的DAG，顶点{2,5,6,7}没有任何后继或外边。假设我将分别为顶点{2,5,6,7}赋值{3,2,4,6}。

Answer 1

为了好玩：

我有DAG中节点之间的连接，就像这样。

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);

假设我将分别为顶点{2,5,6,7}赋值{3,2,4,6}。

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;
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
            ));

#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) --> 

这是对“我也想知道，上面提到的东西是否可以在DAG中使用Boost”这个问题的回答。不要把这个作为你的解决方案。

我故意用一些技巧和简洁来写这个解决方案。它会帮助你开始一些事情，但请确保你理解方法的每一步。实际上，使用适当的捆绑属性、适当的顶点id映射、适当的输出等重写它。

备注备注者。你的教育是你自己的责任。学习是他们中最伟大的技能。

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);