Implementing longest path algorithm in Haskell

Question

I would like some help implementing a longest path algorithm for Haskell. I've only used Haskell for about two weeks and haven't done anything in a functional language before. I am really lost when trying to implement algorithms in a functional language when you are limited to immutable data and recursion.

I've been trying to implement this algorithm: http://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/

My graph is constructed like this:

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

So I have weights on both vertices and edges, and the weights can be any datatype. Therefore I also need to take two functions, f and g, when computing the longest path. The longest path from vertex a to b will then be the sum of f(w) and g(w) for all weights in the path.

I have tried implementing this but I always find myself trying to code the "imperative" way, which gets really ugly really fast...

Please point me in the right direction.

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

As you can see it's a lot of messy code for such a simple algorithm and I'm sure its doable in a much cleaner way.

Answer 1

Here is an approach that employs a more "functional" way of thinking. It revolves around two functions:

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

longestPath returns the path as a list of edges of the longest path. pathCost returns the cost of a path.

The definition of longestPath goes something like this:

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 ]

(maximumBy comes from Data.List and comparing from Data.Ord)

N.B. The edges will be generated in reverse order.

There are a host of implementation details to figure out, and, in particular, you'll have to slightly modify this to handle the case when there is not a path from start to node (which can happen once you start deleting nodes), but this is the approach I would start with.