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

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。

我可以知道我可以在每个步骤中使用哪些功能，以便 "Search" 时间最少。

我也想知道，上面提到的东西在使用 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) -->

注意

将此视为对问题 "I also wanted to know, is something above mentioned possible in a DAG using boost." 的回答。不要将此作为您的解决方案。

我特意以一些天赋和简洁的方式编写了这个解决方案。它将帮助您开始一些工作，但请确保您了解其中的每一步。事实上，使用适当的 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

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

Directed Acyclic Graph : Updating the vertex property of a parent node by comparing the property of the child nodes.

c++

boost

directed-acyclic-graphs

演示

注意

奖励：可视化