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.

MongoDB

MongoDB (said to be derived from humongous) is one of the important NoSQL databases used now. NoSQL can be read as no relations or sometimes Not only relations. Drawback is that NoSQL doesn't hold the ACID properties fully but in areas where humongous data needs to be handled(like facebook) then NoSQL is far more better than relational types. Mongodb follows document oriented storage. Mongodb handles the data as JSON documents (stored as BSON). It is flexible and it can store huge data at ease.

Enough said lets see MongoDB in action in our local machine.

sudo apt-get install mongodb

Now install pymongo (MongoDB api for python).

sudo easy_install pymongo

MongoDB with Flask

"Flask-PyMongo bridges Flask and PyMongo, so that you can use Flask’s normal mechanisms to configure and connect to MongoDB." (courtesy : http://flask-pymongo.readthedocs.org)

Install it via terminal by,

sudo easy_install Flask-PyMongo

Things are pretty easy than it sounds.

First initialize PyMongo on flask:

from flask.ext.pymongo import PyMongo

mongo = PyMongo(app)

Then initialize the connection for example:

from pymongo import Connection  

connection = Connection() 

db = connection.test_database

collection = db.test_collection

Above code use test_database which is a default one in MongoDB.

Accessing mongodb

posts = db.posts

posts.insert(post)

will insert the JSON data 'post' into the database.

db.posts.find() and db.posts.find_one()   will do the work of SELECT.

find_one() only returns one exact result.

for example:

db.posts.find_one({"title": filename})

The above code will return the document whose title field matches the variable filename.

One thing to note is that pymongo provides default '_id' field, but it stores it as a ObjectId. So using strings '1' '2' etc wont work in find function as id searching variables.

Click here to see the code of my paint app in flask using MongoDB as database.

MongoDB in Django

If you think flask was easy then Django is super-easy.

A lot of mongodb engines are available. Well i used the tutorial from the following site.

http://django-mongodb-engine.readthedocs.org/en/latest/topics/setup.html

Install Django-nonrel, djangotoolbox and Django MongoDB Engine.

Then make the following changes in DATABASES in settings.py.

DATABASES = {

   'default' : {

      'ENGINE' : 'django_mongodb_engine',

      'NAME' : 'test_database'

   }

}

Thats it. MongoDB works perfectly fine as any other database.

Paint App in Django

      Previously done paint app's frame work is changed from Flask to Django. Django feels like an alien for those who dealt with flask only. Its entirely different. Django follows MVC (Model View Control) architecture. Mine is a single app. Unlike in Flask we can create more than one app in a Django project. For a beginner the django book would be a blessing. It helped me a lot.

click here for Django tutorial


      The main difference between Flask and Django is defining databases. In Django we got a choice. We can either write database as raw as we did in Flask or we can use the models. According to django book writing raw codes is a bad example. I will agree with that because using models makes everything much easier. I am not sure about my level of knowledge in Django, but i can assure that its not that hard.

       We specify urls in urls.py in main project folder. Its like doing everthing independently. Views in views.py, defining template and static folders and database etc in settings.py etc. The files will be created automatically when we run the startproject command. All we have to do is fill it. People sometimes prefer Flask where flexibility is needed. Because sometimes Django's structure will give you some problems when defining your own functionality. Flexibility is less than Flask. If flexibility is not a factor for your app then Django is your thing. I am planning to do a Django app on some stock exchange data. When i finish that i will write a post on that one too.

Click here to see my Paint app code in Django