Implementation of Graph DS using Python and BFS,DFS covered with iteration

This post will be mostly code. Please use proper indenting cuz Python otherwise will make your life hell. If you’re using Sublime go to, set Convert Indentation to tabs.

Gist : I have used the collections.defaultdict dict DT for implementing a dict of sets.
Vertices have been stored as adjacency list kind of elements as a dictionary. The code is raw and may have errors ( though no compilation error as of the post’s writing). Please comment for additional details. This is purely for testing purposes.


 

graph            A Graph.

 



from collections import defaultdict

#The Graph will be a dictionary of sets
class Graph():

def __init__(self, connections, directed = False):
self.graph = defaultdict(set)
self.directed = directed
self.add_connections (connections)

def add_connections(self, connections):
for node1,node2 in connections:
self.add_connection(node1,node2)

def add_connection(self, node1, node2):
self.graph[node1].add(node2)
if not self.directed:
self.graph[node2].add(node1)

def remove(self, node):
#removes all references to the node
#Use iteritems for dict items like k,v in dictname.iteritems():
for n,cons in self.graph.iteritems():
try:
#Removing from a set involves setname.remove(element)
cons.remove(node)
except KeyError:
pass
try:
#Removing from a dictionary involves rem dict_element_name
del self.graph[node]
except KeyError:
pass

def isconnected(self, node1, node2):
if node1 in self.graph[node2] or node2 in self.graph[node1]:
return True
return False

def dfs(self,start):
#If start node does not exist, return None (search is futile)
if start not in self.graph:
return None
#Start with an empty set
visited = set()

#To return unse ( which is not a set
unset = []
#Initially fill stack with start vertex
stack = [start]

#While stack is not empty keep repeating this algorithms
while stack:
#Take the first element of stack (pop means last inserted , aggressive)
vertex = stack.pop()
#If vertex has not been visited yet, add it to visited and look for all the element in graph[vertex]
if vertex not in visited:
visited.update(vertex)
unset.append(vertex)
stack.extend(self.graph[vertex] - visited)
return unset

def bfs(self, start):
if start not in self.graph:
return None
visited = set()
queue = [start]
unset = []
while queue:
vertex = queue.pop(0)
if vertex not in visited:
visited.update(vertex)
unset.append(vertex)
queue.extend(self.graph[vertex] - visited)
return unset

#Should work but not tested
def findpath(self,v1, v2):
m = bfs(v1)
if v2 in m:
return m[:m.index(v2)+1]
return None

 

Advertisements

Promises (and async prog) in JavaScript – To be continued..

For those living under a rock in the world of Web Dev and who missed the big buzz when Promises in JavaScript were the talk of the town. I present this article. Yeah, I am one of you and did not really bother to check them out because most of my routine tasks were being performed using Callbacks. Now, since I think I have some time to look into it ( free from my BackEnd work) I am interested in writing about them.

Notes to self : I Promise that this won’t be a long post. I Promise that this post will give only an elementary idea of Promise in JS because I myself found it very difficult to find something, giving you a very elementary idea of the same. I also Promise that I will not keep your hanging and add all the relevant context that you need to know/understand in order to understand JavaScript Promises, like async. 


 

promise

What is ‘Asynchronous Programming’ in JS ?
console.log("A");
jQuery.get("X.html",function(){
console.log("B");
});
console.log("C");

The mentioned code extract may or may not return the Alphabet output A B and C in order. It may be A C B too. Why? Because B is executed asynchrnously. Because loading the X.html page may take time and is executed as soon as its available and the extract console.log("C"); does NOT wait for it to complete.
See this code extract :

tweet = A(); //Line1
//Do something with tweet
doSomeImportantThings; //Line2

So, line number 2 will not be able to execute until Line 1 is done and the next things are done as JavaScript is single threaded.

But, now check this code :

A(function(){ //Line 1
//Do something with tweet
});
doSomethingWithTweet(); //Line 2

