Warshall’s APSP using BGL

December 19, 2010

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!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: