Lưu biểu đồ trong Haskell

Question

Tôi có thể dễ dàng xác định một kiểu dữ liệu cho một nút của biểu đồ được chỉ dẫn.

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

Tôi có thể lưu biểu đồ vào tệp bằng chức năng hiển thị, sau đó khôi phục tệp bằng cách đọc. Tuy nhiên, chương trình sẽ không đối phó với một chu kỳ. Có cách nào nhỏ nhặt để lưu và khôi phục biểu đồ không?

Answer 1

Không xa như tôi biết. Bạn phải viết một hàm truyền tải đồ thị.

Trước tiên, hãy quyết định nơi để phá vỡ vòng tròn. Trong trường hợp này nó là tầm thường: sử dụng các tên nút (giả sử chúng là duy nhất trong một biểu đồ). Đối với một cấu trúc phức tạp hơn, chẳng hạn như một biểu đồ có các nút và các cạnh riêng biệt, bạn sẽ phải quyết định có lưu trữ các cạnh với các nút, các nút có cạnh hay giữ các nút và các cạnh hoàn toàn riêng biệt hay không.

Sau đó liệt kê tất cả các nút trong biểu đồ. Trong trường hợp này, cách rõ ràng là duyệt qua các biểu đồ thu thập các nút trong một bản đồ hữu hạn (xem Data.Map). Sau đó lưu trữ mỗi nút dưới dạng tên theo sau là danh sách các tên nút khác.

Khôi phục biểu đồ có nghĩa là sử dụng mẫu "buộc nút". Đọc biểu đồ được lưu trữ thành một cấu trúc của [(String, [String])]. Sau đó, đồ thị ban đầu có thể được xây dựng lại với mã sau:

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 

Lưu ý đệ quy lẫn nhau: gọi bảng makeNode, gọi hàm findNode, gọi bảng. Thanks to lazy evaluation this does the Right Thing.

Chỉnh sửa: mã hiện đã được kiểm tra và mở rộng một chút.

Answer 2

Có và không. Nó có thể được thực hiện thông qua kiến ​​thức miền về cấu trúc của loại nút của bạn và xác định một số khái niệm bình đẳng mà bạn có thể kiểm tra, kết hợp với một danh sách hoặc bản đồ các nút được thấy cho đến nay để phục hồi chia sẻ. Trong trường hợp bệnh lý, có một khái niệm về một StableName trong GHC để xây dựng một khái niệm như vậy.

Mặt khác, Matt Morrow đã thực hiện một số công việc để trích xuất dưới dạng ngôn ngữ lắp ráp .S tệp, dữ liệu tuần hoàn tùy ý sử dụng thư viện chân không tiện dụng của mình. Vì vậy, một trong hai điều đó hoặc chân không có thể phù hợp với nhu cầu của bạn.

Nói chung tránh các voodoo và các nút theo dõi được thấy cho đến nay trong một bản đồ có lẽ là giải pháp hợp lý và duy trì nhất.