Problem 86a

Set the degree of a every node in a graph. The degree of a node is the number of edges touching that node. A loop, an edge where both ends are the same node, counts as two.

We will use the degree to color a graph with the minimum number of colors. We now define a node type to have a value, degree and color.

Example

{-| A node has a value, degree and a color 
-}
type alias Node comparable =
    ( comparable, Int, Int )


g80 =
    ( [ ( 'b', 0, 0 )
      , ( 'c', 0, 0 )
      , ( 'd', 0, 0 )
      , ( 'f', 0, 0 )
      , ( 'g', 0, 0 )
      , ( 'h', 0, 0 )
      , ( 'k', 0, 0 )
      ]
    , [ ( 'b', 'c', 5 )
      , ( 'b', 'f', 8 )
      , ( 'c', 'f', 9 )
      , ( 'f', 'k', 17 )
      , ( 'g', 'h', 15 )
      ]
    )

g80d =
    ( [ ( 'b', 2, 0 )
      , ( 'c', 2, 0 )
      , ( 'd', 0, 0 )
      , ( 'f', 3, 0 )
      , ( 'g', 1, 0 )
      , ( 'h', 1, 0 )
      , ( 'k', 1, 0 )
      ]
    , [ ( 'b', 'c', 5 )
      , ( 'b', 'f', 8 )
      , ( 'c', 'f', 9 )
      , ( 'f', 'k', 17 )
      , ( 'g', 'h', 15 )
      ]
    )

degree g80 = g80d

Unit Test

import Html
import List
import Set


type alias Node comparable =
    ( comparable, Int, Int )


type alias Edge comparable =
    ( comparable, comparable, Int )


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


{-| Given a graph return a graph with the degree of each node correctly set
   so we can color the graph with the minimum number of colors
-}
degree : Graph comparable -> Graph comparable
degree ( nodes, edges ) =
    -- your implementation goes here
    ([],[])


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)
            [ degree graph84 == graph84
            , degree graph80 == graph80
            , degree graph81 == graph81
            , degree ( [], [] ) == ( [], [] )
            , degree loopsAndParallels == loopsAndParallels
            ]


g80 =
    ( [ ( 'b', 2, 2 )
      , ( 'c', 2, 2 )
      , ( 'd', 0, 0 )
      , ( 'f', 3, 3 )
      , ( 'g', 1, 1 )
      , ( 'h', 1, 1 )
      , ( 'k', 1, 1 )
      ]
    , [ ( 'b', 'c', 5 )
      , ( 'b', 'f', 8 )
      , ( 'c', 'f', 9 )
      , ( 'f', 'k', 17 )
      , ( 'g', 'h', 15 )
      ]
    )


graph80 =
    ( [ ( 'b', 2, 0 )
      , ( 'c', 2, 0 )
      , ( 'd', 0, 0 )
      , ( 'f', 3, 0 )
      , ( 'g', 1, 0 )
      , ( 'h', 1, 0 )
      , ( 'k', 1, 0 )
      ]
    , [ ( 'b', 'c', 5 )
      , ( 'b', 'f', 8 )
      , ( 'c', 'f', 9 )
      , ( 'f', 'k', 17 )
      , ( 'g', 'h', 15 )
      ]
    )


graph81 =
    -- has a loop and parallel edges
    ( [ ( 'b', 2, 0 )
      , ( 'c', 2, 0 )
      , ( 'd', 0, 0 )
      , ( 'f', 3, 0 )
      , ( 'g', 4, 0 )
      , ( 'h', 2, 0 )
      , ( 'k', 1, 0 )
      ]
    , [ ( 'b', 'c', 5 )
      , ( 'b', 'f', 8 )
      , ( 'c', 'f', 9 )
      , ( 'f', 'k', 17 )
      , ( 'g', 'h', 15 )
      , ( 'g', 'h', 14 )
      , ( 'g', 'g', 15 )
      ]
    )


graph84 =
    ( [ ( 'b', 3, 0 )
      , ( 'c', 2, 0 )
      , ( 'd', 0, 0 )
      , ( 'f', 4, 0 )
      , ( 'g', 3, 0 )
      , ( 'h', 1, 0 )
      , ( 'k', 1, 0 )
      ]
    , [ ( 'b', 'c', 5 )
      , ( 'b', 'f', 8 )
      , ( 'b', 'g', 9 )
      , ( 'c', 'f', 9 )
      , ( 'f', 'g', 13 )
      , ( 'f', 'k', 17 )
      , ( 'g', 'h', 15 )
      ]
    )


loopsAndParallels =
    ( [ ( 'b', 3, 0 )
      , ( 'c', 2, 0 )
      , ( 'd', 0, 0 )
      , ( 'f', 4, 0 )
      , ( 'g', 4, 0 )
      , ( 'h', 2, 0 )
      , ( 'k', 3, 0 )
      ]
    , [ ( 'b', 'c', 5 )
      , ( 'b', 'f', 8 )
      , ( 'b', 'g', 9 )
      , ( 'c', 'f', 9 )
      , ( 'f', 'g', 13 )
      , ( 'f', 'k', 17 )
      , ( 'g', 'h', 15 )
      , ( 'h', 'g', 15 )
      , ( 'k', 'k', 15 )
      ]
    )

Solution

Solution