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.

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