Graph.js – a Graph Algorithms Library in JavaScript

Hello World!
I am writing a blog post after long time. I was quite a busy these days. One day I thought of developing a game in JavaScript. The game design was such that it required graph algorithms implementation in JS. I googled but found nothing suitable for my work. So I though of implementing my own Graph Algorithms Library in JavaScript.This post is in regard to Graph.js ( Github Repo ) – a lite weight JavaScript Graph Algorithms Library. Graph.js is easy to use , change and debug. All the algorithms present in it are efficient in terms of space and time complexity.

Algorithms implemented

  • Depth First Search
  • Breadth First Search
  • Dijkstra – Shortest Distance between two nodes
  • Bellman Ford – Shortest Distance between two nodes.
  • Johnson’s Algorithm for all pair shortest path.
  • Prim’s Algorithm for minimum spanning tree of Undirected complete graph.

How to use

Just include graph.js file in your application .
If you want to build the file from the source code you can just run the make command from the top level directory of the project.

Future Additions to the project

  • Implement more algorithms like clustering , max flow , bipartite matching , random graph generation.
  • Add some test suite ( Preferably QUnit )
  • Add a graph visualizer ( Big Enhancement)
  • Some very good code examples of the usage of library.

Note : You can visit Github Repo for example code and other information. As the library is in nascent stage you can find errors . Feel free to fork , make pull requests and report errors.

What are some great real-life love stories that people have heard?

Answer by Anonymous:

24th may 2013 was the day which changed my views about life.

My room-mate at IIT had fallen in love in the 3rd year of our college to one of the most chirpy, flamboyant girl of our batch. I had no particular reservations for their relationship other than the fact that they were quite opposites my buddy was shy, intro and she altogether was different and I actually felt that she did not love my friend as much as he did. Actually because of her nature I thought she took their relationship very lightly. But whatever be my notion both got along well then I got placed in the US and left while my friend got placed in an MNC in India.

We kept in touch for a few months but like it happens usually we got busy in our lives and could not interact much. I took my parents to USA and my links with India got completely cut. Now 9 years later I am on an business trip to India I thought of meeting my college friends and contacted many through Facebook and likewise. I tried contacting my roomie but met with no responses. When 7-8 of us met I got this news that my roomie died 5 years ago in the Delhi blast at Karol bagh.

I was shocked and couldn’t sink in the fact he was his parents only son and that troubled me more about how those people would be surviving. So I took his address and went to meet them. When I entered the place (a simple yet utterly beautiful one) I found a group of four 2 old men and 2 old women were having their evening snacks and were smiling, laughing and talking. I went on and introduced myself to them. They all greeted me with a lot of love and asked me to join in and served me some tea. I took it and was left with no words on how to ask them about how things have been over the years. So I decided to leave and as I was about to rise the gates opened and my friend’s gf entered (I thought so these two finally married).

She was surprised to see me and welcomed me and asked me to stay over the dinner. After a lot of pestering I agreed and later mustering a lot of courage I asked her so how’s life? to which she smiled and replied good. after a moment silence she continued “we were happy very happy together and were about to get married when it all happened. I was devastated but then I looked at these 4 people (his and her parents) and decided that I would have to move on. I bought a new place, brought in all four together and are now living happily.” She said when I do something for them I know Shubhu smiles and its his happiness that I always want. I asked her how is she managing? She said love is not only about his physical presence in my life…it is about celebrating togetherness and that we do each day with our parents and I know somewhere he is also around here watching our every move keeping us protected. And then she added wish I had his child.

After listening to all this I realized the strength of their love and couldn’t help envying my friend on how lucky he was to have found this girl who is selflessly busy playing her role in their relation without the society bound order of marriage etc. I couldn’t help feeling small at the girl’s immense strength and pure love that their relation stands on. I realized how wrong I was in those days.
She said she has enough memories to last for a lifetime and added:
Log aksar humse humari khushmijaji ka karan pucha karte hai,
Toh hum bhi palat kar keh dete hai,
Huzoor aapki zindagi me yaaden hai,
Par humari to har ek yaad me zindagi rehti hai…

A huge salute to you girl and lots of respect to you.
Indeed life is beautiful its just the matter of ones view to take the challenges.

View Answer on Quora

KillFlash :HTML5

What a newbie thinks about HTML5 ?

HTML5 rumoured as the flash killer is one of the hot topics among the developers. Saying that it is  just a revision(5th) of  the  HTML standard will not serve the power it provided to the developers. I myself being new to web technologies have always thought of making a game . [Disclaimer: I am newbie.]

So we will be making a car racing game.Demo Sourcecode

Language used:

