9

有向グラフのノードのデータ型を簡単に定義できます。

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

show 関数を使用してグラフをファイルに保存し、read を使用して復元できます。ただし、show はサイクルに対応しません。グラフを保存して復元する簡単な方法はありますか?

4

2 に答える 2

8

私が知る限りではありません。グラフ走査関数を作成する必要があります。

まず、どこで循環性を壊すかを決めます。この場合は簡単です: ノード名を使用します (グラフ内で一意であると仮定します)。ノードとエッジを別々のタイプとして持つグラフなど、より複雑な構造の場合、エッジをノードと共に格納するか、ノードをエッジと共に格納するか、またはノードとエッジを完全に分離したままにするかを決定する必要があります。

次に、グラフ内のすべてのノードを列挙します。この場合、明らかな方法は、有限マップ内のノードを収集するグラフをトラバースすることです ( Data.Mapを参照)。次に、各ノードを名前として保存し、その後に他のノード名のリストを続けます。

グラフを復元するということは、「結び目を結ぶ」パターンを使用することを意味します。格納されたグラフを [(String, [String])] の構造体に読み込みます。次に、元のグラフを次のコードで再構築できます。

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

相互再帰に注意してください。table が makeNode を呼び出し、それが findNode を呼び出し、それが table を呼び出します。 遅延評価のおかげで、これは Right Thing を実行します。

編集:コードがテストされ、わずかに拡張されました。

于 2008-12-28T07:02:47.030 に答える
2

はいといいえ。これは、Node タイプの構造に関するドメインの知識と、これまでに見たノードのリストまたはマップと組み合わせてテストできる等価性の概念を定義して、共有を回復することによって実行できます。病的なケースでは、そのような概念を構築するための GHC の StableName の概念があります。

別の面では、Matt Morrow が、彼の便利なバキューム ライブラリを使用して、任意の循環データをアセンブリ言語の .S ファイルの形式で抽出する作業を行っています。したがって、それまたは真空のいずれかがニーズに合う場合があります。

一般に、マップでこれまでに見られたブードゥーと追跡ノードを回避することは、おそらく最も合理的で保守可能なソリューションです。

于 2009-09-11T17:25:39.633 に答える