Come utilizzare un grafico diretto BGL come uno non orientato (per l'uso in algoritmo di layout)?

Question

Sto lavorando su un grafo orientato (in realtà uno bidirezionale) con Boost.Graph. Mi piacerebbe usare gli algoritmi di layout che esistono (sia Kamada-Kawai o Fruchterman-Reingold), ma si accettano solo grafi non orientati come parametri.

Qual è il modo più semplice per utilizzare questi algoritmi di layout? Più in generale, qual è il modo giusto per attirare un algoritmo a pensare che un grafo orientato è in realtà non orientato?

Grazie, Benoît

Answer 1

Sei sicuro che Fruchterman-Reingold algoritmo accetta solo grafi non orientati? Ho provato a fare funzionare il piccolo esempio dalla documentazione Boost utilizzando un grafico bidirezionale invece di un unico undirected, e compilato e corse bene.

---

Per rispondere alla tua domanda, io non sono sicuro che ci sono delle strutture costruite in BGL per convertire un grafo orientato ad uno non orientato. L'unica soluzione che ho trovato è la creazione di un nuovo grafico e aggiungere tutti i bordi dall'originale:

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

Tuttavia, credo che questa soluzione potrebbe sollevare qualche problema di prestazioni quando si tratta di enormi grafici. Ci può essere un modo migliore per raggiungere il tuo obiettivo, ma io non sono un esperto in BGL, in modo che tutto quello che posso dare: -!)

---

Come Benoît sottolineato in un commento, il BGL fornire una funzione copy_graph che copia tutti i vertici e bordi di un grafico in un'altra. Pertanto, il codice di cui sopra può ridursi a questo:

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