HTML5, JavaScript.

Step 1:

Create a file named index.html and copy the following code into it.


<html>
		<head>
        	<script src="jquery.js"></script>
			<script src="keys1.js"></script>
			<script src="keys2.js"></script>
                        <style>#canvas{border:dashed}</style>
		</head>
		<body>

		</body>
	</html>

In this step we have just created out html file and included the external javascript.

Step 2:
Download and unzip all the files from this folder.

This folder will have three files:

  • jquery.js: Write less do more JavaScript library.
  • keys1.js,keys2.js: These two files are used to handle the key events as handling the key events until now is very dirty.

We are not going into the details of the files keys1.js and keys2.js as it is beyond the scope of this post.If you donot know about jquery you can see the official jquery website or if you want to learn about the jquery you can see the documentation of the jquery or visit w3schools website.

Step 3:

Add the following code into your body tag.

<script>
var CANVAS_WIDTH = 480*2;
var CANVAS_HEIGHT = 280*2;

var canvasElement = $("<canvas width='" + CANVAS_WIDTH +"' height='" + CANVAS_HEIGHT + " '' id='canvas'></canvas>");
var canvas = canvasElement.get(0).getContext("2d");
canvasElement.appendTo('body');
var FPS=30;

var threading=setInterval(function() {

  update();
  draw();
}, 1000/FPS)

function update(){

}

function draw(){

}

</script>

Variables CANVAS_WIDTH CANVAS_HEIGHT are the width and the height of the container where we will be painting everything.
We are creating a canvas with id name =”canvas” and then we are appending it to the body.

The variables FPS represents frames per second.

The setInterval(code,n) is the javascript function used to call the function code after every n milliseconds . So here we are calling the functions draw() and update aftre every 1000/FPS milliseconds. Right now update and draw function are empty.

You can now see your index.html file in the browser. It should look  like this.
pic1
Step:4

Now we will be painting our player on canvas. Just add the following code snippet inside script tag of the body.

var player={

color: "#00A",
  x: 400,
  y: 500,
  width: 40,
  height: 40,
  draw: function() {
    canvas.fillStyle = this.color;
    canvas.fillRect(this.x, this.y, this.width, this.height);
  }

}

Player has the following attributes:

Color: color of the player.

x,y:Coordinates of the current position of the player.

width,height: Height and width of the rectangle.

draw: a function to draw the player on the canvas.

Update the draw function of the step:3.

function draw(){
	 canvas.clearRect(0, 0, CANVAS_WIDTH, CANVAS_HEIGHT);
	 player.draw();
	 }

Again open the index.html file in the browser. It should appear like this. pic2 Step:5 As we have to move our player with the arrow keys so now we will add the event listeners. Just update the function update() of step2.

function update() {

  if (keydown.left) {
    player.x -= 10;
	if(player.x<=0){
		player.x=0;
	}
  }

  if (keydown.right) {
    player.x += 10;
	if(player.x>=CANVAS_WIDTH-32){player.x=CANVAS_WIDTH-32;
	}
  }

}

Whenever the left arrow key is pressed we are decreasing the value of x by 10.And whenever right arrow key is pressed we are increasing the value of x by 10. Now again open your index.html. Your player will now move with your fingers.

Step:6

Now we will be adding the enemy cars in our game. Just add the following code inside the script tag of the body.

var enemy = {

	color: "#000",
	x:480,
	y:10,
	width:32,
	height:32,
	speed:10,
	draw:function(){
	  canvas.fillStyle = this.color;
    canvas.fillRect(this.x, this.y, this.width, this.height);

	},
	 update:	function(){

this.y +=this.speed;
if(this.y>=320*2){
this.x=(Math.random()*960)%960;
		this.y=10;
}
	}
	};

Enemy has the following attributes:

Color: color of the enemy.

x,y:Coordinates of the current position of the enemy.

width,height: Height and width of the rectangle.

draw: a function to draw the enemy on the canvas.

update:a function to update the position of the enemy.

and now update the draw and update functions.

add enemy.update(); in update function.
add enemy.draw(); in draw function.

Open your index.html in the browser.
Now we have to check the collision of the enemy car and the player car. 

