Сохранение графиков в Haskell - PullRequest
Новая
       47

Сохранение графиков в Haskell

9 голосов
/ 28 декабря 2008

Я легко могу определить тип данных для узла ориентированного графа. 

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

Я могу сохранить график в файл, используя функцию show, а затем восстановить его, используя read. Однако шоу не справится с циклом. Есть ли тривиальный способ сохранить и восстановить график?

Ответы [ 2 ]

8 голосов
/ 28 декабря 2008

Не так, как я знаю. Вы должны написать функцию обхода графа.

Сначала решите, где разорвать круглость. В этом случае это тривиально: используйте имена узлов (предполагая, что они уникальны в графе). Для более сложной структуры, такой как граф с узлами и ребрами в качестве отдельных типов, вам нужно будет решить, сохранять ли ребра с узлами, узлы с ребрами или хранить узлы и ребра полностью отдельно.

Затем перечислите все узлы на графике. В этом случае очевидным способом является обход узлов, собирающих граф, в конечной карте (см. 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

Обратите внимание на взаимную рекурсию: таблица вызывает makeNode, который вызывает findNode, который вызывает таблицу. Благодаря ленивым оценкам это правильно делает .

Редактировать: код теперь протестирован и немного расширен.

2 голосов
/ 11 сентября 2009

Да и нет. Это можно сделать с помощью знания предметной области о структуре типа вашего узла и определения некоторого понятия равенства, которое вы можете проверить, в сочетании со списком или картой узлов, которые вы видели до сих пор для восстановления совместного использования. В патологическом случае в GHC существует понятие StableName для построения такого понятия.

С другой стороны, Мэтт Морроу проделал некоторую работу по извлечению в виде файла .S файла ассемблера произвольных циклических данных с помощью своей удобной вакуумной библиотеки. Так что либо это, либо вакуум могут удовлетворить ваши потребности.

В целом, избегание узлов вуду и слежения за узлами, которые до сих пор встречались на карте, является, вероятно, наиболее рациональным и поддерживаемым решением.

...