BGL: كيف أقوم بتخزين edge_descriptors و vertex_descriptors بكفاءة؟

Question

لذلك بعد حل مشكلة التبعية الدائرية مع BGL ، وصلت إلى عقبة أخرى.

أنا أستخدم حاليًا قائمة متاخمة لتصميم الرسم البياني الخاص بي. يتم تطبيق الخصائص المجمعة لكل من العقد والحواف لتخزين بعض المعلومات في الرسم البياني. لذلك لدي شيء مثل هذا:

class Node {
    int x, int y // position
};
class Edge {
    float length;
};

boost::adjacency_list<boost::listS, boost::listS, boost::directedS, Node, Edge>

تنشأ المشكلة عندما أرغب في تخزين اختصارات لعقد محددة وحواف في مكان آخر في الكود الخاص بي (على سبيل المثال بالنسبة لشارع يحتوي على عدة ممرات). كان النهج الأول هو حفظ Edge_Descriptors و Vertex_Descriptors حيث كنت بحاجة إليها. لكنني أتساءل عن حجم (من حيث البايتات) التي ستكون هذه الواصفات. ربما يكون هناك حل أفضل مثل تخزين جزء صغير من المعلومات للحصول على نفس النتائج.

هل يعرف أي شخص مقدار الذاكرة المستخدمة في ناقل من هذا النوع:

std::vector<edge_descriptor> ?

لقد فكرت بالفعل في تخزين المؤشرات إلى Edge_Descriptors ولكني لا أعرف ما إذا كان سيعمل وكيف يعمل.

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

تحرير: الآن بعد أن تم الإجابة على سؤالي الأول ، ما زلت أتساءل شيئًا واحدًا. أريد بناء نوع من الواجهة لفصل الرسم البياني الخاص بي. يجب أن تفصل هذه الواجهة تفاصيل فئة الرسم البياني من فئات أخرى يجب ألا تكون على دراية بتفاصيل الرسم البياني. وبالتالي ، يجب أن تتعرف الفئات الأخرى على العقد والحواف كأرقام. لذلك توصلت إلى فكرتين:

1. أنا استخدم hash_map std::tr1::unordered_map<int, edge_descriptor> لتكون قادرًا على ترجمة الأرقام إلى الواصفات التي يتم استخدامها مرة أخرى كمؤشرات إلى كائن الرسم البياني الخاص بي. قد تكون هذه خطوة واحدة إلى الكثير - ربما يستغرق حساب قيم التجزئة الكثير من الوقت إذا كان هناك ما يكفي من العقد والحواف التي يتم حسابها. لهذا السبب كان لدي فكرة ثانية.
2. يجب على الرسم البياني نفسه تحويل هذه الأرقام داخليًا إلى الحواف والعقد. أعلم أنه يمكن استخدام الخصائص الداخلية مع خرائط الممتلكات لتحقيق فكرتي. يمكنك بعد ذلك الوصول إلى عقدة بمجرد كتابة شيء مثل:
   boost::property_map<My_Graph, my_prop>::type index = get(my_prop(), G);

ولكن هل هناك طريقة للجمع بين خرائط الممتلكات هذه مع خصائقي المجمعة؟

أو هل لديك فكرة أخرى لم أصب بها ، حتى الآن؟

Answer 1

تأخذ واصفات Vertex و Edge حجمًا صغيرًا جدًا.

واصفات الرأس هي أرقام. واصفات الحافة هي بنية صغيرة تحتوي على مصدر وواصفات قمة الرأس المستهدفة ، ومؤشر إلى البيانات الداخلية المرفقة بوصاف الحافة.

لذلك فإن إجابة سؤالك هي أنه يمكنك استخدامها في المتجهات. لن تشكل مشكلة في الذاكرة.