Step:7
Just add the following code in the script tag inside the body.
function collision(a, b) {
  return a.x < b.x + b.width &&
         a.x + a.width > b.x &&
         a.y < b.y + b.height &&
         a.y + a.height > b.y;

And then update the draw function.

 
function draw(){
	 canvas.clearRect(0, 0, CANVAS_WIDTH, CANVAS_HEIGHT);
	 if(collision(enemy,player)==true){
clearInterval(threading);
canvas.font='20pt Calibri';
canvas.fillText("Game Over Press F5 ",600,500);
 }
	 player.draw();
	 enemy.draw();
}

Now play

XOR Properties

XOR also known as Exclusive OR  is a logical operation operates on two operands which results in true only if one of the operand has a value true .

In Java,C++,C,C#  it is represented by ^.

In computer Science it is often used for bitwise operations.

               010  XOR 110 =100

               001 XOR 000=001

               111 XOR 111=000

               1010 XOR 1111 = 0101 

There are certain properties of XOR which accounts for its numerous uses.  ( I came to know some of them when I was trying to solve a problem in codechef. )

  • XOR operation is Commutative . A^B=B^A
  • XOR operation is Associative . (A^B)^C=A^(B^C)
  • XOR ing of same number is zero. A^A=0
  • XOR has zero(0) as the identity element. A^0=A

Here are some of the problems where XOR minimizes our effort.

  1. Swapping the numbers.
  2. Finding the number in the list which has odd parity.

1. Swapping

Swapping the numbers is very easy . There are many ways to do this

Method 1: 

int x=10,y=5,temp;
temp=x; // temp=10
x=y; // x=5
y=temp;  // y=10

Method 2:

int x=10,y=5;
x=x+y;   // x=15
y=x-y;   // y=10
x=x-y;  // x=5;

Method 3( Using XOR):

int x=10,y=5;
y=x^y; // 15
x=x^y; // 5(=y)
y=y^x;  // 10(=x)

How is it happening? and Why?

Recall the properties of XOR-

Merge  steps : y=y^x and x=x^y  as x=x^(y^x)

OR


x=x^(x^y) ; // ( As XOR is commutative)

OR


x=(x^x)^y; //( As XOR is associative)

OR


x=0^y=y; //(As A XOR 0=A)

Similarly


y=0^x=x;

2.  Finding the numbers having odd parity.

Example:

There is an array which contains 2n+1 elements in which there are n numbers having duplicates. Only one element is there which which is not paired. How we can find  that element ?

Method 1:

Count the occurrence of every (distinct ) element . If for any element count is 1 ,that is the required element.

Time Complexity- O(n^2);

Can we do better?

Ya, of course.

Method 2:


int result=array[1];  //assuming  array is 1 based

for(int i=2;i<=array.length;i++)

result=result^array[i];

result contains the required element.

If you follow the Use of XOR in Swapping  numbers  then you can easily understand why it is happening that result contains the required element.

Happy Coding!!! :)

Something about Java

Introduction

With the advent of technical Civilization, where competition is the only survival maxim, JAVA is much ahead than its counterpart technologies. Its flexibility is its power and ‘inheritance of legacy’ is buzzword among techno-savvy.

JAVA and C++ have much in common and indirectly depends on C.Java is a hot property of Sun Microsystem, thanks to its godfathers such as James Gosling,Patrick Naughton, Chris Warth, Ed Frank and Mike Sheridan.?

Advantages of JAVA

JAVA offers a number of advantages to developers.

  • Java is simple: Java was designed to be easy to use and is therefore easy to write, compile, debug, and learn than other programming languages.The reason that why Java is much simpler than C++ is because Java uses automatic memory allocation and garbage collection where else C++ requires the programmer to allocate memory and to collect garbage.
  • Java is object-oriented: Java is object-oriented because programming in Java is centered on creating objects, manipulating objects,and making objects work together. This allows you to create modular programs and reusable code.
  • Java is platform-independent: One of the most significant advantages of Java is its ability to move easily from one computer system to another.The ability to run the same program on many different systems is crucial to World Wide Web software, and Java succeeds at this by being platform-independent at both the source and binary levels.
  • Java is distributed: Distributed computing involves several computers on a network working together. Java is designed to make distributed computing easy with the networking capability that is inherently integrated into it. Writing network programs in Java is like sending and receiving data to and from a file.
  • Java is interpreted: An interpreter is needed in order to run Java programs. The programs are compiled into Java Virtual Machine code called bytecode. The bytecode is machine independent and is able to run on any machine that has a Java interpreter. With Java, the program need only be compiled once, and the bytecode generated by the Java compiler can run on any platform.
  • Java is secure: Java is one of the first programming languages to consider security as part of its design. The Java language, compiler, interpreter, and runtime environment were each developed with security in mind.
  • Java is robust: Robust means reliable and no programming language can really assure reliability. Java puts a lot of emphasis on early checking for possible errors, as Java compilers are able to detect many problems that would first show up during execution time in other languages.
  • Java is multithreaded: Multithreaded is the capability for a program to perform several tasks simultaneously within a program. In Java, multithreaded programming has been smoothly integrated into it, while in other languages, operating system-specific procedures have to be called in order to enable multithreading. Multithreading is a necessity in visual and network programming.

