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.

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!!! 🙂

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!!!!. 🙂