Here, A does stuff asynchronously and Line2 will not wait for A to finish. This is the beauty of Asynchronous execution. But, at times, when things are asynchronous it may lead to trouble if we exactly need the things to happen in some order.

Consider the scenario below :

  1. Load a Loading GIF file to indicate page is loading
  2. Load Images
  3. Load Fonts
  4. Load Everything else relevant
  5. Only if all are loaded, remove the GIF Loader and display the content

Due to JavaScript’s synchronous execution and single-threadedness the above order may not be executed as we desire. Say, Images and Fonts are from third party websites like Google and hence, asynchronous loading is necessary. So, it will take a while. Not sure how much though and the Loader will also not know what is the finishing time. This is sad. Check Pseudo code :


loadLoaderGif();
getImages{function('url'){
//load the images from the URL
})();
getFonts(function('fontsurl'){
//Load fonts
})();
//etc. etc.
//unloadLoaderGif();

As you can tell, based on your internet speed and mostly any damn internet speed, loadLoaderGif() and unloadLoaderGif(); will execute almost immediately whereas the async functions will take their own time for fetching images and laying them at the right places etc. So, the whole purpose has been defeated yeah ? Ok. To solve this our forefathers already included callbacks in JS.

Check this pseudo-code extract :

loadLoaderGif();
n = function('fontsurl'){
//Load fonts
UnloadLoaderGif();
}
m = function('url' , getFonts, n){
//load the images from the URL
getFonts(n);
}
(function(getImages, m){
getImages(m);
}());

Oh. Callback hell!

Now, how about this???

loadLoaderGif();
//I am a magical block of code and I ensure you that I will execute
//All of the loaing n crying, ranting stuff and then only let the function next
//to me execute
unloadLoaderGif();

See the middle block of comments !!!!
Yeah, Promises come into the picture now.

INCOMPLETE ( To be continued )

Detach yourself from association of your favorite website/app from a Social Network

So friends, I am pretty sure that some of you are totally annoyed with your inability to deactivate your facebook account because you have your favorite webapp associated with Facebook for login. This sucks to be honest.

Ok, chances are that the DB of the webapp that you want to use has your email ID set as a regular user and Facebook association is only a FK relationship. Good news.

In simple words, you can actually (99% chances) detach your favorite webapp from a social site by just resetting the password using the Forgot Password option. I tried it with Duolingo and it works haha.

So, go ahead n deactivate facebook peacefully and still log0in to your favorite webapp. Good luck!

facebook-sucks

 

An open source ‘Good’ Web Application stack

Web Framework – Django : Python or Flask : Python

Server – Apache HTTP Server

Database – MySQL

Virtual Environment – Vagrant (You want Docker ?)

Task Watcher – Grunt

Database Agent – Sequel Pro (Macbook <3)

Server – AWS EC2

Media Server (if any) – AWS S3

Add some cute JS, CSS3, HTML5 etc. to the front end.

I guarantee some considerable amount of your savings in your next web app budget!

Django Basics : Part – 3

 

 

So, I hope you managed to setup the django project and could visit the welcome page after running the server. Now, this tutorial contains the interesting part. Creating an app that works !!!! Interesting ? Yes, certainly, for I will guide you in this tutorials as how to create models, url configurations, map a basic relationship between models, migrate the models to create suitable relations in the DB (SQLLite in your case), write code to query the database and also, run the django shell ( a ridiculously important part of learning django), apart from the primary task of getting the application run on the default django server.

In some future tutorial I will guide you how to setup django with Apache server and MySQL.

django-python

Let’s now create an app within the musicStore project.


 

Create the app

$python manage.py startapp musicApp

This creates all the necessary files inside the musicStore/musicApp/ directory.


 

Confirm if the following files were created after this command. 

