Graph Library

Well I do know that there are some amazing Open Source Graph Libraries out there, but during the course of the last semester I happened to make one for myself.

It so happened that for quite some time now I have learning a lot about Object oriented Design Patterns (From the book Head First Design Patterns, its an amazing book and do read if you haven’t read Gang of four or this before. Highly highly recommended, already in my list of top 3 books for Java). And due to my unsatisfiable thirst for growth in Concurrency, I thought why not lets design a Graph Library which provides internal synchronization in the library. By internal synchronization I mean a mechanism where one could lock all the access to a node or an edge and do the required processing. JGraphT or Jung for that matter do not provide it.

Further we were suppose to make an ADT for graph’s for the course Data Structures and Algorithms, so I thought finally a perfect opportunity to club my interests with academics (Sadly never used it for academics). But ultimately with all the assignments and tests I couldn’t design it for concurrency, but yes the library does form a basic architecture on which I can build up later.

Salient Feature of GraphS (Yes! I named it GraphS which means Graph with Synchronization) :

  1. Traversal is through nodes rather than by retrieving from indexed list. Hence One can lock the operation on a Node. (More work needed with blocking and non-blocking features)
  2. Follows all the good Design Patterns and guaranteed for Scalability.
  3. Abstract Class Graphs.java  has the basic implementation of a graph. DirectedGraph.java & UnDirectedGraph.java extends it.
  4. API provides 2 shortest path Algorithm Implementations : Dijkshtra’s and Bellman Ford Algorithms
  5. API provides 2 MST Implementations : Krushkal and Prim’s
  6. Well Tested

There is a lot of work which needs to be done:

  1. Complete the synchronization part as explained above
  2. Improve the Documentation.
  3. Implement the GUI component.
  4. Profile it with more than a million nodes and compare it with other Graph libraries.

Somehow couldn’t use it for my course work but hopefully the experience of building it would be handy as for next I would be working on Neo4J which is a Graph Database.

People interested to build it firther, pl write to me at jatin@jatinpuri.com.You can download the source code from github under MIT license.

 

PS: Some problem with my github account, for now you can download it from here.