Warshall’s APSP using BGL

I have been working on pgRouting for past few days, specifically the All Pairs Shortest Path APSP function. pgRouting internally uses Boost Graph Library(BGL) to handle the non-trivial graph related functionality and for APSP, we have decided to use the Warshall’s Algorithm.

The BGL manual gives an example of the Johnson’s APSP implementation, and you need to tweak it a little bit to get the same working for Warshall. The following code will give a quick bite of how you can implement the Warshall’s Algo.

Note: All credits to the BGL manual, I have just modified it to work for Warshall

#include <boost/config.hpp>

#include <iostream>

#include <fstream>
#include <boost/graph/graph_traits.hpp>

#include <boost/graph/adjacency_list.hpp>

#include <boost/graph/floyd_warshall_shortest.hpp>

using namespace boost;
typedef adjacency_list<vecS, vecS, directedS, no_property,property<edge_weight_t, int, property<edge_weight2_t, int> > > Graph;

void static_warshall()

{

const int V = 6;	typedef std::pair<int,int> Edge;
Edge edge_array[ ] =	{ Edge(0,1), Edge(0,2), Edge(0,3), Edge(0,4), Edge(0,5),	Edge(1,2), Edge(1,5), Edge(1,3), Edge(2,4),                             Edge(2,5),	Edge(3,2), Edge(4,3), Edge(4,1), Edge(5,4) };
const int E = sizeof (edge_array)/sizeof (Edge);
int weights[] = { 0, 0, 0, 0, 0, 3, -4, 8, 1, 7, 4, -5, 2, 6 };

Graph g(edge_array, edge_array + E, weights, V);

std::vector<int> d(V, std::numeric_limits<int>::max());	int D[V][V];
floyd_warshall_all_pairs_shortest_paths(g, D, distance_map(&d[0]));

for(int i=0;i<V;i++)

{

for(int j=0;j<V;j++)

{

std::cout<<D[i][j]<<" ";

}

std::cout<<std::endl;

}

}

&nbsp;

I hope I can come up with a working version of APSP for pgRouting some time in future. You can check out the core source code from the git repository I have forked here: https://github.com/jay-mahadeokar/pgrouting

Cheers!

Contribution to pgRouting

Its semester holidays @IIT kanpur and I am enjoying the stay at home! Meanwhile, I have found a really interesting pass-time. The pgRouting project!

I got introduced to pgRouting when I was working at Location Guru, we used to call some routing plsql function of postgres that were implemented using pgRouting, and even then I was fascinated with the things inside it. Now I am getting the chance to get into the inner details and learn a host of other technologies.

Basically, in order to contribute to pgRouting, you need to learn:

• C++ STL and Templates
• Boost Graph Library
• postgreSQL and postGIS basics
• plsql
• cmake

Its amazing how many small things are needed to make a nice tool. That is I guess the power of open-source and collaboration!  I will keep updating the things I explore as I try to put these holidays to some use (though I keep on finding new innovative ways to waste time!). I do need to think on what thesis topic I will work on pretty soon too!

Cheers!

Script and Create windows installers

I had to do some settings and installation stuff for one of the project I was working on, when I came to know about NSIS (Nullable Scriptable Install System)

I have become an instant fan of it…  Ever since I started coding during II Year of Engineering and made my silly softwares and games (using C/C++/Java) , I always wanted to create good looking installers for them. NSIS allows you to write small scripts which specify what files you want to install and where in a very easy manner. You just need to learn the basic syntax of the scripts and you can create your own installers.

And again its free and opensource, which makes things even better!!

Quick Links:

Download NSIS

Learn NSIS Scripting

Sun Studio Blogging Contest 2009

Sun has launched yet another blogging contest, and now its turn of Sun Studio to be the centre of attention.

To Enter, simply:

1. Download Sun Studio.
2. Blog about it
3. Submit your entries!

The prizes are as always excellent. So, get going!  I am not entering this time, but I still savor the easiest 100$ that could have ever made, when I won the Sun Student Reviews contest, back in 2008!

Google Code Jam is back!

Google has announced the – Google Code Jam 2009 – the big daddy of all coding competitions around the world which in google words:

Offers coders from around the world an opportunity to solve complex algorithmic problems under time pressure, using the programming languages and tools of their choice.

The contest will have a qualification round followed by 3 full online rounds, and if you happen to be good enough to pass these rounds, you may just get a chance to visit GOOGLE for the final round at their Mountain View, California headquarters!

And not to mention the hot prizes to be won – Last year alone 80,000$ were awarded over the contest!

The contest registeration  will be opening around mid-August..  So, all you diehard coders, keep your fingers tuned to the keyboard!

Quick Resources:

• Last years problems – just to get a trailor!.
• Google Code Jam Anounce Group.
• Last Year prizes and details