Вычисление графа доминанта с использованием алгоритма Лунгауэра Тарьяна Boost и его отображение с помощью graphviz

Question

Позвольте мне прежде всего извиниться, если я нарушил правила, так как я знаю, что мой вопрос уже задан здесь измененным образом: Lengauer Tarjan Algorithm in BGL (boost graph library). Тем не менее, я (по-прежнему) не могу использовать ответ для правильного отображения результата.

Чтобы быть более точным: я следил за ответом и успешно применил алгоритм Ленгауэра-Тарьяна к моему графику (который для удобства является частью документации Boost: http://www.boost.org/doc/libs/1_55_0/libs/graph/test/dominator_tree_test.cpp). Теперь, если понять код правильно соответствующую информацию о владычества дерева хранится в domTreePredMap, который имеет тип PredMap:

const int numOfVertices = testSet[i].numOfVertices; 
//See example for test_sets - it just the same routine 
G g(
    testSet[i].edges.begin(), testSet[i].edges.end(), 
    numOfVertices); 

typedef graph_traits<G>::vertex_descriptor Vertex; 
typedef property_map<G, vertex_index_t>::type IndexMap; 
typedef 
    iterator_property_map<vector<Vertex>::iterator, IndexMap> 
    PredMap; 

vector<Vertex> domTreePredVector, domTreePredVector2; 
IndexMap indexMap(get(vertex_index, g)); 
graph_traits<G>::vertex_iterator uItr, uEnd; 
int j = 0; 
for (tie(uItr, uEnd) = vertices(g); uItr != uEnd; ++uItr, ++j) 
{ 
    put(indexMap, *uItr, j); 
} 

// Lengauer-Tarjan dominator tree algorithm 
domTreePredVector = 
    vector<Vertex>(num_vertices(g), graph_traits<G>::null_vertex()); 
PredMap domTreePredMap = 
    make_iterator_property_map(domTreePredVector.begin(), indexMap); 

lengauer_tarjan_dominator_tree(g, vertex(0, g), domTreePredMap);` 

Для меня одна из главных преимуществ бустера является возможность автоматически генерируется графический вывод с помощью Graphviz с write_graphviz (соиЬ, г), где г представляет собой граф из ЬурейеЕ G:

typedef adjacency_list< 
    listS, 
    listS, 
    bidirectionalS, 
    property<vertex_index_t, std::size_t>, no_property> G; 

Однако, я не могу перевести DomTreePredMap в нечто write_graphviz (COUT, X) можно понять. Я ценю любую помощь, излагающую, как график можно построить из domTreePredMap, который может быть напечатан с использованием графика.

Спасибо, что прочитали все это и помогли мне.

Answer 1

Извините, что беспокою вас - мне удалось найти ответ сам в повышающего документальном:

Вот минимальный рабочий пример, чтобы проиллюстрировать мою проблему. В принципе, я хочу вычислить график (один слева) и его доминантное дерево (справа), как показано здесь: http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/lengauer_tarjan_dominator.htm#fig:dominator-tree-example и распечатать оба графика с помощью graphviz.

Следуя примеру, мне удалось вычислить и распечатать исходный граф и выполнить на нем алгоритмы Ленгауэра-Тарджана. Информация о дереве доминантов хранится в DomPredMap и может быть скопирована в целочисленный вектор. В позиции i вектора idom хранится идентификатор родителя узла i. Если родительский узел не существует, сохраняется max_int. Эта информация может быть использована для добавления ребер из idom [i] в ​​i в testSet, из которого можно окончательно построить граф g2. Спасибо вам за вашу помощь и терпение.

#include <iostream> 
#include <boost/graph/graphviz.hpp> 
#include <boost/graph/adjacency_list.hpp> 
#include <boost/graph/dominator_tree.hpp> 
#include <algorithm> 
#include <fstream> 
#include <cstdlib> 
#include <string> 
#include <sstream> 
#include <vector> 
using namespace std; 


struct DominatorCorrectnessTestSet 
    { 
     typedef pair<int, int> edge; 

     int numOfVertices; 
     vector<edge> edges; 
     vector<int> correctIdoms; 
    }; 

    using namespace boost; 

    typedef adjacency_list< 
     listS, 
     listS, 
     bidirectionalS, 
     property<vertex_index_t, std::size_t>, no_property> G; 

    int main(int, char*[]) 
    { 



    typedef DominatorCorrectnessTestSet::edge edge; 

     DominatorCorrectnessTestSet testSet[1]; 



     testSet[0].numOfVertices = 8, //Orignal problem see left hand side 
     testSet[0].edges.push_back(edge(0, 1)); 
     testSet[0].edges.push_back(edge(1, 2)); 
     testSet[0].edges.push_back(edge(1, 3)); 
     testSet[0].edges.push_back(edge(2, 7)); 
     testSet[0].edges.push_back(edge(3, 4)); 
     testSet[0].edges.push_back(edge(4, 5)); 
     testSet[0].edges.push_back(edge(4, 6)); 
     testSet[0].edges.push_back(edge(5, 7)); 
     testSet[0].edges.push_back(edge(6, 4)); 

     testSet[1].numOfVertices = 8; //Used to create Dominator Tree 

    const int numOfVertices = testSet[0].numOfVertices; 

    G g(
     testSet[0].edges.begin(), testSet[0].edges.end(), 
     numOfVertices); 

    typedef graph_traits<G>::vertex_descriptor Vertex; 
    typedef property_map<G, vertex_index_t>::type IndexMap; 
    typedef 
     iterator_property_map<vector<Vertex>::iterator, IndexMap> 
     PredMap; 

    vector<Vertex> domTreePredVector, domTreePredVector2; 
    IndexMap indexMap(get(vertex_index, g)); 
    graph_traits<G>::vertex_iterator uItr, uEnd; 
    int j = 0; 
    for (tie(uItr, uEnd) = vertices(g); uItr != uEnd; ++uItr, ++j) 
    { 
     put(indexMap, *uItr, j); 
    } 
    write_graphviz(cout, g); 
    // Lengauer-Tarjan dominator tree algorithm 
    domTreePredVector = 
     vector<Vertex>(num_vertices(g), graph_traits<G>::null_vertex()); 
    PredMap domTreePredMap = 
     make_iterator_property_map(domTreePredVector.begin(), indexMap); 

    lengauer_tarjan_dominator_tree(g, vertex(0, g), domTreePredMap); 
vector<int> idom(num_vertices(g)); 
     for (tie(uItr, uEnd) = vertices(g); uItr != uEnd; ++uItr) 
     { 
      if (get(domTreePredMap, *uItr) != graph_traits<G>::null_vertex()) 
      idom[get(indexMap, *uItr)] = 
       get(indexMap, get(domTreePredMap, *uItr)); 
      else 
      idom[get(indexMap, *uItr)] = (numeric_limits<int>::max)(); 
     } 

     for (int k =0; k <idom.size();k++){ 

      if (k>0){ 
      cout << idom[k] << " nach " << k << endl; 
      int t= idom[k]; 
      testSet[1].edges.push_back(edge(t, k)); 
      } 
     } 

     G g2(testSet[1].edges.begin(), testSet[1].edges.end(),8); 
     int jj=0; 
     for (tie(uItr, uEnd) = vertices(g2); uItr != uEnd; ++uItr, ++jj) 
      { 
      put(indexMap, *uItr, jj); 
      } 

     write_graphviz(cout, g2); 
     cout << endl; 


return 0; 

}