كيفية استخدام الرسم البياني الموجه BGL كواحد غير مريض (للاستخدام في خوارزمية التخطيط)؟

Question

أنا أعمل على رسم بياني موجه (في الواقع واحد ثنائي الاتجاه) مع Boost.graph. أود استخدام خوارزميات التخطيط الموجودة (إما Kamada-Kawai أو Fruchterman-Reingold) لكنها تقبل فقط الرسوم البيانية غير المعردة كمعلمات.

ما هي أبسط طريقة لاستخدام خوارزميات التخطيط هذه؟ بشكل عام، ما هي الطريقة الصحيحة لإغراء خوارزمية في التفكير في أن الرسم البياني الموجه هو غير مجهز في الواقع؟

شكرا، benoît.

Answer 1

هل أنت متأكد من أن خوارزمية Fruchterman-Reingold يقبل فقط الرسوم البيانية غير المعردة؟ حاولت تشغيل المثال القليل من دعم الوثائق باستخدام رسم بياني ثنائي الاتجاه بدلا من واحد غير مريض، وتجميع وركض بشكل جيد.

---

للإجابة على سؤالك، لست متأكدا من أن هناك أي مرافق مدمجة في BGL لتحويل الرسم البياني الموجه إلى واحد غير مريض. الحل الوحيد الذي وجدته هو إنشاء رسم بياني جديد وإضافة جميع الحواف من المرء الأصلي:

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

ومع ذلك، أعتقد أن هذا الحل قد يثير بعض مشكلة الأداء عند التعامل مع الرسوم البيانية الضخمة. قد تكون هناك طريقة أفضل لتحقيق هدفك، لكنني لست خبيرا في BGL، لذلك كل هذا كل ما يمكنني تقديمه لك :-)!

---

كما أشار Benoît في تعليق، فإن BGL يوفر وظيفة copy_graph التي تنسخ جميع القمم وحواف الرسم البياني في واحد آخر. لذلك، يمكن أن يغلي التعليمات البرمجية أعلاه إلى هذا:

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