Алгоритм Ленгауэра Тарьяна в BGL (библиотека повышенных графов)

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

Я определил следующий тип для моего графика (для анализа)

typedef boost::adjacency_list<boost::listS, boost::vecS,
boost::bidirectionalS, vertex_info, edge_info> Graph;

и я хотел бы иметь другой объект, содержащий соответствующее дерево доминант. Я попробовал следующее:

  // dominator tree is an empty Graph object
dominator_tree = trace;

typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
typedef typename boost::property_map<Graph, boost::vertex_index_t>::type IndexMap;
typedef typename boost::iterator_property_map<typename std::vector<Vertex>::iterator, IndexMap> PredMap;

IndexMap indexMap(get(boost::vertex_index, dominator_tree));

std::vector<Vertex> domTreePredVector = std::vector<Vertex>(
num_vertices(dominator_tree),
boost::graph_traits<Graph>::null_vertex());

PredMap domTreePredMap = make_iterator_property_map(
domTreePredVector.begin(), indexMap);

lengauer_tarjan_dominator_tree(dominator_tree, vertex(0, dominator_tree),
domTreePredMap);

Когда я выводю содержимое dominator_tree в файл .dot, оно точно такое же, как в trace. То есть похоже, что вызов последней строки выше ничего не изменил. Входной график выглядит так:
http://s24.postimg.org/y17l17v5x/image.png

Узлом INIT является узел 0. Если я выберу любой другой узел в качестве второго аргумента функции, он все равно возвращает идентичный результат.

Что я делаю неправильно?? Цени любую помощь.

1

Решение

Смотрю на документацию ( http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/lengauer_tarjan_dominator.htm ) Я вижу, что первый параметр помечен IN.

Это означает, что это ТОЛЬКО входной параметр. Так что не стоит ожидать, что это изменится!

ТРЕТИЙ параметр отмечен OUT. Так что это значение, которое будет изменено после вызова. Согласно документации:

OUT: DomTreePredMap domTreePredMap Доминирующее дерево, где родители
являются непосредственными доминантами каждого ребенка.

Итак, если вы хотите, чтобы график был изменен, вам придется сделать это самостоятельно: удалить все существующие ребра, а затем выполнить итерацию по дереву, добавляя ребра в граф, как указано в дереве.

2

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

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