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 )
]
)