الرسوم البيانية

7. الرسوم البيانية

تُعدّ الرسوم البيانية بنية معطيات أساسية في علم الحاسوب. يتكوّن الرسم البياني من مجموعة من الرؤوس (vertices) تربطها الأضلاع (edges). وقد اعتدنا على تصوير الرسوم البيانية على النحو المبيّن في الشكل 7.1.

الشكل 7.1: مثال على رسم بياني.

رسميًّا، الرسم البياني هو مجموعة V من الرؤوس ومجموعة E من الأضلاع، وهي أزواج غير مرتّبة من الرؤوس. إذا كان {x,y}∈ E، نقول إن الرأسين x و y متجاوران. وبما أن علاقة التجاور متناظرة، فإننا نتحدث عن رسم بياني غير موجّه.

ويمكننا أيضًا تعريف مفهوم الرسم البياني الموجّه بأخذ E لتكون مجموعة من الأزواج المرتّبة من الرؤوس بدلًا من الأزواج غير المرتّبة. حينئذٍ نتحدث عن الأقواس (arcs) بدلًا من الأضلاع. إذا كان (x,y) ∈ E، نقول إن y خَلَفٌ لـ x ونكتب x → y. ويُعطى مثال على رسم بياني موجّه في الشكل 7.2.

الشكل 7.2: مثال على رسم بياني موجّه.

يُسمّى القوس الممتد من رأس إلى نفسه، كما في هذا المثال، حلقة (cycle). أما درجة الدخول (indegree) (وبالمثل درجة الخروج (outdegree)) لرأس فهي عدد الأقواس المتّجهة نحوه (وبالمثل المتّجهة بعيدًا عنه). والمسار (path) من رأس u إلى رأس v هو متتالية x0,…,xn من الرؤوس بحيث x0 = u و xn = v و xi → xi+1 من أجل 0 ≤ i < n. ويكون طول هذا المسار n؛ فهو يحتوي على n قوسًا.

وقد تحمل الرؤوس، شأنها شأن الأقواس، معلومات. حينئذٍ نتحدث عن رسم بياني موسوم (labeled graph). ويُعطى مثال على رسم بياني موجّه وموسوم في الشكل 7.3.

الشكل 7.3: مثال على رسم بياني موجّه وموسوم.

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

في ما يأتي، سنستخدم مصطلح ضلع لكلٍّ من الرسوم البيانية الموجّهة وغير الموجّهة.

العمليات الأساسية على الرسوم البيانية

قبل تعريف بنى المعطيات اللازمة لتمثيل الرسوم البيانية، لا بدّ من النظر في العمليات التي ينبغي أن توفّرها هذه البنى. ونفعل ذلك بمعزل عن أي تمثيل بعينه، بهدف بناء خوارزميات عامة. ويمكننا تمييز العمليات الأساسية الآتية:

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

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

7.1 مصفوفة التجاور

ننظر في هذا القسم في الحالة التي تُمثَّل فيها الرؤوس بأعداد صحيحة، وبشكل أدق بأعداد صحيحة متتالية 0,…,N − 1. بعبارة أخرى، لدينا V = {0,…,N − 1}.

يعطي البرنامج 67 (انظر الصفحة التالية) توقيعًا مصغّرًا لهذه الرسوم البيانية. والنوع t هو نوع الرسوم البيانية. وقد جُعل مجرّدًا عن قصد لأننا سنقدّم تنفيذين مختلفين لهذا التوقيع. وتأخذ دالة الإنشاء create القيمة N وسيطًا، وتعيدها دالة nb_vertex. والأهم هنا أننا نفترض أن الرسم البياني يحتوي منذ البداية على N من الرؤوس. وبناءً على ذلك، لا نوفّر عمليات لإضافة الرؤوس أو حذفها أو لاختبار انتمائها إلى الرسم البياني. أما في حالة الأضلاع، فلدينا بالفعل هذه العمليات، وهي add_edge، وremove_edge، وmem_edge. ولاحظ أن دالتي إضافة الأضلاع وحذفها تقابلان بنية أمرية. ولا يوفّر التوقيع سوى دالتي المرور على خلفاء رأس (iter_succ) وعلى جميع الأضلاع (iter_edge). ويمكن تحقيق المرور على جميع الرؤوس بسهولة بحلقة for من 0 إلى N − 1. وأخيرًا، لاحظ أن هذا التوقيع يصلح على حدٍّ سواء للرسوم البيانية الموجّهة وغير الموجّهة.

