Graph Colouring

       Now, I am creating a web application, Graph Coloring.The graphs are drowned using nodes and lines. In this Graph Coloring application, the nodes of the graph are colored using different colors for adjacent nodes. My application has two parts, one python script that runs in server and the other, an html file which act as user interface for the users.The html file provides the graphical view representation of my application.This application will be explained in detail, later on.

Graph and Graph Coloring

        Mathematically, a graph is a representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges.Vertices are also called nodes or points, and edges are also called lines or arcs.
        In Graph theory, graph coloring is a special case of graph labeling. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the same color; this is called a vertex coloring.

        Now let's going through the codes.In my application, i have used canvas in html file.Canvas is a rectangular portion or area within the html page, and you can control every pixel in it. The canvas element has several methods for drawing paths, boxes, circles, characters, and adding images. For drawing within the canvas, you should need Javascript. The codes are below.

<canvas id="graph" width="700" height="440" style="border:2px solid #000000;"></canvas>

The above code is used for drawing a canvas in html5. I have choose JavaScript for drawing on canvas.More details on canvas and Javascript are available at: http://www.w3schools.com/html5/html5_canvas.asp. 

       Here in the graph application my aim is use javascript for detecting the mouse movements so that i can get the position of each mouse click. Thus getting the points where mouse is clicked, so that i can draw the vertex and lines. I have assigned different clicks for application, double click for creating a node and two single clicks for drawing a line. My codes for mouse actions are below.

function Point(x,y){
    this.x = x;
    this.y = y;
}

function getMousePos(e){
    var point = new Point(0,0);
    if (e.pageX != undefined && e.pageY != undefined) {
point.x = e.pageX;
point.y = e.pageY;
}
    else{
point.x = e.clientX + document.body.scrollLeft +
document.documentElement.scrollLeft;
point.y = e.clientY + document.body.scrollTop +
document.documentElement.scrollTop;
}

    point.x -= canvas.offsetLeft;
    point.y -= canvas.offsetTop;
    return point;      
}

In the above code, mouse points are returned.the vertex and line are drowned using this points.

function drawcircle(e){
    point=getMousePos(e);
    if(checkNode(point,40)==-1){
Vertex(point,"black");
context.font = "10pt Courier New";
context.fillText(v,point.x+10,point.y-20);
v++;
vertex_list.push(point);
}
    else{ 
        alert("node overlapped");
}
}

function drawline(e){
    var point = getMousePos(e);
    var vertex_no=checkNode(point,40);
    if(vertex_no>=0){
if(start_edge==0){
 start_edge=1;
 selected_vertex=vertex_no;
 context.beginPath();
       context.moveTo(vertex_list[vertex_no].x, vertex_list[vertex_no].y);
}
else{
 start_edge=0;
          if(adj_list[selected_vertex]==undefined)
adj_list[selected_vertex]= new Array();
 if(adj_list[vertex_no]==undefined)
adj_list[vertex_no]= new Array();
 if(selected_vertex!=vertex_no){
adj_list[selected_vertex].push(vertex_no);
adj_list[vertex_no].push(selected_vertex);
 }
 context.lineTo(vertex_list[vertex_no].x,vertex_list[vertex_no].y)
 context.stroke();
 context.closePath(); 
}
}
    else
start_edge=0;
    }

       The functions ‘drawline’ and ‘drawcircle’ gets called when the user clicks, i.e. double or single click, anywhere within the canvas. Its arguments is a MouseEvent object that contains information about where the user clicked. Each functions calls getMousePos(e), where the getMousePos(e) returns the values of mouse coordinates where ever the user clicks within the canvas. The values are returned to a vertex_list.After the values are returned, they are used to draw nodes and lines within the canvas.
       Now for the coloring part, an adjacency list containing the list of nodes is needed for coloring.Since the html file is the client and the adjacency list are sent to the server. For communicating with server, i.e. the python script, jQuery is used.i have used jQuery for sending the adjacent list to the server running the python script where the coloring algorithm is implemented.For more details on jQuery visit http://www.w3schools.com/jquery/default.asp.
The complete the code of Graph coloring application is available at: https://github.com/jaseemkp/Graph-Coloring-Django
You can try the graph coloring application at : http://jastech-graph.herokuapp.com/