Wie ein BGL gerichteten Graphen als ungerichtete man verwenden (für den Einsatz in Layout-Algorithmus)?

Question

Ich arbeite an einem gerichteten Graphen (eigentlich eine bidirektionale eins) mit Boost.Graph. Ich möchte die Layout-Algorithmen verwenden, die vorhanden sind (entweder Kamada-Kawai oder Fruchterman-Reingold), aber sie nur ungerichtete Graphen als Parameter übernehmen.

Was ist der einfachste Weg, um diese Layout-Algorithmen zu benutzen? Allgemein gesagt, was der richtige Weg ist, um einen Algorithmus zu locken zu denken, dass ein gerichteter Graph tatsächlich ungerichtet?

Danke, Benoît

Answer 1

Sind Sie sicher, dass Fruchterman-Algorithmus Reingold akzeptiert nur ungerichtete Graphen? Ich habe versucht, das kleine Beispiel aus der Boost-Dokumentation laufen einen bidirektionalen Graphen anstelle eines ungerichteten ein verwenden, und es kompiliert und lief ganz gut.

---

Um Ihre Frage zu beantworten, ich bin nicht sicher, ob es irgendwelche Einrichtungen in der BGL gebaut einen gerichteten Graphen zu einem ungerichteten ein konvertieren. Die einzige Lösung, die ich gefunden wird ein neues Diagramm Erstellen und Hinzufügen aller Kanten aus dem Original:

typedef adjacency_list<vecS, vecS, bidirectionalS> BidirectionalGraph;
typedef adjacency_list<setS, vecS, bidirectionalS> UndirectedGraph;
// UndirectedGraph uses a set to avoid parallel edges

BidirectionalGraph bdg;
// use bdg

// create an undirected graph with the edges of the first one
typedef graph_traits<BidirectionalGraph>::vertex_iterator vi_beg, vi_end;
tie(vbeg, vend) = vertices(bdg);

UndirectedGraph ug(std::distance(vbeg, vend));

typedef graph_traits<BidirectionalGraph>::edge_iterator ei, ei_end;

for (tie(ei, ei_end) = edges(bdg) ; ei != ei_end ; ++ei)
{
    add_edge(source(*ei,bdg), target(*ei,bdg), ug);
}

Aber ich denke, diese Lösung könnte einig Performance-Problem aufwerfen, wenn sie mit großen Graphen zu tun. Es kann ein besserer Weg, um Ihr Ziel zu erreichen, aber ich bin kein Experte in BGL, so dass alles, was ich dir geben kann: -)

---

Wie Benoît in einem Kommentar darauf, bieten die BGL eine Funktion copy_graph, die kopiert alle Ecken und Kanten eines Graphen in eine andere. Daher oben kann der Code dazu einkochen:

#include <boost/graph/copy.hpp>

Bidirectional bdg;
// use bdg

// create an undirected graph with the vertices and edges of the first one
UndirectedGraph g;
copy_graph(bdg, g);