Lengauer Tarjan Algorithm en BGL (biblioteca de gráficos de impulso)

Necesito crear un árbol dominador para un gráfico dado. El código que tengo se comstack y se ejecuta sin errores, pero la salida tiene exactamente el mismo aspecto que la entrada.

He definido el siguiente tipo para mi gráfica (para ser analizada)

typedef boost::adjacency_list Graph; 

y me gustaría tener otro objeto que contenga el árbol de dominador correspondiente. Intenté lo siguiente:

  // dominator tree is an empty Graph object dominator_tree = trace; typedef typename boost::graph_traits::vertex_descriptor Vertex; typedef typename boost::property_map::type IndexMap; typedef typename boost::iterator_property_map<typename std::vector::iterator, IndexMap> PredMap; IndexMap indexMap(get(boost::vertex_index, dominator_tree)); std::vector domTreePredVector = std::vector( num_vertices(dominator_tree), boost::graph_traits::null_vertex()); PredMap domTreePredMap = make_iterator_property_map( domTreePredVector.begin(), indexMap); lengauer_tarjan_dominator_tree(dominator_tree, vertex(0, dominator_tree), domTreePredMap); 

Cuando envío el contenido de dominator_tree a un archivo .dot, es exactamente el mismo que en el rastreo. Es decir, parece que la llamada de la última línea de arriba no cambió nada. El gráfico de entrada se ve así: http://s24.postimg.org/y17l17v5x/image.png

El nodo INIT es el nodo 0. Si elijo cualquier otro nodo como el segundo argumento de la función, aún devolverá un resultado idéntico.

¿¿Qué estoy haciendo mal?? Apreciate cualquier ayuda.

Mirando la documentación ( http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/lengauer_tarjan_dominator.htm ) veo que el primer parámetro está marcado como IN.

Esto significa que este es un parámetro de entrada SOLAMENTE. ¡Así que no debes esperar que se cambie!

El parámetro TERCERO está marcado como OUT. Este es el valor que se cambiará después de la llamada. Según la documentación:

OUT: DomTreePredMap domTreePredMap El árbol dominador donde los padres son dominadores inmediatos de cada niño.

Por lo tanto, si desea que se cambie el gráfico, deberá hacerlo usted mismo: elimine todos los bordes existentes y luego itere a través del árbol agregando bordes al gráfico según lo especifique el árbol.