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 )

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. 

 

Django Basics : Part-2

magic-pony-django-wallpaper

‘M happy to be back to  you all.

So, this post will help you setup your first django web app and will also fill in details and notes on how many of its small components work and interact. I have just explained the basic components in my previous post which is the first part without any hint of python-django code. Let me do that this time and get you acclimatized to the things that may go wrong often as well, apart from the things that will go right! This part 2 tutorial will comprise a few defined set of steps.
Before we begin I want you to refer this tutorial if you want to know anything about writing your first django app beyond this tutorial please visit : https://docs.djangoproject.com/en/1.9/intro/tutorial01/
Also, I assume that you have python 2.7 installed in your machine as this tutorial will be on django 1.9x and python 2.7. this tutorial should work on both Windows and Unix based systems, including Mac, though the directory structure is assumed to be of Mac. One can use it in Windows by making slight changes to the tutorial’s instructions.

So, let’s begin…

To know how to install pip please refer my tutorial on installing pip. All the commands below are to be executed in the terminal.

Install django

$pip install django

 

Check if Installation is successful

$python
>>>import django
>>>print django.get_version()

This will tell you the version of django that you just installed. If you did not install it properly you will see error messages in executing the first or the second function.
When done, type :

>>exit()
or
>>>ctrl + D

to exit from the python prompt

 

Create your project directory and ‘cd’ to it

$cd ~/Desktop/
$mkdir djangoTutorialStuff
$cd djangoTutorialStuff

 

Make a django project

$django-admin startproject musicStore 

Check if it worked and you may want to check the directory structure too.
$cd musicStore

You’re gonna see two things inside the project. A manage.py file and a musicStore directory. The manage.py is the principle python file governing the whole project. Anything you want to do with the project goes like python manage.py <your_command>.

Confirm if the musicStore directory has the following files : 

__init__.py  – Tells that this directory is a django directory
settings.py  – Contains the overall settings of the whole django project (musicStore)
urls.py  – Contains the root url configurations for the musicStore project
wsgi.py  – contains the application callable which the application server uses to communicate with your code

As of now, only the project has been setup without any setting changes.
Next you have to create app(s) of your choices to actually do something of its own. These apps are pluggable django entities that can also be used by other projects like musicStore does.  Apps will be created in the next tutorial – Part 3 !

Confirm if project setup works 

$cd ~/Desktop/musicStore
$python manage.py runserver

Verify if the following output shows up :

Performing system checks…
System check identified no issues (0 silenced).
You have unapplied migrations; your app may not work properly until they are applied.
Run ‘python manage.py migrate’ to apply them.
February 29, 2016 – 15:48:41
Django version 1.9.1, using settings ‘musicStore.settings’
Starting development server at http://127.0.0.1:8000/
Quit the server with CONTROL-C.

Now visit : http://127.0.0.1:8000/

If django welcome page shows up you’re good to go. If not, please leave a comment.

So you wanna GIT ?

Why GIT ?


Every time you’re asked to submit that crucial programming assignment what comes to your mind after completion of the program ? Uh, not a movie. It’s GIT I know ! So, that’s exactly how you proceed towards storing your lovely little program forever so that you can hug your code every time you miss your ex right?

Git is a terrific way to store not just code but almost every kind of file you can think of that can be stored online. It employs altogether a different approach of controlling versions of your files. While other similar tools like SVN are Centralized Revision Control Systems (CRVS), Git employs Distributed Revision Control System(DRVCS). So, every person having access to your repository can clone your code and maintain a local copy of exactly the same data as in GitHub and can make changes locally with full control. So, in some catastrophical situation, god forbid, some client who cloned your code from Peru can help you to recover your data !!!

There can be nothing better than Git’s own website but I am here to help you skip some contrived details and dive right into basic usage of Git.


Basic Commands

        • git init – Initializes a local Git repository in your current local directory
        • git clone <remote_repository_name> – Clones a remote repository to your local git repository
        • git add <file_name1,file_name2...> or git add * or git add . – Stages (consider it analogically as a local buffer where you store files that are to be committed) your marked files or all for commit
        • git commit -m "<message>" – Commits the staged files with ‘message’ as commit message
        • git push <remote_name> <remote_branch_name> – Pushes your code to the remote named ‘origin’ and its branch ‘master’
        • git remote add <remote_name> <remote_repository_URL> – Adds a remote repository of given name and given URL
        • git remote -v – Displays all remotes with URLs
        • git checkout -b feature_x – Creates a new branch ‘feature_x’ and switches to the branch
        • git branch -a or git branch -r or git branch– Shows branches ; ‘r’ for remote only
        • git checkout -- <file_name> – Discards changes to file
        • git log – Gives commit history
        • git status – Gives status of staging area and working directory
        • git checkout <branch_name> – Moves the HEAD to the specified branch
        • git pull – Pulls code from remote repository’s tracker branch (default /master) to current local branch
        • git fetch origin – Fetches code first from Remote repository’s tracker branch to local branch without merging th code. Gives a chance to check the code before merging
        • git merge <branch_name> – Merges fetched code from specified branch

Note : I will be covering a topic on Basic Branching and Merging in GIT including Merge conflicts soon


