用haskell在列表和集合中創建一個有向無環圖

我想在haskell中創建一個DAG，但由於我是新手，對於整個函數式編程而言，我希望有一些方向。用haskell在列表和集合中創建一個有向無環圖

圖表需要與僅列表和集合來構建，並且以下功能必須實現：

V = add_vertex（G，W）

一個頂點與指定的權重w被加到DAG g及其唯一的頂點標識符v被返回。

的add_edge（G，A，B，W）

從與頂點標識符的頂點到頂點的標識符b中的頂點的邊被添加到DAG克與重量瓦特

什麼我目前做的是創造它看起來像這樣一種數據類型：

data Graph v w = Graph {vertices :: [(v, w)], 
edges :: [([(v, w)], [(v, w)], w)]} deriving Show

而且我想我需要某種形式的構造函數圖形的，它看起來像這樣：

create_graph :: (v,w) -> w -> Graph v w 
create_graph v w = Graph [v] [(v, v, w)]

我想要做的只是創建一個空圖，但現在我需要輸入一些起始值，如果我理解正確。我該如何解決這個問題？

的add_vertex功能如下：

add_vertex :: Graph v w -> (v, w) -> Graph v w 
add_vertex (Graph v w) x = Graph (v ++ [x]) w

但我真的不知道怎麼回事頂點標識，而不是整個圖表。我想我也應該指定標識符需要是一個字符，權重可以是浮點數或整數，我該怎麼做？

我也想有拓撲排序的功能和獲得最長路徑的權重。考慮到這一點，我應該以不同的方式定義圖的結構嗎？

感謝

來源

2014-01-27 hboy

1）你的圖形數據類型只存儲頂點，但你的「圖形構造函數」也試圖存儲邊緣。 2）你的add_vertex實現非常單一。你應該使用：而不是++。可能你應該從較簡單的練習開始。 – user3974391

是的，這是構造函數的問題。我只想做一個空的圖，不插入任何頂點或邊，是可行的嗎？將考慮從++更改爲：，謝謝指出。那麼這是我們第一次在學校獲得的優秀成績，我正在努力閱讀「儘可能地學習你一個哈斯克爾」。 – hboy

空圖只會是'emptyGraph = Graph [] []'。在你的數據類型中，我不明白爲什麼每條邊都有兩個頂點列表;並假設'w'是權重的類型參數，爲什麼頂點的權重在邊緣重複。 – kosmikus

什麼，我會做的是定義圖形像一棵樹

data Graph a = Graph [(a,[a])] -- Graph is a list of origins paired with edgeends 

createGraph ::Eq a => [(a,a)] -> Graph a 
createGraph = undefined 

empty :: Graph a 
empty = Graph [] 

insertVertex :: Eq a => a -> Graph a -> Graph a 
insertVertex = undefined -- insert if not already in the Graph (with empty edges) 

insertEdge :: Eq a => (a,a) -> Graph a -> Graph a 
insertEdge = undefined -- insert edge in list of origin 
--do not forget to add origin, end if they don't exist

實現這些和擔心BFS/topsort後來想想一個BFS的結果 - 你想要的是什麼結果呢？（topsort的結果應該是我猜的列表）。

來源

2014-01-27 15:39:10 epsilonhalbe

用haskell在列表和集合中創建一個有向無環圖

回答

相關問題