Направленный ациклический граф: Обновление свойства вершины родительского узла путем сравнения свойства дочерних узлов.

У меня есть соединения между узлами в DAG, как это.

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

Я должен выполнить некоторые задачи на этом графике.
1) Найти все вершины без преемников.
2) Присвойте значение вершинам без преемников. (Я могу сделать это с помощью свойств Vertex).
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.

Могу ли я узнать, какие функции я могу использовать для каждого шага, чтобы время поиска было минимальным.

Я также хотел знать, возможно ли что-то вышеупомянутое в DAG с использованием boost.

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

Предположим, я назначу значения {3,2,4,6} вершинам {2,5,6,7} соответственно.

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

3) Обратный ход графика […]

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

DEMO

Жить на Колиру

#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».. Не включайте это в качестве решения.

Я намеренно написал это решение с некоторым изяществом и краткостью. Это будут помочь вам начать что-то, но, пожалуйста, убедитесь, что вы понимаете каждый шаг на этом пути. На самом деле, переписать его с помощью правильного связанные свойства, правильное отображение идентификатора вершины, правильный вывод и т. д.

Пусть покупатель будет бдителен. Ваше образование является вашей собственной ответственностью. Обучение — величайший навык из всех.

БОНУС: Визуализируйте

Используя 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);

Жить на Колиру

введите описание изображения здесь

3

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector