Sundio - Exercice 5

graph_coloring.ts

/// <reference path="./typings/globals/node/index.d.ts" />

namespace Sundio {
    /**
     * Vertex
     */
    export class Vertex {
        private _color: number;

        private _links: Vertex [];

        constructor() {
            this._color = null;
            this._links = [];
        }

        /**
         * Connects a vertex with another.
         * 
         * @param   vertex  Vertex to be linked to.
         */
        public addLink(vertex: Vertex): void {
            this._links.push(vertex);
        }

        /**
         * Retrieves the degree of the vertex.
         * 
         * @returns The number of links with other vertices.
         */
        public degree(): number {
            return this._links.length;
        }

        /**
         * Retrieves the requested neighbour vertex.
         * 
         * @param   n   The number of the vertex that we want to get (neighbours are in the same order we set them)
         * @returns The requested vertex.
         */
        public getNeighbour(n: number): Vertex {
            return this._links[n - 1];
        }

        /**
         * Checks if the vertex is painted.
         * 
         * @returns 'true' if the vertex have an assigned color, 'false' if not.
         */
        public isColored(): boolean {
            return this._color !== null;
        }

        /**
         * Retrieves the color of the vertex.
         * 
         * @returns The color of the vertex if is defined, if is not defined, returns null.
         */
        public getColor(): number {
            return this._color;
        }

        /**
         * Sets the color of the vertex.
         * 
         * @param   color   The color to paint the vertex.
         */
        public setColor(color: number): void {
            this._color = color;
        }
    }

    /**
     * Graph
     * 
     * Really it's a undirected, connected graph but to simplify it..
     */
    export class Graph {
        private _nVertex: number;
        private _nEdges: number;

        private _vertices: Vertex [];
        private _addedLinks: number;

        constructor(nVertex: number, nEdges: number) {
            this._nVertex = nVertex;
            this._nEdges = nEdges;

            this.fillVertices();
            this._addedLinks = 0;
        }

        /**
         * Checks if all the relations are set.
         * 
         * @returns 'true' if all the relations are set, false if not.
         */
        public isComplete(): boolean {
            return this._addedLinks === this._nEdges;
        }

        /**
         * Checks if all vertices have at least one relation.
         * 
         * @returns 'true' if all the vertices have some relation, 'false' if not.
         */
        public canBeColorized(): boolean {
            if (!this.isComplete()) {
                return false;
            }

            let allConnected: boolean = true;
            let nVertices = this._vertices.length;

            while (allConnected && --nVertices >= 0) {
                if (this._vertices[nVertices].degree() === 0) {
                    allConnected = false;
                }
            }

            return allConnected;
        }

        /**
         * Sets a relation between two nodes of the graph (don't allows loop relations).
         * 
         * @param   vertexA First vertex of the relation (really the order is not important).
         * @param   vertexB Second vertex of the relation.
         */
        public addLinkBetween(vertexA: number, vertexB: number): void {
            if (vertexA !== vertexB) {
                this._vertices[vertexA - 1].addLink(this._vertices[vertexB - 1]);
                this._vertices[vertexB - 1].addLink(this._vertices[vertexA - 1]);
                this._addedLinks++;
            }
            else {
                console.warn('To be able to color the graph, this cannot have loop relations. Thanks for your conprehension and try again.');
            }
        }

        /**
         * @returns The maximum degree of all the vertices.
         */
        public getMaxDegree(): number {
            let maxD: number = 0;

            for (let vertex of this._vertices) {
                maxD = Math.max(maxD, vertex.degree());
            }

            return maxD;
        }

        /**
         * @returns An array with all the vertices ordered by vertex number.
         */
        public getVertices(): Vertex [] {
            return this._vertices;
        }

        /**
         * Fills the graph with unconnected vertices.
         */
        private fillVertices(): void {
            this._vertices = [];
            for (let i = 0; i < this._nVertex; i++) {
                this._vertices[i] = new Vertex();
            }
        }
    }

