BGL中的Lengauer Tarjan算法(增强图库) [英] Lengauer Tarjan Algorithm in BGL (boost graph library)

问题描述

我需要为给定的图形创建一个控制树.我编写的代码可以正确运行并运行，但输出看起来与输入完全相同.

I need to create a dominator tree for a given graph. The code I have compiles and runs without errors, but the output looks exactly the same as the input.

我为图形定义了以下类型(待分析)

I have defined the following type for my graph (to be analyzed)

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

，我想让另一个对象包含相应的支配者树.我尝试了以下方法:

and I would like to have another object containing the corresponding dominator tree. I tried the following:

  // 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中的内容完全相同. IE.看起来上面最后一行的调用没有更改任何内容.输入图如下所示: http://s24.postimg.org/y17l17v5x/image.png

When I output the content of dominator_tree to a .dot file, it is exactly the same as in trace. I.e. it looks like the call of the last line above did not change anything. The input graph looks like this: http://s24.postimg.org/y17l17v5x/image.png

INIT节点是节点0.如果我选​​择其他任何节点作为该函数的第二个参数，它仍将返回相同的结果.

The INIT node is the node 0. If I choose any other node as the second argument of the function, it still returns an identical result.

我做错了什么?感谢任何帮助.

What am I doing wrong?? Apreciate any help.

推荐答案

看一下文档(

Taking a look at the documentation ( http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/lengauer_tarjan_dominator.htm ) I see that the first parameter is marked IN.

这意味着这仅是输入参数.因此，您不应期望它会被更改！

This means that this is an input parameter ONLY. So you should not expect it to be changed!

THIRD参数标记为OUT.因此，这是将在调用后更改的值.根据文档:

The THIRD parameter is marked OUT. So this is the value that will be changed following the call. According to the documentation:

OUT:DomTreePredMap domTreePredMap父级的控制树 是每个孩子的直接控制者.

OUT: DomTreePredMap domTreePredMap The dominator tree where parents are each children's immediate dominator.

因此，如果要更改图形，则必须自己做:删除所有现有的边，然后遍历树，按照树的指定将边添加到图形中.

So, if you want the graph to be changed, you will have to do it yourself: remove all existing edges and then iterate through the tree adding edges to the graph as specified by the tree.

这篇关于BGL中的Lengauer Tarjan算法(增强图库)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！