summaryrefslogtreecommitdiffstats
path: root/189-broken.lua
blob: a4ae546465f275e00f742eaec182b6340a4c6ac4 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
local triangle_graph = {
}

--[[
http://en.wikipedia.org/wiki/Graph_coloring#Computing_the_chromatic_polynomial
]]
function chromatic_polynomial(g, t)
    local edge_start
    for v1, edges in ipairs(g) do
        for v2index, v2 in ipairs(edges) do
            if v1 == v2 then return 0 end
            if not edge_start then edge_start = v1 end
        end
    end

    if edge_start == nil then return t^#g end

    local edge_end = table.remove(g[edge_start])
    local edge_removed = chromatic_polynomial(g, t)
    table.insert(g[edge_start], edge_end)

    -- need to contract the edge here
    local edge_contracted = chromatic_polynomial(g, t)
    -- and then fix it back up

    return edge_removed - edge_contracted
end