c++ - دورات في برنامج شجرة العائلة




graph cycle assertions family-tree (16)

أعتقد أن لديك بعض القيمة التي تحدد بشكل فريد الشخص الذي يمكنك بناء الشيكات عليه.

هذا هو واحد خادع. على افتراض أنك تريد الحفاظ على الهيكل شجرة ، أقترح هذا:

افترض هذا: A لديه أطفال مع ابنته الخاصة.

يضيف نفسه إلى البرنامج باعتباره A و B مرة واحدة في دور الأب ، دعونا نسميها صديقها.

إضافة is_same_for_out() التي تخبر المخرج الذي يولّد جزءًا من برنامجك أن جميع الروابط التي تذهب إلى B داخليًا يجب أن تنتقل إلى A عند عرض البيانات.

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

بناء على ذلك ، يمكنك العمل على التزامن رمز A و B لتجنب التناقضات.

هذا الحل بالتأكيد ليس مثالياً ، لكنه نهج أولي.

أنا المطور لبعض برامج شجرة العائلة (مكتوبة في C ++ وكيو تي). لم يكن لدي أي مشاكل حتى أرسل لي أحد زبائني تقريرًا عن الأخطاء. المشكلة هي أن العميل لديه طفلين مع ابنتهما ، ونتيجة لذلك ، لا يمكنه استخدام برنامجي بسبب الأخطاء.

هذه الأخطاء هي نتيجة لتأكيداتي ومحاولاتي المختلفة حول الرسم البياني للعائلة التي يتم معالجتها (على سبيل المثال ، بعد السير في دورة ، ينص البرنامج على أن X لا يمكن أن يكون الأب أو الجد من Y).

كيف يمكنني حل هذه الأخطاء دون إزالة جميع تأكيدات البيانات؟


أهم شيء هو avoid creating a problem ، لذلك أعتقد أنه يجب عليك استخدام علاقة مباشرة لتجنب وجود دورة.

كما قالmarkmywords ، # تشمل "fritzl.h".

أخيرا يجب أن أقول recheck your data structure . ربما يحدث خطأ ما هناك (ربما تكون قائمة مرتبطة ثنائية الاتجاه تحل مشكلتك).


استرخاء تأكيداتك.

ليس عن طريق تغيير القواعد ، والتي من المرجح أن تكون مفيدة جدًا ل 99.9٪ من عملائك في اكتشاف الأخطاء في إدخال بياناتهم.

بدلاً من ذلك ، يمكنك تغييره من خطأ "لا يمكن إضافة علاقة" إلى تحذير مع "إضافة على أي حال".


يجب أن تكون قد أعددت عائلة Atreides (إما الحديث أو Atreides أو القديم Oedipus Rex ) كحالة اختبار. لا يمكنك العثور على أخطاء باستخدام البيانات المطهرة كحالة اختبار.


آخر جواب وهمية وهمية لسؤال سخيف:

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

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

على سبيل المثال: http://en.wikipedia.org/wiki/Cousin_marriage

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

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


يبدو أنك (و / أو شركتك) لديها سوء فهم أساسي لما يفترض أن تكون شجرة العائلة.

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

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

لدى GEDCOM العديد من القضايا ، مثل عدم التوافق مع العلاقات الجنسية نفسها ، وسفاح المحارم ، الخ ... أي في الحياة الحقيقية يحدث في كثير من الأحيان أكثر مما تتخيل (خاصة عندما تعود في وقت ما إلى 1700-1800).

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

يعطينا عدم التحقق من الصحة مزيدًا من "الحل الواقعي" ، والحل الأبسط والأكثر مرونة.

أما بالنسبة لهذه الحالة المحددة ، فإنني أقترح إزالة التأكيدات لأنها لا تصمد عالميا.

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


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

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

على سبيل المثال ، إذا نظرت إلى أسلاف 2 ^ n التي لديك في جيل n ، إذا لم يكن هناك تداخل ، عندئذ سيكون لديك أسلاف أكثر في 1000 بعد الميلاد من وجود أشخاص أحياء. لذا ، يجب أن يكون هناك تداخل.

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

يمكن العثور على دورات حقيقية في شجرة في بعض الطرق. والطريقة الخاطئة هي وضع علامة على كل سلف من فرد معين ، وعند المرور ، إذا تم وضع علامة على الشخص الذي ستنتقل إليه بعد ذلك ، فقم بقص الارتباط. سيؤدي ذلك إلى قطع العلاقات المحتملة بدقة. الطريقة الصحيحة للقيام بذلك هي البدء من كل فرد ، وتمييز كل سلف بمسار ذلك الشخص. إذا كان المسار الجديد يحتوي على المسار الحالي كمسرح ثانوي ، فستكون هناك دورة ، ويجب كسرها. يمكنك تخزين المسارات كمتجه <bool> (MFMF، MFFFMF، إلخ) مما يجعل المقارنة والتخزين سريعان للغاية.

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

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


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