Disadvantages of JAVA

  • Performance: Java can be perceived as significantly slower and more memory-consuming than natively compiled languages such as C or C++.
  • Look and feel: The default look and feel of GUI applications written in Java using the Swing toolkit is very different from native applications. It is possible to specify a different look and feel through the pluggable look and feel system of Swing.
  • Single-paradigm language: Java is predominantly a single-paradigm language. However, with the addition of static imports in Java 5.0 the procedural paradigm is better accommodated than in earlier versions of Java.


Difference between Java And C++

Why java is slow

The Real World

The moment you start using objects in your program, Java looses the potential
for optimization. This section lists some of the reasons why.

1. All Objects are Allocated on the Heap

Java only allocates primitive data types like int and double and object
references on the stack. All objects are allocated on the heap.

For large objects which usually have identity semantics, this is not a handicap.
C++ programmers will also allocate these objects on the heap.
However, for small objects with value semantics, this is a major performance killer.

What small objects? For me these are iterators. I use a lot of them in my designs.
Someone else may use complex numbers. A 3D programmer may use a
vector or a point class. People dealing with time series data will use a time class.
Anybody using these will definitely hate trading a zero-time stack
allocation for a constant-time heap allocation. Put that in a loop and that becomes
O (n) vs. zero. Add another loop and you get O (n^2) vs. again, zero.

2. Lots of Casts

With the advent of templates, good C++ programmers have been able to avoid casts
almost completely in high-level programs. Unfortunately, Java doesn’t have templates,
so Java code is typically full of casts.

What does that mean for performance? Well, all casts in Java are dynamic casts,
which are expensive. How expensive? Consider how you would implement a dynamic cast:

The fastest thing you could do is assign a number to each class and then have a
matrix that tells if any two classes are related, and if they are, what is the
offset that needs to be added to the pointer in order to make the cast.
In that case, the pseudo-code for the cast would look something like this:

DestinationClass makeCast (Object o, Class destinationClass) {
Class sourceClass = o.getClass (); // JIT compile-time
int sourceClassId = sourceClass.getId (); // JIT compile-time

int destinationId = destinationClass.getId ();

int offset = ourTable [sourceClassId][destinationClassId];

if (offset != ILLEGAL_OFFSET_VALUE) {
return ;
}
else {
throw new IllegalCastException ();
}
}
Quite a lot of code, this little cast! And this here is a rosy picture
-using a matrix to represent class relationships takes up a lot of memory and no
sane compiler out there would do that. Instead, they will either
use a map or walk the inheritance hierarchy – both of which will slow things down even further.

3. Increased Memory Use

Java programs use about double the memory of comparable C++ programs
to store the data. There are three reasons for this:

Programs that utilize automatic garbage collection typically use
about 50% more memory that programs that do manual memory management.
Many of the objects that would be allocated on stack in C++ will
be allocated on the heap in Java.
Java objects will be larger, due to all objects having a virtual table
plus support for synchronization primitives.
A larger memory footprint increases the probability that parts of the
program will be swapped out to the disk. And swap file usage kills the
speed like nothing else.

4. Lack of Control over Details

Java was intentionally designed to be a simple language. Many of the
features available in C++ that give the programmer control over details were
intentionally stripped away.

For example, in C++ one can implement schemes that improve the locality
of reference. Or allocate and free many objects at once. Or play pointer
tricks to make member access faster. Etc.

None of these schemes are available in Java.

5. No High-Level Optimizations

Programmers deal with high-level concepts. Unlike them, compilers deal
exclusively with low-level ones. To a programmer, a class named Matrix
represents a different high-level concept from a class named Vector.
To a compiler, those names are only entries in the symbol table.
What it cares about are the functions that those classes contain,
and the statements inside those functions.

Now think about this: say you implement the function exp (double x, double y)
that raises x to the exponent y. Can a compiler,
just by looking at the statements in that function, figure out that exp (exp (x, 2), 0.5)
can be optimized by simply replacing it with x? Of course not!

All the optimizations that a compiler can do are done at the statement level,
and they are built into the compiler.
So although the programmer might know that two functions are symmetric and
cancel each other now, or that the order of some function calls is irrelevant
in some place,
unless the compiler can figure it out by looking at the statements,
the optimization will not be done.

So, if a high-level optimization is to be done, there has to be a way
for the programmer to specify the high-level optimization rules for the compiler.

