طريقة فعالة لحساب متكرر شجرة المسيطر؟

Question

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

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

وبسذاجة يبدو أنه يجب أن يكون من الممكن حيث سيكون هناك الكثير من العقد في أعماقي في الرسم البياني التي لديها idoms مجرد وسيلة قليلا فوقهم وتتأثر بالتغيرات في أعلى الرسم البياني.

وراجع للشغل مثلما جانبا: انها غريبة أن موضوع الأشجار المسيطر هو "مملوكة" من قبل الناس مترجم وليس هناك ذكر في كتب عن نظرية المخططات الكلاسيكية. تطبيق أنا استخدامه ل- بلدي FindRoots جافا كومة محلل - لا علاقة لالمترجم نظرية

وتوضيح: أنا أتحدث عن مخطط موجه هنا. "الجذر" أود أن أشير إلى هو في الواقع عقدة مع أعظم وسائل الأتصال. لقد تحديث النص أعلاه استبدال الإشارات إلى "شجرة" مع "الرسم البياني". أنا أميل إلى نفكر بها أشجار لأن الشكل هو <م> أساسا شجرة تشبه. الرسم البياني هو في الواقع من الكائنات في كومة جافا وكما يمكنك أن تتخيل الهرمية معقول. لقد وجدت شجرة المسيطر مفيدة عند القيام بتحليل تسرب OOM لأن ما كنت مهتما في غير "ما يبقي هذا الكائن على قيد الحياة؟" والجواب في نهاية المطاف هو المسيطر فيها. أشجار المسيطر تسمح لك <مهم> رؤية الغابة بدلا من الأشجار. لكن في بعض الأحيان الكثير من غير المرغوب فيه يطفو إلى أعلى الشجرة بحيث يكون لديك الجذر مع الآلاف من الأطفال تحتها مباشرة. لمثل هذه الحالات وأود أن تجربة مع حساب الأشجار المسيطر متجذرة في كل من الأطفال المباشر (في الرسم البياني الأصلي) من الجذر وربما بعد ذلك تذهب إلى المستوى التالي أسفل وهلم جرا. (أنا أحاول لا داعي للقلق حول إمكانية صلات في الوقت الحاضر:)

Answer 1

boost::lengauer_tarjan_dominator_tree_without_dfs .

Answer 2

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

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

وفكرتي الثانية هي أن النقطة الرئيسية لسؤالك يبدو أن تجنب إعادة حساب النتيجة لجذر الشجرة.

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

وآمل أن يساعد!

Answer 3

هل يمكنك توضيح أي نوع من الرسم البياني كنت بدأت مع؟ أنا لا أرى كيف يكون هناك أي فرق بين الرسم البياني وهي شجرة، والشجرة المسيطر من أن الرسم البياني. يجب أن تكون الأم كل عقدة idom لها، وستكون بالطبع أن تهيمن عليها كل شيء فوقه في شجرة.

Answer 4

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

يمكنك فقط البحث عن "التحديثات الإضافية شجرة المسيطر" للعثور على بعض المراجع.

واعتقد انك على علم rel="nofollow الذاكرة محلل الكسوف لا أشجار استخدام المسيطر، لذلك هذا الموضوع هو ليس تماما "مملوكة" من قبل المجتمع المترجم بعد الآن:)