التوقيع مصغّر عن قصد. وعلى وجه الخصوص، فإن الرسوم البيانية غير موسومة. وتقترح بعض تمارين هذا القسم امتدادات.

التمثيل المباشر لمثل هذا الرسم البياني هو مصفوفة M بحجم N × N، حيث يشير كل عنصر Mi,j إلى وجود ضلع بين الرأسين i و j. وبما أن الرسوم البيانية مفترضة غير موسومة، فيكفي استخدام مصفوفة من القيم المنطقية:

  type vertex = int
  type t = bool array array

تعريف الدالة التي تنشئ رسمًا بيانيًا خاليًا من الأضلاع واضح: ننشئ مصفوفة مربّعة مهيّأة بالقيمة false.

  let create n = Array.make_matrix n n false
  let nb_vertex = Array.length

في ما يأتي، نفترض أن جميع الرسوم البيانية موجّهة. ويشير التمرين 7.4 إلى التعديلات اللازمة للرسوم البيانية غير الموجّهة. ويمكن إجراء إضافة ضلع أو حذفه أو اختبار وجوده كلها في زمن ثابت:

  let mem_edge g v1 v2 = g.(v1).(v2)
  let add_edge g v1 v2 = g.(v1).(v2) <- true
  let remove_edge g v1 v2 = g.(v1).(v2) <- false

لتطبيق دالة f:vertex->unit على جميع خلفاء رأس v في رسم بياني g، يكفي المرور على الصف g.(v) من المصفوفة، مثلًا باستخدام Array.iteri. ونختبر وجود الضلع قبل تطبيق الدالة f على الرأس المقابل.

  let iter_succ f g v =
    Array.iteri (fun w b -> if b then f w) g.(v)

لتطبيق دالة f:vertex->vertex->unit على جميع أضلاع رسم بياني g، نبدأ بالمرور على رؤوس g بحلقة for. ثم نمرّ، لكل رأس v، على أضلاعه الخارجة باستخدام iter_succ. وتُشتقّ الدالة المُمرَّرة إلى iter_succ بتطبيق جزئي للدالة f على v.

  let iter_edge f g =
    for v = 0 to nb_vertex g - 1 do iter_succ (f v) g v done

يُعطى الكود الكامل للرسوم البيانية عبر مصفوفات التجاور في البرنامج 68. ويمكن تكييف بنية مصفوفة التجاور مع حالة الرسوم البيانية الموسومة (انظر التمرين 7.3) و/أو الرسوم البيانية غير الموجّهة (انظر التمرين 7.4).

التعقيد

يلخّص الجدول في الشكل 7.4 تعقيد العمليات الرئيسية على مصفوفات التجاور. وبصفة عامة، يُعبَّر عن التكلفة بدلالة عدد الرؤوس N

وعدد الأضلاع E. أما في الحالة الخاصة لمصفوفات التجاور، فإن التكلفة تعتمد على N فحسب.

الشكل 7.4: تكلفة العمليات على مصفوفات التجاور.

بطبيعة الحال، نفترض أن الدوال المُمرَّرة كوسائط إلى iter_succ وiter_vertex وiter_edge ذات تكلفة ثابتة. ومن هذا الجدول نستنتج أن مصفوفات التجاور ملائمة جيدًا للرسوم البيانية الكثيفة (dense)، أي الرسوم البيانية التي يكون فيها عدد الأضلاع E من رتبة N2. وفي الواقع، تكون درجة خروج كل رأس حينئذٍ من رتبة N، بحيث تصبح iter_succ مثالية. وبالمثل، يتعيّن على iter_edge أن تمرّ على عدد من الأضلاع من رتبة N2، ومن ثمّ فهي أيضًا مثالية.

أما تكلفة الحيّز (space)، فمن الواضح أن مصفوفة التجاور تشغل حيزًا تربيعيًّا، أي (N + 1)2 كلمة في حالة مصفوفة منطقية (انظر القسم 3.2 نموذج التنفيذ). ويمكننا تقليل هذه التكلفة بمعامل ثابت باستخدام المتجهات البتية (bit vectors) (انظر القسم 4.2 المتجهات البتية). ويقترح التمرين 7.5 مثل هذا التحسين. ومن المهم ملاحظة أن هذا التحسين ممكن فقط إذا كانت الأضلاع غير موسومة.

