asynchorous backtracking algorithm - graph coloring

export {Agent, Environment}
type AgentID = number
type Value = number

type Assignment = {
    agentID: AgentID,
    value: Value
}
type Nogood = Assignment[]
type QueuedMessage = {
    type: 'OK' | 'NOGOOD' | 'ADD_NEIGHBOR',
    from: AgentID,
    to: AgentID,
    payload: any
}

class Agent {
    id: AgentID;
    domain: number[];
    neighbors: number[];
    terminated: boolean;
    currentValue: number;
    agentView: Map<number,number>;
    nogoodList: Nogood[];
    environment: Environment;

    constructor(id: AgentID, domain: number[], neighbors: number[], environment: Environment) {
        this.id = id;
        this.domain = domain;
        this.neighbors = neighbors;
        this.terminated = domain.length === 0;
        this.currentValue = this.terminated ? -1 : domain[0];
        this.agentView = new Map<number,number>;
        this.nogoodList = [];
        this.environment = environment;
    }

    initialize(){
        for (const neighbor of this.neighbors) {
            if (neighbor > this.id) {
                this.environment.sendMessage(
                    'OK',
                    this.id,
                    neighbor,
                    [this.id, this.currentValue]
                )
            }
        }
    }

    isConsistent(agentView: Map<number,number>, currentValue: number): boolean {
        for (const [agentId, otherAgentValue] of agentView) {
            if (otherAgentValue === currentValue)
                return false
        }

        // no good

        for (const nogood of this.nogoodList) {
            const matchesView = nogood.every(assign => {
                if (assign.agentID === this.id) return assign.value === currentValue
                return agentView.get(assign.agentID) === assign.value
            })
            if (matchesView) return false
        }


        return true
    }

    handleMessage(msg: QueuedMessage){
        if (msg.type === 'OK') {
            this.agentView.set(msg.payload[0], msg.payload[1])
            this.checkAgentView()
        } else if (msg.type === 'NOGOOD') {
            this.nogoodList.push(msg.payload)
            for (const [Ak, dk] of msg.payload) {
                if (!this.neighbors.includes(Ak)) {
                    this.agentView.set(Ak, dk)
                    this.environment.sendMessage('ADD_NEIGHBOR', this.id, Ak, null)
                }
            }
            this.checkAgentView()
        } else {
            this.neighbors.push(msg.from)
            this.environment.sendMessage('OK', this.id, msg.from, [this.id, this.currentValue])
        }
    }

    checkAgentView() {
        console.log("in agent view", this.agentView)
        if (!this.isConsistent(this.agentView, this.currentValue)) {
            console.log("inconsistent")
            let candidate = this.domain.find((element) => this.isConsistent(this.agentView, element))
            if (candidate === undefined) {
                this.backtrack()
            } else {
                this.currentValue = candidate
                let lowerPriorityNeighbors = this.neighbors.filter((n) => n > this.id)
                lowerPriorityNeighbors.forEach((n) => this.environment.sendMessage('OK', this.id, n, [this.id, this.currentValue]))
            }
        }
    }



    backtrack() {
        let nogood = this.hyperresolve(this.nogoodList)
        if (!nogood || nogood.length === 0) {
            this.environment.broadcastTermination()
            this.terminated = true
        } else {
            let lowestPriorityNeighborNogood = nogood.reduce((prev:Assignment, curr:Assignment) => prev.agentID < curr.agentID ? curr : prev)
            this.environment.sendMessage('NOGOOD', this.id, lowestPriorityNeighborNogood.agentID, nogood)
            this.agentView.delete(lowestPriorityNeighborNogood.agentID)
            this.checkAgentView()
        }
    }

    hyperresolve(nogoodList: Nogood[]): Nogood {
        let res = new Map<AgentID, Assignment>()

        for (const nogood of nogoodList) {
            for (const assignment of nogood) {
                if (assignment.agentID === this.id)
                    continue
                else
                    res.set(assignment.agentID, assignment)
            }
        }
        return [...res.values()]
    }
}

class Environment {
    agents: Map<AgentID, Agent> = new Map()
    messageQueue: QueuedMessage[] = []
    running: boolean = true

    addAgent(agent: Agent){
        this.agents.set(agent.id, agent)
    }

    sendMessage(type: 'OK' | 'NOGOOD' | 'ADD_NEIGHBOR', from: AgentID, to: AgentID, payload: any):void {
        this.messageQueue.push({type, from, to, payload})
    }
    broadcastTermination() {
        console.log("TERMINATED")
        this.running = false
    }

    async process() {
        this.agents.forEach(a => a.initialize())
        console.log("after agent view")
        while (this.running && this.messageQueue.length > 0) {
            let msg = this.messageQueue.shift()!
            const receiver = this.agents.get(msg.to)
            if (!receiver) continue
            receiver.handleMessage(msg)

        }

        if (this.running) {
            console.log("--- Solution Found ---");
            this.agents.forEach(a => console.log(`Agent ${a.id}: ${a.currentValue}`));
        }
    }
}

// RUNNING
let env = new Environment()
let agent0 = new Agent(0, [0,1,2], [1,2], env)
let agent1 = new Agent(1, [0,1,2], [2], env)
let agent2 = new Agent(2, [0,1,2], [], env)

env.addAgent(agent0)
env.addAgent(agent1)
env.addAgent(agent2)

env.process()