在Haskell中實現最長路徑算法

Question

我想爲Haskell實現一個最長路徑算法。我只使用了Haskell大約兩週的時間，並且之前沒有在功能語言中做過任何事情。如果您僅限於不可變數據和遞歸，嘗試在函數式語言中實現算法時，我確實迷失了方向。

我一直在努力實現這個算法：http://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/

My圖表構造是這樣的：

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

所以我有兩個頂點和邊權重，權重可以是任何數據類型。因此，在計算最長路徑時，我還需要執行兩個函數，即f和g。然後，從頂點a到b的最長路徑將是路徑中所有權重的f(w)和g(w)之和。

我已經嘗試實現這個，但我總是發現自己試圖代碼的「勢在必行」的方式，它變得非常醜陋真快......

請點我在正確的方向。

weight_of_longest_path :: (Ord w) => Graph w -> Char -> Char 
              -> (w -> w) -> (w -> w) -> w 
weight_of_longest_path (Graph v w) startVert endVert f g = 
    let 
    topSort = dropWhile (/= startVert) $ topological_ordering (Graph v w) 
    distList = zip topSort $ 
       (snd $ head $ filter (\(a,b) -> a == startVert) v) 
       : (repeat (-999999999)) 
    finalList = getFinalList (Graph v w) topSort distList f g 
    in 
    snd $ head $ filter (\(a,b) -> b == endVert) finalList 

getFinalList :: (Ord w) => Graph w -> [Char] -> [(Char, w)] 
            -> (w -> w) -> (w -> w) -> [(Char, w)] 
getFinalList _ [] finalList _ _ = finalList 
getFinalList (Graph v w) (firstVert:rest) distList f g = 
    let 
    neighbours = secondNodes $ filter (\(a,b,w) -> a == firstVert) w 
    finalList = updateList firstVert neighbours distList (Graph v w) f g 
    in 
    getFinalList (Graph v w) rest finalList f g 

updateList :: (Ord w) => Char -> [Char] -> [(Char, w)] -> Graph w 
           -> (w -> w) -> (w -> w) -> [(Char, w)] 
updateList _ [] updatedList _ _ _ = updatedList 
updateList firstVert (neighbour:rest) distList (Graph vertices weights) f g = 
    let 
    edgeWeight = selectThird $ head 
      $ filter (\(a,b,w) -> a == firstVert && b == neighbour) weights 
    verticeWeight = snd $ head 
      $ filter (\(a,b) -> a == neighbour) vertices 
    newDist = calcDist firstVert neighbour verticeWeight edgeWeight 
         distList f g 
    updatedList = replace distList neighbour newDist 
    in 
    updateList firstVert rest updatedList (Graph vertices weights) f g 


calcDist :: (Ord w) => Char -> Char -> w -> w -> [(Char, w)] 
          -> (w -> w) -> (w -> w) -> w 
calcDist firstVert neighbour verticeWeight edgeWeight distList f g = 
    if (compareTo f g 
     (snd $ head $ filter (\(a,b) -> a == neighbour) distList) 
     (snd $ head $ filter (\(a,b) -> a == firstVert) distList) 
     edgeWeight verticeWeight) == True 
    then 
    (f (snd $ head $ filter (\(a,b) -> a == firstVert) distList)) 
    + (g edgeWeight) + (f verticeWeight) 
    else 
    (f (snd $ head $ filter (\(a,b) -> a == neighbour) distList)) 

replace :: [(Char, w)] -> Char -> w -> [(Char, w)] 
replace distList vertice value = 
    map (\p@(f, _) -> if f == vertice then (vertice, value) else p) 
     distList 

正如你可以看到它是這樣一個簡單的算法很多亂七八糟的代碼，我敢肯定，它在一個更清潔的方式是可行的。

Answer 1

這是一種採用更「功能性」思維方式的方法。它圍繞着兩個功能：

longestPath :: Graph -> Node -> Node -> [Edge] 
pathCost :: Graph -> [Edges] -> Int 

longestPath返回路徑的最長路徑的邊緣的列表。 pathCost返回路徑的成本。

的longestPath的定義是這樣的：（從Data.OrdmaximumBy來自Data.List和comparing）

longestPath g start end 
    | start == end = [] 
    | otherwise = 
    maximumBy (comparing (pathCost g)) 
       [ e : path | e <- edges of the node start 
          let start' = the other vertex of e, 
          let g' = graph g with node start deleted, 
          let path = longestPath g' start' end ] 

注：邊緣將以相反的順序生成。

有大量的實現細節需要弄清楚，特別是，如果沒有從start到node（當開始刪除時可能會發生這種情況，您將不得不稍微修改以處理這種情況節點），但這是我開始的方法。