7.2 قوائم التجاور

في حالة الرسوم البيانية المتخلخلة، يتمثّل بديل مصفوفات التجاور في استخدام مصفوفة (array) تحتوي على قائمة خلفاء كل رأس. ونحن نتحدث عن قوائم التجاور (adjacency lists). ويتبع نوع الرسوم البيانية هذا التعريف مباشرةً.

  type vertex = int
  type t = vertex list array

يُمثَّل الرسم البياني الفارغ بمصفوفة تحتوي على قوائم فارغة فقط.

  let create n = Array.make n []
  let nb_vertex = Array.length

لاختبار وجود ضلع بين الرأسين v1 وv2 في رسم بياني g، نمرّ على قائمة التجاور g.(v1) بحثًا عن v2. ونفعل ذلك هنا باستخدام الدالة List.mem.

  let mem_edge g v1 v2 =
    List.mem v2 g.(v1)

نضيف ضلعًا بين v1 وv2 بإضافة v2 إلى القائمة g.(v1). ولا نفعل ذلك إلا إذا لم يكن الضلع موجودًا من قبل، لتجنّب تكرارات غير ضرورية في قائمة التجاور.

  let add_edge g v1 v2 =
    if not (mem_edge g v1 v2) then g.(v1) <- v2 :: g.(v1)

نحذف الضلع v1 → v2 بحذف أي ظهور محتمل لـ v2 في القائمة g.(v1). ويمكننا فعل ذلك بسهولة باستخدام List.filter.

  let remove_edge g v1 v2 =
    g.(v1) <- List.filter ((<>) v2) g.(v1)

ومع ذلك، لاحظ أن استخدام List.filter هذا فيه عيبان: فمن جهة، لا يستفيد من غياب التكرارات في القائمة ليتوقف مبكرًا. ومن جهة أخرى، يعيد بناء القائمة g.(v1) بأكملها بلا داعٍ في الحالة التي لا يظهر فيها v2. ويقترح التمرين 7.8 علاجًا لهذه المسائل. وبالمثل، يمكن الاستفادة من كون الرؤوس أعدادًا صحيحة لتحسين العمليات الثلاث السابقة بالحفاظ على قوائم التجاور مرتّبة (انظر التمرين 7.9).

المرور على خلفاء رأس v في رسم بياني g أبسط مما هو عليه في حالة مصفوفات التجاور. ويُنفَّذ على نحو بديهي بتطبيق List.iter على قائمة التجاور g.(v).

  let iter_succ f g v = List.iter f g.(v)

أما كود iter_edge، في المقابل، فهو نفسه المستخدم لمصفوفات التجاور.

  let iter_edge f g =
    for v = 0 to nb_vertex g - 1 do iter_succ (f v) g v done

يُعطى الكود الكامل للرسوم البيانية عبر قوائم التجاور في البرنامج 69.

التعقيد

يلخّص الجدول في الشكل 7.5 تعقيد العمليات الرئيسية على قوائم التجاور. وهنا، يرمز δ إلى درجة خروج رأس.

الشكل 7.5: تكلفة العمليات على قوائم التجاور.

لاحظ أن العمليتين mem_edge وadd_edge لم تعودا، على خلاف ما هو عليه الحال في مصفوفات التجاور، من الرتبة O(1) بل من الرتبة O(δ). وفي المقابل، أصبح لكلٍّ من iter_succ وiter_edge تعقيد أمثل.

أما تكلفة الحيّز، فلقوائم التجاور تعقيد أمثل O(N + E). ولكي نكون دقيقين، فإن التكلفة هي N + 3E + 1 كلمة (انظر القسم 3.2 نموذج التنفيذ).

7.3 قواميس التجاور

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

