Another reason to love Neo4J

For one of the projects where Neo4J is being used, I have been working on implementing K-Shortest Path algorithm using Yen’s loopless improvised algorithm.

Now an issue in the algorithm is that; Say  in computing top 4 shortest path, what the algorithm does is that it when computing the 2nd shortest path; It removes arcs of the 1st shortest path from the graph. And so removes the 2nd while computing 3rd shortest path and so on. And later in the end, it adds back all the removed arcs.

The problem now is that when one thread is computing a kth shortest path, other threads cannot use the algorithm as the graph is not in its complete shape. i.e. because first thread in the computation has temporarily removed some arcs, and the same graph cannot be used for any other purpose till those arcs are again added. Hence multiple instances of the algorithm cannot be used in parallel. One can solve the problem by  instead of removing them, have a flag in the relationship for a particular par of nodes. Flag will be cleared once the computation is over. But when running many instances in parallel there shall be many  such key value pairs in the relationships.There is an extra load in teh end to clear the flags.

Now this would have been a problem while using any other graph library. But the transaction model in Neo4J solves the above issue.

Here is the crazy part which I am unsure of if at all its a good practice:
I will have the code inside a transaction, but not let the transaction succeed. i.e. I will implement the algorithm and remove the respective arcs in the process, when I have the desired output, I will call the transaction a failure. hence the arcs are never removed and the same instance of the algorithm can be used. Further there will be no need to later add those arcs as in reality they were never removed.

This is so cool. Though there is another issue with it as pointed out by Mattias Persson of NeoTechnologies-

The only problem I  see here is that removing relationships will grab write locks which will be held throughout the transaction and prevent any other shortest path algo to remove those relationships as long as the transaction is alive.

How big this issue is, I do not know. But if carefully crafted should behave well. In any case its way better than removing the arcs and halting all the other computations on the graph.

More on it here.

 

New Development:
Another reason why I use N3o4J is to reduce the development time.  Reason being had I used some graph service at expense of memory, rebuilding the graph even to test small things takes a lot of time. With Neo4J I dont have to worry about that. Though with JUNG the problem can be solved by using a custom class loader and using the test’ as plugins hence saving time. But all this requires effort.