بقدر ما أعرف ، حتى المسيحيين يقبلون الزواج (وبالتالي الأطفال) بين أبناء عمومة ، والتي سوف تحول شجرة العائلة إلى DAG الأسرة.

المعنوي من القصة هو: اختيار هياكل البيانات الصحيحة.


تكرار الأب (أو استخدام الارتباط / مرجع).

على سبيل المثال ، إذا كنت تستخدم قاعدة بيانات ذات تسلسل هرمي:

$ #each person node has two nodes representing its parents.
$ mkdir Family
$ mkdir Family/Son
$ mkdir Family/Son/Daughter
$ mkdir Family/Son/Father
$ mkdir Family/Son/Daughter/Father
$ ln -s Family/Son/Daughter/Father Family/Son/Father
$ mkdir Family/Son/Daughter/Wife
$ tree Family
Family
└── Son
    ├── Daughter
    │   ├── Father
    │   └── Wife
    └── Father -> Family/Son/Daughter/Father

4 directories, 1 file

تأكيدات لا تنجو من الواقع

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

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

فيما يتعلق "بالأشجار" العائلية (في الواقع أنها رسوم بيانية كاملة ، بما في ذلك الدورات) ، هناك حكاية لطيفة:

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

تصبح الأمور أكثر غرابة ، عندما تأخذ surrogates أو "الأبوة غير الواضحة" بعين الاعتبار.

كيف تتعامل مع ذلك

حدد الدورات على أنها خارج النطاق

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

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

اسمح بالعلاقات اليدوية

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

يمكن للمستخدم بعد ذلك التعامل مع الحالات النادرة باليد. سيظل نموذج البيانات الخاص بك بسيطًا جدًا وستظل تأكيداتك على قيد الحياة.

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

اجعل نموذج البيانات الخاص بك أكثر مرونة ، وتخطي التأكيدات ، واختبار الثوابت

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

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

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

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

  • يظل عمه عمًا ، حتى عندما تضيف المزيد من "العلاقات الرومانسية"
  • كل طفل لديه أحد الوالدين
  • السكان الذين لديهم جيلين لديه واحد على الأقل

أو يمكن أن تكون تقنية:

  • لن ينهار برنامجك على رسم بياني يصل إلى 10 مليار عضو (بغض النظر عن عدد الترابطات)
  • مقياس البرامج الخاص بك مع O (رقم العقد) و O (عدد الحواف ^ 2)
  • يمكن لبرنامجك حفظ وإعادة تحميل كل رسم بياني عائلي يصل إلى 10 مليار عضو

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


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


يجب التركيز على ما يجعل القيمة الحقيقية لبرامجك . هل الوقت المستغرق في جعله يعمل لمستهلك واحد يستحق سعر الترخيص؟ من المحتمل لا.

أنصحك بالاعتذار لهذا العميل ، وأخبره أن وضعه خارج نطاق برنامجك ويصدر له استردادًا.


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

وأود أن تخزين البيانات في ناقلات مع عدد صحيح دائم لكل شخص وتخزين الآباء والأمهات والأطفال في الأجسام شخص حيث قال int هو مؤشر المتجه. سيكون هذا سريعًا جدًا في الانتقال بين الأجيال (ولكنه بطيء لأشياء مثل عمليات البحث عن الأسماء). تكون الكائنات حسب ترتيب وقت إنشائها.


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

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


يجب أن تستخدم شجرة عائلتك علاقات موجهة. بهذه الطريقة لن يكون لديك دورة.


يتطلب تمرير مؤشر إلى base_all<U...> مجرد وجود تعريف base_all<U...> . بدون محاولة الوصول إلى التعريف ، لن يكتشف المحول البرمجي أن النوع غير محدد بالفعل. يتمثل أحد الأساليب للتخفيف من هذه المشكلة في استخدام وسيطة تتطلب تعريفًا لـ base_all<U...> ، على سبيل المثال:

template< class ...T> struct base_all
   : id<T> ...
{
    typedef int type;
};
// ...
template< class ... U>
static constexpr bool test(typename base_all<U...>::type) noexcept
{
    return true;
}

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

#include <type_traits>

template <typename...>
struct is_one_of;

template <typename F>
struct is_one_of<F>
{
    static constexpr bool value = false;
};

template <typename F, typename S, typename... T>
struct is_one_of<F, S, T...>
{
    static constexpr bool value = std::is_same<F, S>::value
        || is_one_of<F, T...>::value;
};

template <typename...>
struct is_unique;

template <>
struct is_unique<> {
    static constexpr bool value = true;
};

template<typename F, typename... T>
struct is_unique<F, T...>
{
    static constexpr bool value = is_unique<T...>::value
        && !is_one_of<F, T...>::value;
};

int main()
{
    constexpr bool b = is_unique<int, float, double>::value;
    constexpr bool c = is_unique< int, char, int>::value;
    static_assert( b == true && c == false , "!");
}




c++ graph cycle assertions family-tree