September 20, 2010

Vertex coloring problem app in Google app engine

Filed under: Projects — shijitht @ 12:37 am

Google App Engine lets you create and deploy apps on the same machine which servers google apps like Gmail. As we all know, it is a cloud infrastructure. Sandbox is the name of the virtual environment(machine), for running our apps. Our aim is to create an app to solve graph(vertex) coloring problem.

The problem is, no two adjacent nodes in the graph should have the same color. The input is a graph and  output  its colored form. The output is shown in the browser and use of HTML 5, JavaScript and Django is gonna make it interesting.

Google App Engine

Goole App Engine allows your apps to run in the sandbox. Like said, it is a secure box. It got some restrictions like can’t write to filesystem, only read files uploaded by the app, use specified APIs to get access to resources and services and there is a dead line for responses. Violation of these limits will end in an exception. And the free account limits a user in other ways like the usual storage limit, connection limit. Go visit the site for more details.

The app engine now supports two runtime, python and java. I prefer python, so I gone a stick to it. The sandbox has a standard python interpreter. The libraries which conflicts with the above mentioned policies are removed. It provides a data model to store data and api for managing it. The web frameworks like Django are also supported. As the site has a more detailed documentation for theses things, lets move to what I have done.

Getting started

Google App Engine resides in a remote server. So there will be question about how to develop offline. The emulation of app engine can be produced offline using App Engine SDK. It is available online. Install it and conform the requirements like run time support are satisfied in your system.


Start the project by creating a folder for it. The app consists of mainly three type of files. app.yaml, project.py and index.html. This is the case for a simple project. To bring order in a little bigger project, the css, js, image etc folders could be included and more html pages for better functionality. The app.yaml file should be updated to reflect these changes.

app.yaml is the configuration file of app engine. It specifies the runtime, version, url handling etc. The python script does all data processing and transactions. To provide an MVC, the html elements are separated from the script(model) and put in separate html files(view). The current situation gives a lot of web tools and frameworks to develop front end. And app engine supports most of the frameworks. The SDK comes with inbuilt webapp and Django support. I used a mix of HTML 5, JavaScript, CSS, Django as front-end and python, app engine as back-end.

Canvas element in HTML 5 provided the canvas and images were drawn with JavaScript. CSS styles the pages and Django allows an easy integration with server for the creation of dynamic pages. You can find the code at http://github.com/shijith/ColoringProblem. This app is hosted under http://coloringproblem.appspot.com. For an example, see an instance of coloring

Some ideas

While developing a clicking application like this, a certain doubt is; How could you know, whether the click was on a circle or not. The answer is, for a circle at (0,0)

x^2 + y^2 = r^2 .

Let the circle be at (x1,y1) and click at (x2,y2). A point inside the circle should satisfy,

(x2 - x1)^2 + (y2 - y1)^2 <= r^2 .


Google app engine provides a very fast and reliable server for our apps and at no cost. HTML 5 includes a lot of in build elements for the creation of heavy graphics applications with JavaScript. The recent developments in browser technology fastened (300X) JavaScript execution and hence providing for the overall performance. With CSS 3 more effects can be added with less effort like round curves or a box. App engine dashboard provides detailed error report which eases error detection and debugging.


1 Comment »

  1. […] Vertex coloring problem app in Google app engine September 2010 4 […]

    Pingback by 2010 in review « The Sandbox — January 2, 2011 @ 6:38 pm

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: