local n = 80 local rOuter = 240 local rCircles = 7 local sx, sy local adjacent = {} local working = {} local workingCount = 0 local iterations = 0 local d local p0 local pedge = 0.04 local function neighbours(k) local w = {} for l = 1,n do if adjacent[k][l] then w[#w+1] = l end end return w end local function getAverageDegree() local sum = 0 for k = 1,n do sum = sum + #neighbours(k) end return sum/n end local function newRandomGraph(p) for k = 1,n do adjacent[k] = {} for l = 1,n do adjacent[k][l] = false end end local ne = n * (n-1)/2 for i = 1,ne do if love.math.random() < p then local k,l = love.math.random(n), love.math.random(n) adjacent[k][l] = true adjacent[l][k] = true end end d = getAverageDegree() p0 = 1/(d+1) end function love.load() sx, sy = love.graphics.getWidth(), love.graphics.getHeight() cx, cy = sx/2, sy/2 newRandomGraph(pedge) love.graphics.setBackgroundColor(204, 231, 244) end local function coords(k) local phi = 2 * math.pi * k/n return sx/2 + rOuter * math.cos(phi), sy/2 + rOuter * math.sin(phi) end function love.draw() for k = 1,n do for l = k,n do if adjacent[k][l] then local x1,y1 = coords(k) local x2,y2 = coords(l) love.graphics.setColor(10, 10, 10) love.graphics.line(x1,y1,x2,y2) love.graphics.setColor(0, 0, 0) end end end for k = 1,n do local x, y = coords(k) if working[k] then love.graphics.setColor(128, 0, 0) else love.graphics.setColor(150, 150, 255) end love.graphics.circle("fill", x, y, rCircles) love.graphics.setColor(0, 0, 0) end love.graphics.print("Got " .. tostring(workingCount) .. " nodes working", 5, 5) love.graphics.print("Average of " .. tostring(d) .. " conflicts", 5, 17) love.graphics.print("Iteration #" .. tostring(iterations), 5, 30) end function love.update(dt) -- Toss some coins to see who wants to work local wants = {} for k = 1,n do wants[k] = love.math.random() < p0 end local newWorking = {} local newWorkingCount = 0 -- Find out who should work in the end for k = 1,n do -- Are all neighbours idle? local neighboursIdle = true for _, l in ipairs(neighbours(k)) do if wants[l] then neighboursIdle = false break end end -- We only work if we want and all neighbours don't newWorking[k] = wants[k] and neighboursIdle if newWorking[k] then newWorkingCount = newWorkingCount + 1 end end -- Update if we improved if newWorkingCount > workingCount then working = newWorking workingCount = newWorkingCount end iterations = iterations + 1 end