من الناحية المثالية، نريد بنية رسم بياني لا تكون رؤوسها بالضرورة أعدادًا صحيحة ويمكن إضافتها أو حذفها ديناميكيًّا. كما تجمع البنية بين المزايا الخاصة لمصفوفات التجاور وقوائم التجاور في الزمن والحيّز. وهذه البنية موجودة: يكفي أن نجمع بنية قاموس مع بنية مجموعة. فالرسم البياني ليس في جوهره سوى قاموس يُقرَن فيه كل رأس بمجموعة خلفائه. بعبارة أخرى، نحتفظ بفكرة قوائم التجاور، لكن نستبدل المصفوفة بقاموس، والقوائم بمجموعات. وسنسمّي هذه البنية قاموس التجاور (adjacency dictionary). وبهذه الطريقة، لا تقتصر الرؤوس على الأعداد الصحيحة، ويمكن إضافتها وحذفها بسهولة. أما من حيث الفعالية، فيكفي استخدام جدول مُجزَّأ (hash table) للقاموس للحصول على تعقيد أمثل. ويمكننا أيضًا استخدام جدول مُجزَّأ لتمثيل مجموعة خلفاء رأس.

وبالتالي يمكننا أن نُوسِّط بنية قاموس التجاور لدينا بوحدة H من الجداول المُجزَّأة (مثل الوحدة المذكورة في القسم 5.3 الجداول المُجزَّأة أو الوحدة Hashtbl من المكتبة القياسية لـ OCaml).

  module Graph(H: HashTable) = struct

للتوضيح، نُدخل وحدة V للقاموس، كمرادف للوحدة H. ويكون نوع الرؤوس حينئذٍ هو نوع مفاتيح الوحدة V.

    module V = H
    type vertex = V.key

وبالمثل، نُدخل وحدة E لمجموعات الرؤوس المتجاورة، وهي أيضًا مرادف للوحدة H. والفكرة هنا هي تمثيل مجموعة من الرؤوس بجدول مُجزَّأ، وذلك بقرن كل عنصر من عناصر المجموعة بالقيمة ().

    module E = H

وبالتالي يكون نوع الرسوم البيانية كما يأتي:

    type t = (unit E.t) V.t

لو كانت الأضلاع موسومة، لكفى قرن كل خَلَف w للرأس v بوسم الضلع v → w بدلًا من القيمة () (انظر التمرين 7.10).

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

    let create () = V.create ()
    let nb_vertex g = V.length g

نتحقق من انتماء رأس v إلى الرسم البياني g باستخدام V.mem، أي باختبار كونه مفتاحًا في القاموس. ونضيف v بإنشاء ارتباط يقرن v بجدول مُجزَّأ جديد.

    let mem_vertex g v = V.mem g v
    let add_vertex g v = V.add g v (E.create ())

نلاحظ أن الدالة add_vertex تفترض أن v غير موجود بعد في الرسم البياني g. وإلا لتعيّن علينا أولًا التحقق من وجود v باستخدام mem_vertex. أما حذف رأس v فأكثر دقة: فلا يقتصر الأمر على وجوب حذف ارتباطه من القاموس، بل يلزم أيضًا حذف كل ظهور لـ v من مجموعات تجاور الرؤوس الأخرى (المكتوبة هنا بالرمز s).

    let remove_vertex g v =
      V.remove g v;
      V.iter (fun _ s -> E.remove s v) g

ولمزيد من الفعالية، ينبغي ألا نصل إلا إلى أسلاف v. ويقترح التمرين 7.14 تحسينًا من هذا القبيل.

لإضافة ضلع بين الرأسين v1 و v2 أو حذفه أو اختبار وجوده، نبدأ باسترجاع مجموعة تجاور v1 باستخدام V.findgv1. ثم نستخدم على التوالي الدوال E.replace وE.remove وE.mem.

    let mem_edge g v1 v2 = E.mem (V.find g v1) v2
    let add_edge g v1 v2 = E.replace (V.find g v1) v2 ()
    let remove_edge g v1 v2 = E.remove (V.find g v1) v2

تفترض هذه الدوال الثلاث أن v1 موجود بالفعل في الرسم البياني، أي أن V.findgv1 لا يفشل. أما الدالة add_edge، فنستخدم فيها E.replace بدلًا من E.add، لتجنّب التكرارات في مجموعة التجاور.

للمرور على مجموعة رؤوس رسم بياني g، يكفي المرور على مجموعة مفاتيح القاموس باستخدام V.iter. وبالمثل، نمرّ على خلفاء رأس v بالمرور على مجموعة تجاوره باستخدام E.iter.

    let iter_vertex f g = V.iter (fun v _ -> f v) g
    let iter_succ f g v = E.iter (fun w _ -> f w) (V.find g v)