    /**
     * GraphColoring
     */
    export class GraphColoring {

        public static colorize(graph: Graph, recursive: boolean = true): void {
            // If the graph can be colorized.
            if (graph.canBeColorized()) {
                // do it! (no matter the vertex from which we start coloring because all will be connected).
                const vertices = graph.getVertices();

                if (vertices.length !== 0) {
                    if(recursive) {
                        this.colorizeVertexRecursive(vertices[0]);
                    }
                    else {
                        this.colorizeVertex(vertices);
                    }
                }
            }
            else {
                console.warn('The graph cannot be colorized.');
            }
        }

        private static colorizeVertex(vertices: Vertex []):void {
            for (let vertex of vertices) {
                vertex.setColor(this.getProperColor(vertex));
            }
        }

        private static colorizeVertexRecursive(startVertex: Vertex): void {
            let nNeighbours: number = startVertex.degree();

            // If the vertex was already colored, this means we already have passed across it, so we need to do nothing.
            if (!startVertex.isColored()) {

                // Color the node with a diferent color that their neighbours.
                startVertex.setColor(this.getProperColor(startVertex));

                // And color their neighbours too.
                while (--nNeighbours >= 0) {
                    this.colorizeVertexRecursive(startVertex.getNeighbour(nNeighbours + 1));
                }
            }
        }

        private static getProperColor(vertex: Vertex): number {
            let colorChoise: number = 0;
            let found: boolean = false;

            while (!found) {
                // We will try to set the first available color.
                let nNeighbours: number = vertex.degree();
                let isCandidate: boolean = true;

                colorChoise++;

                // But if such color is set for at least one of our neighbours, we will try with the following.
                while (isCandidate && --nNeighbours >= 0) {
                    let neighbour: Vertex = vertex.getNeighbour(nNeighbours + 1);
                    if (neighbour.isColored()) {
                        if (neighbour.getColor() === colorChoise) {
                            isCandidate = false;
                        }  
                    }
                }

                // When the color is found, we can stop the loop.
                found = isCandidate;
            }

            // And return the found color.
            return colorChoise;
        }
    }
}

let readline = require('readline');

let rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
    terminal: false
});

/**
 * Auxiliar function that formats the stdin input.
 */
function getInputNumbers(line: string): number [] {
    let re = /^(\d+)\s(\d+)$/;
    let matches: RegExpExecArray;
    
    if ((matches = re.exec(line)) !== null) {
        return [
              parseInt(matches[1], 10)
            , parseInt(matches[2], 10)
        ];
    }

    return [];
}

let graph: Sundio.Graph = null;

// Waiting for stdin.
rl.on('line', (line) => {
    let numbers = getInputNumbers(line);

    if (numbers.length !== 0) {
        // If we don't have any graph to fill.
        if (graph === null) {
            // We need to create one with the given number of vertices and edges.
            graph = new Sundio.Graph(numbers[0], numbers[1]);
        }
        // If we already have a graph to fill.
        else if (!graph.isComplete()) {
            // Create the relation between the given vertices.
            graph.addLinkBetween(numbers[0], numbers[1]);
        }

        // If we have a completely filled graph.
        if (graph !== null && graph.isComplete()) {
            // We need to color it.
            Sundio.GraphColoring.colorize(graph, false);

            // And show the odd number of vertices
            let vertices = graph.getVertices();
            let oddVerticesNumber = graph.getMaxDegree();

            // It must be the max degree + one if it is even.
            if (oddVerticesNumber % 2 === 0) {
                oddVerticesNumber++;
            }

            // Show it
            console.log(oddVerticesNumber);


            // And show the color schema of the graph (ordered by node number)
            for (let vertex of vertices) {
                console.log(vertex.getColor());
            }

            //  Mark the graph to be erased by the garbage collector.
            graph = null;
        }
    }
    else {
        console.warn('The given input doesen\'t have the proper format. Try again!');
    }
})