حفظ الرسوم البيانية في هاسكل

Question

أنا يمكن بسهولة تحديد نوع البيانات عن عقدة من الرسم البياني الموجهة.

data Node = Node String [Node] derving (Show, Read)

لا يمكن حفظ الرسم إلى ملف باستخدام عرض وظيفة ، ثم استعادته باستخدام قراءة.ومع ذلك, سوف تظهر على التعامل مع دورة.هل هناك طريقة تافهة إلى حفظ واستعادة الرسم البياني?

Answer 1

لا بقدر ما أعرف.لديك لكتابة الرسم البياني تعبر وظيفة.

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

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

استرداد الرسم البياني يعني استخدام "ربط العقدة" نمط.قراءة تخزين الرسم البياني إلى هيكل [(سلسلة, [سلسلة])].ثم الأصلية الرسم البياني يمكن بناؤها مع التعليمات البرمجية التالية:

import qualified Data.Map as M

data Node = Node String [Node]

instance Show Node where
   show (Node name others) = "Node " ++ show name ++ 
         " " ++ show (map nodeName others)
      where nodeName (Node n _) = n

restoreGraph :: [(String, [String])] -> M.Map String Node
restoreGraph pairs = table
   where
      table = M.fromList $ map makeNode pairs
      makeNode (name, others) = (name, Node name $ map findNode others)
      findNode str = fromJust $ M.lookup str table

ملاحظة المتبادلة العودية:الجدول المكالمات makeNode الذي يدعو findNode الذي يدعو الجدول. بفضل كسول تقييم هذا يفعل الصواب.

تحرير: رمز الآن اختبار توسعت قليلا.

Answer 2

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

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

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