وهنا أيضًا، نفترض أن iter_succ تُستدعى على رأس موجود v. وللمرور على جميع الأضلاع، يكفي تركيب iter_vertex وiter_succ كما فعلنا من أجل مصفوفات التجاور وقوائم التجاور. غير أن الوصول إلى مجموعة تجاور v باستخدام V.findgv سيكون مكلفًا بلا داعٍ. وبدلًا من ذلك، يكفي تركيب V.iter وE.iter مباشرةً.

    let iter_edge f g = V.iter (fun v s -> E.iter (f v) s) g

يُعطى الكود الكامل لبنية الرسم البياني هذه في البرنامج 70.

أما بالنسبة إلى الرسوم البيانية غير الموجّهة والرسوم البيانية الموسومة أو الرسوم البيانية ذات الأضلاع المتعددة بين رأسين، فيُحال القارئ إلى التمارين 7.10–7.12.

التعقيد

إذا افترضنا أن القواميس والمجموعات منفَّذة بجداول مُجزَّأة، نحصل على الأداء المعطى في جدول الشكل 7.6.

الشكل 7.6: تكلفة العمليات على قواميس التجاور.

نلاحظ أن التعقيدات أمثل، باستثناء حالة remove_vertex (انظر التمرين 7.14). أما تكلفة الحيّز، فلا بدّ من وضع افتراض بشأن أحجام الجداول المُجزَّأة. فإذا افترضنا أن عدد الجرافات (buckets) يساوي على الأقل ضعف عدد الارتباطات في كل جدول مُجزَّأ، فإن تكلفة الحيّز لجدول مُجزَّأ يحتوي على K مدخلة هي 6K + 4 كلمة. ومن ثمّ، بالنسبة إلى رسم بياني يحتوي على N رأسًا وE ضلعًا، تكون التكلفة الإجمالية:

وهذا يساوي 10N + 6E + 4 كلمة في المجموع.

الرسوم البيانية المستدامة

الرسوم البيانية المنفَّذة باستخدام قواميس التجاور كما عُرضت أعلاه أمرية بسبب الطبيعة الأمرية للجداول المُجزَّأة. ونحصل بطبيعة الحال على رسوم بيانية مستدامة باستبدال الجداول المُجزَّأة ببنية معطيات مستدامة. ويمكننا، على سبيل المثال، استخدام أي قاموس يمتلك التوقيع Map.S الخاص بـ OCaml (انظر التمرين 7.15)، ولا سيّما كل تلك التي نوقشت في الفصل 5.

7.4 مقارنة الأداء

نستعرض هنا بإيجاز أداء بنى الرسوم البيانية المختلفة. ويُلخَّص التعقيد الزمني للعمليات الرئيسية في جدول الشكل 7.7. وكما أشرنا سابقًا أعلاه، تقدّم قواميس التجاور أفضل تعقيد ممكن لكل عملية.

الشكل 7.7: مقارنة بين بنى معطيات مختلفة للرسوم البيانية.

أما تكلفة الحيّز، فتذكّر تكلفة كل بنية رسم بياني بعدد الكلمات:

• مصفوفة التجاور: 2 كلمة؛
• قوائم التجاور: N + 3E + 1 كلمة؛
• قاموس التجاور: 10N + 6E + 4 كلمة.

من الواضح أن قوائم التجاور أكثر اقتصاديًّا من حيث الذاكرة من قواميس التجاور. أما المقارنة مع مصفوفات التجاور فأصعب. فالواقع أنها تعتمد على كثافة الرسم البياني، أي النسبة بين عدد الرؤوس N وعدد الأضلاع E. فبالنسبة إلى رسم بياني كثيف جدًّا، يكون فيه E قريبًا من N2، تكون مصفوفة التجاور أكثر اقتصاديًّا. وفي حالة رسم بياني متخلخل، تكون فيه على سبيل المثال E ∼ N، تكون قوائم التجاور أكثر اقتصاديًّا. وبصفة عامة، تُفضَّل القوائم على المصفوفات عندما E < N2∕3، وبالمثل تُفضَّل القواميس على المصفوفات عندما E < N2∕6. والقوائم دائمًا أفضل من القواميس من حيث الحيّز.

بطبيعة الحال، عند اختيار بنية للرسوم البيانية، يجب الموازنة بين تعقيد العمليات المختلفة في الحيّز وتعقيدها في الزمن.

    val iter_pred: (vertex -> unit) -> t -> vertex -> unit