# OK to post homework
# Robert Dougherty-Bliss
# 2021-04-04
# Assignment 19

read "C19.txt";

# 1.

# A graph is a pair (V, E), where V is a set and E is a subset of the pairs of
# V.

# If there are no edges, then every vertex can be colored with any of the t
# colors. Thus CrP(G, t) = t^|V| when |E| = 0.

# Suppose that there is at least one edge. We would like to reduce the problem
# to a smaller graph somehow. It makes sense to just delete that edge and try
# to color things again. This will work so long as the vertices incident to
# that edge are not colored the same, and there is a natural bijection between
# such "failed-smaller-colorings" and the colorings of G where we *contract*
# the edge.

# Okay, I understand it!

# 2.

# We want to get to the base case as quickly as possible. Without being clever,
# it doesn't seem like there's an easy way to pick an optimal edge. Rather than
# picking the first edge, I'll try actually picking one at random.

CrPChoice := proc(G, t, selector)
    local e:
    if G[2] = {} then
        return t^nops(G[1]):
    fi:

    e := selector(G):
    CrP(DelEd(G, e), t) - CrP(ConEd(G, e), t):
end:

originalChoice := proc(G)
    return G[2][1]:
end:

randomChoice := proc(G)
    return G[2][rand(1..nops(G[2]))()]:
end:

mostNeighbors := proc(G)
    local max, bestEdge, e, neighbors, k:
    max := -infinity:
    bestEdge := FAIL:

    for k from 1 to nops(G[2]) do
        e := G[2][k]:
        neighbors := nops(select(edge -> edge[1] in e or edge[2] in e, G[2])):
        if neighbors > max then
            max := neighbors:
            bestEdge := e:
        fi:
    od:

    bestEdge:
end:

leastNeighbors := proc(G)
    local min, bestEdge, e, neighbors, k:
    min := infinity:
    bestEdge := FAIL:

    for k from 1 to nops(G[2]) do
        e := G[2][k]:
        neighbors := nops(select(edge -> edge[1] in e or edge[2] in e, G[2])):
        if neighbors < min then
            min := neighbors:
            bestEdge := e:
        fi:
    od:

    bestEdge:
end:

time(CrPChoice(Kn(8), t, originalChoice));
time(CrPChoice(Kn(8), t, randomChoice));
time(CrPChoice(Kn(8), t, mostNeighbors));
time(CrPChoice(Kn(8), t, leastNeighbors));

# These are all roughly the same. I don't see any big savings!

# 3.

PetersonV := {seq(1..10)}:
PetersonE := { {1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 1}
             , {1, 6}, {2, 7}, {3, 8}, {4, 9}, {5, 10}
             , {6, 8}, {6, 9}
             , {7, 9}, {7, 10}
             , {8, 10}
             }:

Peterson := [PetersonV, PetersonE]:

P := CrP(Peterson, t);
factor(P);

subs(t=1000, P);