使用 Boost 的 Lengauer Tarjan 算法计算支配图并使用 graphviz 显示它

Question

如果我违反了规则，首先让我道歉，因为我知道我的问题已经在这里以修改的方式提出：Lengauer Tarjan Algorithm in BGL (boost graph library)。但是，我（仍然）无法使用答案来正确显示结果。

更准确地说：我按照链接的答案成功地将 Lengauer-Tarjan 算法应用于我的图表（为方便起见，它是 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);`

对我来说，Boost 的主要优点之一是可以使用带有 write_graphviz(cout, g) 的 graphviz 自动生成图形输出，其中 g 是来自 typedef G:

的图形

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

但是，我无法将 DomTreePredMap 翻译成 write_graphviz(cout, X) 可以理解的内容。我感谢任何概述如何从 domTreePredMap 构建图形的帮助，它可以使用 graphviz 打印。

感谢大家阅读所有这些内容并帮助我。

Answer 1

抱歉打扰了 - 我自己在 boost 纪录片中找到了答案：

这是一个最小的工作示例来说明我的问题。基本上我想计算图（左边一个）及其支配树（右边），如下所示：http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/lengauer_tarjan_dominator.htm#fig:dominator-tree-example 并使用 graphviz.

打印两个图

按照示例，我设法计算并打印了原始图形，并在其上执行了 Lengauer-Tarjan 算法。支配树的信息存储在 DomPredMap 中，可以复制到一个整型向量中。在向量 idom 的位置 i 存储了节点 i 的父节点的 id。如果不存在父节点，则存储max_int。此信息可用于将 idom[i] 到 i 的边添加到最终可以构建图 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;

}

使用 Boost 的 Lengauer Tarjan 算法计算支配图并使用 graphviz 显示它

Computing a dominator graph using Boost's Lengauer Tarjan algorithm and display it using graphviz

c++

boost

graph-algorithm

graphviz

boost-graph