Topological sort in Haskell

Question

I have a data type Graph which looks like this:

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

This is representing a directed acyclic graph. Where vertices have a char identifier ('a' for the first vertice added, 'b' for the second and so on) and a weight. Edges are two vertice identifiers and a weight.

I'm thinking about making the vertices a bit more complex, maybe they should contain a list of all neighbours?

The topological ordering looks like this so far:

topological_ordering :: Graph w -> [Char]
topological_ordering (Graph v w) =
    let startingNodes = getStartNodes (Graph v w)
        emptyList = []
        sorted = sortAlgorithm startingNodes emptyList (Graph v w)
    in sorted

sortAlgorithm :: [Char] -> [Char] -> Graph w -> [Char]
sortAlgorithm startingNodes sorted (Graph v w) =
    | [] _ _ = []
    | (x:startingNodes) sorted (Graph v w) =
      let sorted = sorted ++ [x]
          neigbours = findNeighbours (Graph v w) x

getStartNodes :: Graph w -> [Char]
getStartNodes (Graph v w) =
    let set1 = Set.fromList $ firstNodes w
        set2 = Set.fromList $ secondNodes w
        startNodes = Set.toList $ Set.difference set1 set2
    in  startNodes

firstNodes :: [(Char, Char, w)] -> [Char]
firstNodes [] = []
firstNodes (x:xs) = selectFirst x:firstNodes xs

secondNodes :: [(Char, Char, w)] -> [Char]
secondNodes [] = []
secondNodes (x:xs) = selectSecond x:secondNodes xs

From there I'm a little lost. I don't really know how to complete the sortAlgorithm, because I want it to be recursive (or use foldl/foldr?). Should implement the data type for Graph in another way or should I continue with this?

I just started haskell a few weeks ago and still feel a bit lost on functional programming.

Thanks

Answer 1

You might want to take a look at how elegantly it is done in Data.Graph. Here is an outline of the algorithm:

topSort      :: Graph -> [Vertex]
topSort       = reverse . postOrd

postOrd      :: Graph -> [Vertex]
postOrd       = postorderF . dff

postorder :: Tree a -> [a]
postorder (Node a ts) = postorderF ts ++ [a]

postorderF   :: Forest a -> [a]
postorderF ts = concat (map postorder ts)

-- | A spanning forest of the graph, obtained from a depth-first search of
-- the graph starting from each vertex in an unspecified order.
dff          :: Graph -> Forest Vertex
dff g         = dfs g (vertices g)

-- | A spanning forest of the part of the graph reachable from the listed
-- vertices, obtained from a depth-first search of the graph starting at
-- each of the listed vertices in order.
dfs          :: Graph -> [Vertex] -> Forest Vertex

That is, a topological sort of a graph is (the reverse of) a post-order traversal of a spanning forest of the graph.

Here is an example of how to use it:

  import qualified Data.Graph as G

  {-
     5 --> 7
     |     |
     v     V
     1 --> 4 --> 8
  -}

  (myGraph,vertexToNode,keyToVertex) = G.graphFromEdges [
      ("node4",4,[8]),     -- the first component can be of any type
      ("node8",8,[]),
      ("node7",7,[4]),
      ("node5",5,[1,7]),
      ("node1",1,[4])
   ]

  sorted = map vertexToNode $ G.topSort myGraph
  -- [("node5",5,[1,7]),("node7",7,[4]),("node1",1,[4]),("node4",4,[8]),("node8",8,[])]