elm

topologySort.elm

module TopologySort (..) where

import Html exposing (..)


type alias Topology =
  List ( String, List String )


initialTopology : Topology
initialTopology =
  [ ( "a", [ "b", "c", "d" ] )
  , ( "b", [] )
  , ( "d", [ "c" ] )
  , ( "c", [ "b" ] )
  ]


invalidTopology : Topology
invalidTopology =
  [ ( "a", [ "b" ] )
  , ( "b", [ "a" ] )
  ]


removeDependencyFromTopology : String -> Topology -> Topology
removeDependencyFromTopology depToRemove topology =
  let
    removeDepFromDependencies =
      List.filter (\dep -> dep /= depToRemove)

    removeDepFromTuple ( name, dependencies ) =
      ( name, removeDepFromDependencies dependencies )
  in
    List.map removeDepFromTuple topology


findTopologyHead : Topology -> Maybe ( String, Topology )
findTopologyHead topology =
  let
    consBlank blank ( name, topology ) =
      ( name, blank :: topology )
  in
    case topology of
      [] ->
        Maybe.Nothing

      ( name, [] ) :: rest ->
        Maybe.Just ( name, rest )

      blank :: rest ->
        Maybe.map (consBlank blank) (findTopologyHead rest)


topoSort : Topology -> List String
topoSort topology =
  case findTopologyHead topology of
    Just ( name, topology ) ->
      name :: topoSort (removeDependencyFromTopology name topology)

    Nothing ->
      []


main : Html.Html
main =
  div
    []
    [ text "Valid Topology: "
    , initialTopology
        |> topoSort
        |> toString
        |> text
    , br [] []
    , text "Invalid Topology: "
    , invalidTopology
        |> topoSort
        |> toString
        |> text
    ]