Graph coloring app

     This Graph coloring app does a special case of graph labeling where we color the nodes according to the constraint that no two adjacent vertices have the same color. Front-end of this app is done in Javascript, HTML5 canvas and back-end in Python.

Forming adjacency list

          The input for the graph coloring algorithm is an adjacency list. Adjacency list consist details about the vertices to which a vertex is connected to.

For example.

   

  The adjacency list for the above graph is,

        

          a: [b, c]

        b: [c, a]

        c: [a, b]

  In this app adjacency list is created in JS.

  The technique used was that when we connect vertex 'a' with vertex 'b', we make two changes in the adjacency list.

   We update vertex a's adjacent list by including b  and we update vertex b's adjacent list by including a.

Simple Graph coloring algorithm

    --The Graph coloring algorithm is implemented in Python.

    --The approach i used is simple.

   -- We create a list called check to indicate whether a node is colored or not. Say, there are six nodes.

    --Then check will contain 6 elements, all '0' initially( [0, 0, 0, 0, 0, 0] ).When a node is colored corresponding element in check is changed to 1. Say if node 3 is colored then we change the 2nd element of list to 1 (since indexing starts from 0).

    --Then we loop over each nodes.

    --In each loop we take the node's adjacent vertices.

    --Then we check whether any of those vertices are colored (The checking is done using the 'check' list).

    --If colored then we will remove those colors from color_list and color the node by selecting one from remaining colors. 

Graph coloring algorithm in python

Here adj_list is the input and color_data is the output.

           not_colored = sorted(adj_list.items(), key=lambda k: len(k[1]), reverse=True)  
           check = len(not_colored) *[0]  
           color_data = {}  
           color_list = [ i for i in range(0, len(not_colored))]  
           for node in not_colored:  
                color_list_dup = []  
                color_list_dup.extend(color_list)  
                for j in node[1]:  
                     if check[j-1]:  
                          try:  
                               color_list_dup[color_data[j]] = None  
                          except:  
                               pass  
                for color in color_list_dup:  
                     if color != None:  
                          color_data[int(node[0])] = color  
                          break  
                check[int(node[0])-1] = 1  
           print color_data  

    The output of the example we used earlier  will look somewhat like the below one in our Graph coloring app.

Check out the source code of the app to see more details , click here.