# 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