Mario Román

topological sorting

1 min read

Naive Haskell implementation.

module TopologicalSort where
 
import qualified Data.Map.Strict as M
import qualified Data.Set as S
 
 
type Graph v = M.Map v (S.Set v)
 
topologicalSort :: (Ord v) => Graph v -> Maybe [v]
topologicalSort g
  | M.null g = Just []
  | S.null (orphanVertices g) = Nothing
  | otherwise = do
      orphans <- pure (S.toList (orphanVertices g))
      rest <- topologicalSort (filterOrphans g)
      return $ orphans ++ rest
 
orphanVertices :: (Ord v) => Graph v -> S.Set v
orphanVertices g = S.difference (M.keysSet g) (S.unions $ M.elems g)
 
filterOrphans :: (Ord v) => Graph v -> Graph v
filterOrphans g = M.filterWithKey (\v _ -> S.notMember v (orphanVertices g)) g
 
 
exampleGraph :: Graph String
exampleGraph = M.fromList
  [ ("a", S.fromList ["b"])
  , ("b", S.fromList ["c","d"])
  , ("c", S.fromList ["d","e"])
  , ("d", S.fromList [])
  ]

Graph View