كيفية إجراء تسلسل هيكل الرسم البياني؟

Question

تمنحنا الملفات المسطحة وقواعد البيانات العلائقية آلية لتسلسل البيانات المنظمة.يعد XML رائعًا لإجراء تسلسل للبيانات الشبيهة بالشجرة غير المنظمة.

لكن العديد من المشاكل يتم تمثيلها بشكل أفضل من خلال الرسوم البيانية.على سبيل المثال، سيعمل برنامج المحاكاة الحرارية مع العقد الحرارية المتصلة ببعضها البعض من خلال حواف مقاومة.

إذن ما هي أفضل طريقة لتسلسل بنية الرسم البياني؟أعلم أن XML يمكنه، إلى حد ما، القيام بذلك --- بنفس الطريقة التي يمكن لقاعدة البيانات العلائقية إجراء تسلسل لشبكة معقدة من الكائنات:عادة ما يعمل ولكن يمكن أن يصبح قبيحًا بسهولة.

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

Answer 1

كيف تمثل الرسم البياني الخاص بك في الذاكرة؟
في الأساس لديك خياران (جيدان):

• تمثيل قائمة الجوار
• تمثيل مصفوفة الجوار

حيث يتم استخدام تمثيل القائمة المجاورة بشكل أفضل للرسم البياني المتناثر، وتمثيل المصفوفة للرسوم البيانية الكثيفة.

إذا استخدمت مثل هذه التمثيلات، فيمكنك إجراء تسلسل لهذه التمثيلات بدلاً من ذلك.

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

   1  2  3
1 #t #f #f
2 #f #f #t
3 #f #t #f

(هذا تمثيل غير محسّن وغير مرجح، ولكن يمكن استخدامه للرسوم البيانية الموجهة)

Answer 2

عادةً ما يتم عرض العلاقات في XML من خلال العلاقة بين الوالدين والطفل.يمكن لـ XML التعامل مع بيانات الرسم البياني ولكن ليس بهذه الطريقة.للتعامل مع الرسوم البيانية في XML يجب عليك استخدام ش س: معرف و XS:IDREF أنواع المخطط.

في أحد الأمثلة، افترض أن العقدة/@id هي نوع xs:ID وأن الرابط/@ref هو نوع xs:IDREF.يوضح ملف XML التالي دورة العقد الثلاث 1 -> 2 -> 3 -> 1.

<data>
  <node id="1"> 
    <link ref="2"/>
  </node>
  <node id="2">
    <link ref="3"/>
  </node>
  <node id="3">
    <link ref="1"/>
  </node>
</data>

العديد من أدوات التطوير تدعم ID وIDREF أيضًا.لقد استخدمت Java JAXB (Java XML Binding.وهو يدعم هذه من خلال @XmlID و ال @XmlIDREF التعليقات التوضيحية.يمكنك إنشاء الرسم البياني الخاص بك باستخدام كائنات Java العادية ثم استخدام JAXB للتعامل مع التسلسل الفعلي لـ XML.

Answer 3

XML مطول للغاية.عندما أفعل ذلك، أتدحرج بنفسي.وفيما يلي مثال على الرسم البياني الحلقي الموجه المكون من 3 عقد.إنه مضغوط جدًا ويفعل كل ما أحتاج إليه:

0: foo
1: bar
2: bat
----
0 1
0 2
1 2

Answer 4

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

serialize(x):
    done - a set of serialized objects
    if(serialized(x, done)) then return
    otherwise:
         record properties of x
         record x as serialized in done
         for each neighbour/child of x: serialize(child)

هناك طريقة أخرى بالطبع وهي قائمة العقد والحواف، والتي يمكن إجراؤها بتنسيق XML، أو بأي تنسيق تسلسل مفضل آخر، أو كمصفوفة مجاورة.

Answer 5

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

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

[[0.0, 0.0, 0.3, 0.1]
 [0.1, 0.0, 0.0, 0.0]
 [0.0, 0.0, 0.0, 0.0]
 [0.5, 0.2, 0.0, 0.3]]

يمكن تمثيلها على النحو التالي:

vals: [0.3, 0.1, 0.1, 0.5, 0.2, 0.3]
cols: [2,   3,   0,   0,   1,   4]
rows: [0,        2, null,  4]

يعد الصف المتناثر المضغوط بمثابة قائمة متجاورة بشكل فعال (تعمل مؤشرات الأعمدة بنفس الطريقة)، ولكن التنسيق يفسح المجال لعمليات المصفوفة بشكل أكثر نظافة.

Answer 6

ومن ناحية أقل أكاديمية وأكثر عملية، في CubicTest نحن نستخدم اكس ستريم (Java) لتسلسل الاختبارات من وإلى XML.يتعامل Xstream مع علاقات الكائنات ذات البنية الرسومية، لذا قد تتعلم شيئًا أو اثنين من النظر إلى مصدره وملف XML الناتج.أنت على حق بشأن قبيح بالرغم من ذلك، فإن ملفات xml التي تم إنشاؤها لا تبدو جميلة.