Направленный ациклический граф: Обновление свойства вершины родительского узла путем сравнения свойства дочерних узлов.
У меня есть соединения между узлами в 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.
Решение
Ради забавы:
У меня есть соединения между узлами в 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);
Другие решения
Других решений пока нет …