Problem 88

Split a graph into its connected components.

Example

connected ([1,2,3,4,5,6,7], [(1,2),(2,3),(1,4),(3,4),(5,2),(5,4),(6,7)])
  == [[1,2,3,4,5][6,7]]

Unit Test

import Html
import List
import Set
import String


type alias Edge comparable =
    ( comparable, comparable )


type alias Graph comparable =
    ( List comparable, List (Edge comparable) )


{-| Given a graph, return connected subsets of nodes.
-}
connected : Graph comparable -> List (List comparable)
connected (nodes, edges) =
   []

main : Html.Html a
main =
    Html.text
        <| case test of
            0 ->
                "Your implementation passed all tests."

            1 ->
                "Your implementation failed one test."

            x ->
                "Your implementation failed " ++ (toString x) ++ " tests."


test : Int
test =
    List.length
        <| List.filter ((==) False)
            [ (List.sort (connected graph80)) 
                ==  [ ['b', 'c', 'f', 'k']
                    , ['d']
                    , ['g', 'h']
                    ]
            , (connected ([], [])) == []
            , (connected ([1, 2, 3], [])) == [[1], [2], [3]]
            , (connected ([1, 2, 3], [(1,2), (2,3)])) == [[1,2,3]]
            ]


graph80 =
    ( [ 'b', 'c', 'd', 'f', 'g', 'h', 'k' ]
    , [ ( 'b', 'c' )
      , ( 'b', 'f' )
      , ( 'c', 'f' )
      , ( 'f', 'k' )
      , ( 'g', 'h' )
      ]
    )

Hint

1. Which previous graph problem will extract one connected component?

Solution

Solution