Don’t play around with the commands below !!!

      • git reset --soft HEAD~ – Move HEAD to previous commit, Staging Area stays the same
      • git reset --mixed HEAD~ – Move HEAD to previous commit, Staging area also gets erased, Working Directory unaffected
      • git reset --hard HEAD~ – Move HEAD to previous commit, Staging area erased, Working directory moved to previous commit DANGEROUS !!!
      • git reset HEAD <file_name>– Unstages the specified file

A Simple MD5 Password Cracking Program using Python


While on my way to completion of my program in Information Systems at University of Cincinnati, I stumbled upon this very interesting assignment in my Cloud Computing course offered by the computer science department. It was a simple 4 or less character strings password breaker that attacks a given 32 or less characters’ hex string and provides the strings that are in its VALUE BUCKET. For example we have the sample execution :

Attacking d077f…

{‘found’: [‘cat’, ‘gkf9’]}

In the aforementioned example we are attacking the first 5 characters of a 32 digit hashed hex string where the values collide. That’s another topic of interest that I will discuss later.

The program uses mincemeat.py module from https://github.com/bigsandy/mincemeatpy. This is a Python 2.7.x Map Reduce library that can divide map and reduce tasks to distributed clients to make tasks faster. In my upcoming posts I will write about Map Reduce and Hadoop.

Logic

  • Generate all possible strings of size 1 to 4 using (0-9) and (a-z)
  • This can be done in various ways like using pre-built libraries or by some fresh logic like generating first the two character strings and then looping them and appending the same two character strings to them. Once ready, we can choose any series from the list starting with any value from 0 to z ,say , 0000 to 0zzz and consider their last three characters as another addition to our main list. Once done, we can take two character strings and append to the main list and finally, one character strings. This way, we have a total list generating all possibilities of strings form 1 to 4 characters of {0-9 and a-z} in any combination.

  • Build grains using modulus technique and send to map function.
  • In the original list ‘bigdata’ we find the length of the list as len(bigdata) and find all its factors. Once found, we can think of the possible number of clients that will execute the map functions and divide the list accordingly in a dictionary of lists , say, {[‘0’, ‘list-chunk1’],[‘1′,’list-chunk2’]…} and build a datasource dictionary using this to be sent to the servers.

  • Since the map function and reduce function cannot use global variables from the parent program we have to pass the input hashed hex string in the datasource itself by a simple technique of sending a dictionary within a dictionary. So, instead of {[‘0’, ‘list-chunk1’],[‘1′,’list-chunk2’]…} the datasource looks like {[‘0’, {‘d077f’,’list-chunk1′}],[‘1’,{‘do77f’,’list-chunk2′]}…} etc where every key value pair is being sent to a separate map function or a different client. This can be unwrapped in the map function to obtain the hashed hex string ‘d077f’ and the list that has to be hashed string wise to check if its first five characters match ‘d077f’ (example).

  • Send output from map to reduce function
  • If a match occurs, send the hashed query string ‘d077f’ (example) and the values that hash to it to reduce function.

  • Send output from reduce function to the parent program
  • If map sends a match, capture the results and aggregate all such results into a single list. Example, {‘d077f’, [‘cat’,’wtf’]} send it to the parent program.

  • Capture reduce functions output
  • Once the parent function receives data from the reduce function the data can be displayed.

Program : 

import hashlib
import string
import itertools
import sys
import mincemeat

inputx = sys.argv[1]
deadlist=[]
deadlist1=[]
deadlist2=[] #Final List
deadlist1string = []
deadlist2string = []
print "Attacking %s..."%sys.argv[1]
m = range(0,10)
for num in m:
	deadlist1string.append(str(num))		
for char in list(string.lowercase):
	deadlist1string.append(char)
for char in deadlist1string:
	for inchar in deadlist1string:
		#First two chars
		deadlist1.append(char)
		deadlist1.append(inchar)
		deadlist.append(''.join(deadlist1))
		deadlist1=[]

#second two chars
for stringx in deadlist:
	deadlist2string.append(stringx)
	for stringx2 in deadlist:
		deadlist2.append(stringx+stringx2)

length3char = len(deadlist2)/(36)
listFor3Digits = deadlist2[:length3char]

#print listFor3Digits
for stringx in listFor3Digits:
	singlestring = stringx
	deadlist2.append(''.join(list(singlestring)[-3:]))
deadlist2+=deadlist2string+deadlist1string

'''listx = []
haha = len(deadlist2)
for i in xrange(1,haha+1):
	if (haha%i == 0):
		listx.append(i)'''

bigdata = []
#print deadlist2[::5188]
for i in xrange(0,333):
		loldict = {}
		loldict[inputx] = deadlist2[(5188*i):(5188*(i+1))]
		bigdata.append(loldict)
		loldict = {}

datasource = dict(enumerate(bigdata))#333*5188 - 333 key value pairs where values are lists
#chunkData = list(itertools.islice(datasource.items(), 1,2)) 


def mapfn(k, v):
	for key in v.keys():
		for w in v[key]:
			if hashlib.md5(w).hexdigest()[:len(key)] == key:
				yield hashlib.md5(w).hexdigest()[:len(key)], w

def reducefn(k, vs):
	result = vs
	return result

s = mincemeat.Server()
s.datasource = datasource
s.mapfn = mapfn
s.reducefn = reducefn

results = s.run_server(password="changeme")
for mm in results:
	found = {}
	found["found"] = results[sys.argv[1]]
	print found
	found = {}