No popular programming language/system does this today. At least not
in the totally open sense, like what the Microsoft’s Intentional
Programming project promises.
However, in C++ you can do template metaprogramming to implement
optimizations that deal with high-level objects. Temporary elimination,
partial evaluation,
symmetric function call removal and other optimizations can be implemented
using templates. Of course, not all high-level optimizations can be done this way.
And implementing some of these things can be cumbersome. But a lot can be done,
and people have implemented some snazzy libraries using these techniques.

Unfortunately, Java doesn’t have any metaprogramming facilities, and thus high-level
optimizations are not possible in Java.

So…

Java, with the current language features, will never be as fast as C++. This pretty much means that it’s not a sensible choice for high-performance software and
the highly competitive COTS arena. But its small learning curve, its forgiveness, and its large standard library make it a good choice for some small and
medium-sized in-house and custom-built software.

Codechef : Prime Generator

Codechef Experience.

It is a medium scaled problem in Codechef. The task was to generate all prime numbers between two given numbers(M and N).

Constraints were N<=10^9  and N-M<=10^4.  Time:2 sec

Easy Part: We all know how we can tell whether any number is prime or not. By definition prime numbers are those numbers which have exactly 2 factors 1 and the number itself. 

There are many approaches to solve this problem.

Approach 1: We start with M and check whether it is divisible by any number between 2 and M-1. We do it until M==N.

Algo:

  1. read M,N
  2. if(m<=2) print 2 do m=m+1
  3. i=2
  4. check=( M%i)
  5. if(check ==0)   do  M=M+1 up-to(M<= N)  and   jump to step 3
  6. else do i=i+1  up-to (i<M) and  jump to step 4
  7. if(i==m) print M else M=M+1 up-to(M<=N) and jump to step 3

Time Complexity: (From wiki)

primes          approach
up to           takes

100             .00100 sec
1000            .02800 sec
10000           1.6980 sec
100000          130.44 sec
1000000         10732  sec

As this algo is taking bruteforce approach so it is impossible to solve the asked problem within the specified time.

Even if you try to make changes like don’t check an even number  ,increase i upto sqrt(i),and check primality of any number with only previous prime numbers,then also time complexity is very high.

Approach2:

Sieve of Eratosthenes 

It is a very standard approach and very fast . This algorithm was created by a Greek mathematician by the name of Eratosthenes.

Algo:

Simply make a list of consecutive numbers from 2 up to the number n. Now, take each number from the front of the list (first 2, then 3 and so on) and remove the multiples of each of these numbers from the rest of the list starting from the square of the number.  At the end of this procedure, all remaining numbers are prime.

The above picture(taken from the wiki) is showing the method to find the prime numbers upto 120.

So in this specific problem what i did is the following.

I took a Boolean array of size 40000 and initialize the with false. I start with i=2 and initialize the value at index 2*i with true.

then I increase i by 2 again and    initialize the value at index i with true.

Then do same thing with i=3,i=5,i=7… increasing every time  i with 3,5,7.. respectively.

Then doing such thing upto i=srt( 40000).If the value at any index  is false then that index is prime otherwise false.

When any number in the range [M,N]<=40000 i can check in O(1) time. If that number is greater than  40000 then i start with the index=2 and do the primality testing upto sqrt(any number) .

When i submit my solution I realized that this algorithm worked out to be very efficient.Why? Because  I saw this!!!!. :)

Nested-Inner class in java

It is possible to define a class within another class.
The scope of the nested class is within the enclosing class.
There are two type of nested classes in Java.
The nested classes which are static are simply called the Nested classes
while the non-static ones are called Inner classes.
Example of Inner Classes.

class outer_class{
public static void main(String args[]){
outer_class outer_object=new outer_class();
}

inner_class inner_object=new inner_class();
int ffff=inner_object.z;

private int x;
public int y;
class inner_class{
void fn(){
x=10;
y=9;
}
private int z;
}

}

In inner classes even the private members of the enclosing class are
directly accessible to the enclosed class.And also the private members
of the enclosed class is accessable through the object of the enclosed class
in the enclosing class.
Note:Inner classes cannot have static members. Static declarations are
for top-level entities,or for the class as a whole, not an instance.
And also we cannot declare any static variable in any function.
Example of Static Classes.

class outer_class{

static class inner_class{

}

}

As it is the static class, we cannot access the members of the outer class directly.

So we have to access them using the object.

Note:There is no such modifier static for the class which is not enclosed
in another class

class dev{
public static void main(String args[])
{
deven.fn();//non-static variable this cannot be referenced
//from the static context
}
}

static class deven{ //Modifier static not allowed here

void fn(){
System.out.println("Deven");
}
}