Berechnen eines Dominator-Graphen mit Boosts Lengauer Tarjan-Algorithmus und Anzeige mit graphviz

Question

Lassen Sie mich zunächst entschuldigen, falls ich gegen die Regeln verstoßen habe, da ich weiß, dass meine Frage hier bereits in abgewandelter Form gestellt wurde: Lengauer Tarjan Algorithm in BGL (boost graph library). Allerdings kann ich die Antwort (noch) nicht verwenden, um das Ergebnis korrekt anzuzeigen.

Um genauer zu sein: Ich folgte der Antwort verknüpft und habe erfolgreich den Lengauer-Tarjan-Algorithmus auf meine Grafik angewendet (die zur Erleichterung ist Teil der Boost-Dokumentation: http://www.boost.org/doc/libs/1_55_0/libs/graph/test/dominator_tree_test.cpp). Nun verstehen, wenn der Code korrekt die relevanten Informationen über den Beherrscher Baum in domTreePredMap gespeichert, die vom Typ PredMap ist:

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);` 

Für mich einer der wichtigsten Vorteile von Boost ist die Möglichkeit, automatisch die grafische Ausgabe mit graphviz erzeugt mit write_graphviz (cout, g), wobei g eine grafische Darstellung von typedef g ist:

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

Allerdings kann ich die DomTreePredMap in etwas write_graphviz (cout, X) verstehen übersetzen. Ich schätze jede Hilfe, die beschreibt, wie ein Diagramm aus domTreePredMap erstellt werden kann, das mit graphviz gedruckt werden kann.

Vielen Dank, dass Sie all das gelesen haben und mir geholfen haben.

Answer 1

Entschuldigen Sie die Störung - ich es geschaffen, die Antwort selbst in dem Boost-Dokumentarfilm zu finden:

Hier ist ein minimales Arbeitsbeispiel, mein Problem zu veranschaulichen. Im Grunde möchte ich das Diagramm (eins links) und seinen Dominator-Baum (rechts) wie hier dargestellt berechnen: http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/lengauer_tarjan_dominator.htm#fig:dominator-tree-example und beide Graphen mit graphviz drucken.

Dem Beispiel folgend, habe ich es geschafft, das ursprüngliche Diagramm zu berechnen und zu drucken und die Lengauer-Tarjan-Algorithmen darauf auszuführen. Die Information über den Dominator-Baum wird in der DomPredMap gespeichert und kann in einen Integer-Vektor kopiert werden. An der Position i des Vektor-Idoms ist die ID des Elternteils des Knotens i gespeichert. Wenn kein Elternknoten existiert, wird max_int gespeichert. Diese Information kann verwendet werden, um die Kanten von idom [i] zu i zu dem testSet hinzuzufügen, aus dem der Graph g2 schließlich konstruiert werden kann. Danke für Ihre Hilfe und Geduld.

#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; 

}