musicStore/musicApp/__init__.py
musicStore/musicApp/apps.py – Configurations for the app for django settings. We won’t usei t in this tutorial, new addition in 1.9
musicStore/musicApp/models.py – Modles are created here
musicStore/musicApp/views.py  – Views are created here (Kind of Controller logic analogous to MVC)
musicStore/musicApp/urls.py – URL routing information, maps URLS to Views
musicStore/musicApp/admin.py – Admin settings for the app useful for the admin console
musicStore/musicApp/migrations/ – Contains all the migrations file so that any database change is recorded and could be used, reverted to etc.
musicStore/musicApp/tests.py  – File to contains unit tests. Mock-Brraintree would be a good start which I will cover in some future tutorial


 

“Projects vs. apps

What’s the difference between a project and an app? An app is a Web application that does something – e.g., a Weblog system, a database of public records or a simple poll app. A project is a collection of configuration and apps for a particular website. A project can contain multiple apps. An app can be in multiple projects.”

-From the django website


Model

Screen Shot 2016-03-01 at 3.52.47 PM

We can see that there are two models, Album and Artist. One Album can have only 1 Artist but 1 Artist can publish multiple Albums. This relationship is defined by the Foreign Key field in Album, album_artist and hence, every Artist object will have an album_set object containing the list of Albums that it may have, and this is a django property.

You will also observe a Meta inner class in the model. this is used to define important metadata pertaining to the model, like ordering of model objects if displayed in a list somewhere, name it will be known as in the DB, name it will be known as in the admin console etc and many more. Full documentation is available in : https://docs.djangoproject.com/en/1.9/intro/tutorial02/

 


Migrations 

Screen Shot 2016-03-01 at 2.02.28 PM
makemigrations command

 

Screen Shot 2016-03-01 at 2.02.44 PM
sqlmigrate <migration_id> command

 

Screen Shot 2016-03-01 at 2.02.56 PM
migrate command

$python manage.py makemigrations
It tells Django that some changes to our models have been made, and are to be stored as a migration in the musicapp/migrations/ directory.

At this point, we can either directly migrate to apply those changes from the migration file or we can check the actual set of SQL commands that are going to be executed by django. The former is done by the migrate command while the latter can be performed by the sqlmigrate <migration_id> command.

In short, makemigrations forms a migration file but doesn’t apply any changes yet. migrate actually applies the changes recorded in the migration file.


 

__str__ method of models

Screen Shot 2016-03-01 at 2.16.35 PM

Now, we add the __str__ method in the models because it provides us the string representation of an object whenever queried. You’ll understand the importance once you start using the shell or the admin console, apart from others which utilise it.


 

Using the django shell

$cd ~/Desktop/musicStore/
$python manage.py shell
>>>from musicApp.models import Artist
>>>Artist.objects.all()
[]
>>>from musicApp.models import Album
>>>Album.objects.all()
[]

First of all, congrats on getting access to the django shell. Here you can do a lot of things, including querying the django database and everything python. it is useful for small fixtures like checking if some value is being returned the way it is supposed to be, before applying changes in the UI etc. You will learn a lot more about it in the tutorial and coming posts.


 

Adding models objects – Continue the terminal from the previous section

>>> artist1 = Artist(artist_name = “The Chainsmokers”, artist_twitter_id = “TheChainsmokers”, slug = “thechainsmokers”)

>>> artist2 = Artist(artist_name = “Imagine Dragons”, artist_twitter_id = “ImagineDragons”, slug = “imgd”)

Add Artists

Screen Shot 2016-03-01 at 3.51.43 PM.png
Add Albums

 

Note : As you can see, we are adding stuff via the django shell but evenetually, there will be forms in the web page in the form of django forms or HTML forms which will help you add objects. this addition via shell is for illustrative purposes. 

artist1.album_set gives you the albums related to the artist1 and so on. This means, if A has a Foreign Key B, any instance of B, say b, can query all the related instances of A as b.a_set.all() and so on.



To be continued….

Next tutorial will be on using URLS and Views to query these model objects.