The first evaluation is almost due, and I guess I have successfully achieved the goals set till now. I had not blogged about GSoc project for quite a while now, so here are the overall technical details.

 

The basic overview of Time Dependent Shortest Path (TDSP) Algorithm is as follows:

1. The time dependent data will be queried from postgres database.
We assume we have following database tables:

1. Ways: (On lines of the one in pgrouting-workshop)
* gid
* source
* target
* name
* the_geom
* static_length (In case time dependent routing is not used)
* any other attributes

2. TimeDepCosts
* gid
* start_time
* end_time
* travel_time

If only static shortest path query is made, then only table 1 is required. If time-dependent shortest path query is made, table 1 and 2 will be used.

Time Dependent SQL Query prototype:

CREATE OR REPLACE FUNCTION time_dependent_shortest_path
(
sql text,
source_id integer,
target_id integer,
directed boolean,
has_reverse_cost boolean,
time_dep_sql text,
query_start_time integer
)
RETURNS SETOF path_result AS ‘$libdir/librouting_tdsp’
LANGUAGE ‘C’ IMMUTABLE STRICT;

2. The postgresql Server Programming Interface is used to retrieve data from database.
The time_dependent_shortest_path query is internally calls the dynamically loaded objects which are postgresql C functions. It is defined in tdsp.h [3].
The Server Programming Interface (SPI) is used to retrieve tuples from ways table into array of edge_columns, defined in tdsp.h.  Similarly tuples from time_dep_costs table are retrieved into array of weight_map_elements.
These are then passed on to the tdsp_wrapper() function which has following prototype:

int tdsp_wrapper
(
edge_columns_t *edges,
unsigned int edge_count,
weight_map_element_t *weight_map_elements,
int weight_map_element_count,
int start_vertex,
int end_vertex,
bool directed,
bool has_reverse_cost,
path_element_t **path,
int *path_count,
char **err_msg
);
The tdsp_wrapper internally calls the tdsp() function, details are given in next section.

 Core function Assumption:
The core function assumes that the query_start_time is 0 and all the start_times in weight map are offset from the query_start_time. This makes the core function independent of the time units and data formats of the input data.
To use the core function with any input data, we need to write wrapper functions that will convert the time_dep_cost entries into weight map entries which follow the above convention. This greatly simplifies the working of the core algorithm and makes the design very flexible and robust.

 3. The core time dependent dijkstra algorithm.
The core algorithm is referred from [1].

The input to a time-dependent shortest path problem is a directed network G = (N,A) and an arrival time function aij(t) for every arc (i, j) ∈ A. The quantity aij(t) gives the time of arrival at j if one departs from i at time t. It is assumed that aij(t) ≥ t. The function aij(t)−t gives the travel time along arc (i, j) if one departs at time t.

If aij(t) is non-decreasing for all (i, j) ∈ A, we say that G is a FIFO network, since in this case commodities will travel through arcs in a First-In-First-Out manner. If this is not the case the problem will be NP Complete. We will therefore assume that G is a FIFO network.

Let P(s, d) denote the set of paths between a source node s and a destination node d. The function EAsd(t) = min{ap(t) : p ∈P(s, d)} gives the earliest arrival time at node d if one leaves s at time t
The pseudo-code for solving the Single source – destination query is as follows:

Initialization:

For all i ∈ N{s}
EAsi(t)←∞

EAss(t)←t

S ←N

Main Loop:

While S != ∅

Select i ∈ S minimizing EAsi(t) S ←S{i}

For all j such that (i, j) ∈ A

EAsj(t) ← min{EAsj(t), aij(EAsi(t))}

The design overview is as follows:

 Edge Wrapper
The edges retrieved from the ways table are fed to the edge wrapper. The edge wrapper provides wrapper functions that help answer queries like –
Given an edge_id, what are the source and target vertex ids.
Given source and target vertex ids, what is the edge id.

Weight Map
The weight map elements retrieved from the time_dep_costs table are fed to the Weight Map. It answers queries like –
Given an edge_id and start_time, what is the travel time for the edge.

Binary Heap
It is used as priority queue while performing time dependent dijkstra search. It provides following functionality –
Insert – Add a vertex to the heap.
Decrease_Key – Given a vertex_id and delta value, decrease the key of that vertex by delta.
Delete_min – Delete and return the vertex with minimum key value and rebalance the heap.

 Boost Adjecency List Graph
It is the graph constructed from the edges retrieved from ways table. It is used to examine the out_edges from a vertex while running the time dependent dijkstra algorithm. It offers many flexible options. For more details refer the boost documentation [2].

 4. The result:
The result is returned in form of path_elements which is similar to the result of the shortest_path() query of the original pgRouting dijkstra algorithm implementation.

 5. References
[1] B Dean. Shortest Paths in FIFO Time-Dependent Networks : Theory and Algorithms, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.94.6765
[2] Boost Adjecency List. http://www.boost.org/doc/libs/1_36_0/libs/graph/doc/adjacency_list.html

Advertisements

Hey!

Its 3rd week of the coding phase of GSoc 2011 and my project seems to be well ahead of its schedule 😉  As per initial proposal, aim till June 15 was to code and test the core TDSP algorithm.

Current Progress:
The design details can be seen here.
* According to new plan, we are not using Boost Priority Queues for heap operations during dijkstra search.
Instead, I have implemented a binary heap that will provide the functionality.
I have also coded the data structures that would be required for the core – time dependent dijkstra implementation.
The initial working draft of algorithm is also ready.
Please find the source file here.
I have also organised the code into different header files – binary_heap.h, weight_map.h, edge_wrapper.h.
Added a boost – dijkstra test function which calls boost::dijkstra_shortest_paths() so as to verify the result.
Testing
I wrote a graph generator which can generate random graphs according to the parameters specified:
– number of vertices
– maximum outdegree of a vertex (I keep this 6 or 8 , since 6 is degree limit for planar graphs)
– Number of time windows and the range of time windows.
So, to see if the result returned by tdsp-dijkstra function is correct, I generated random graphs with time window 1, which starts from 0, meaning that the same travel time will be there for any given start time. This is basically static dijkstra.
I compared the results returned by tdsp-dijkstra and boost-dijkstra and I am getting same output. Tried for graphs with 20,100,500,1000 nodes with max outdegree 8. (generating graphs with nodes more than that was taking too much time and my CPU was getting overworked!)
Only difference in boost-output and tdsp-output comes when there are more than one shortest paths of same length. The there might be difference of predecessors. I guess that is because of different implementations of priority queue (binary_heap in my case).
I have updated the code in github gsoc-tdsp branch.
I have updated the weekly progress reports at the TDSP home page.
Hope the upcoming weeks are similarly productive!  😉

As mentioned in my last post, I will be doing Google Summer of code project for pgRouting. Here, I will give an overview of the algorithm implementation.

pgRouting is a C++ library that provides routing functionality for postgres. I will be extending it so that it can support time dependent routing. An abstract overview of the idea is:


  • The time dependent data will be queried from postgres database.
  • Using the information, a graph will be generated
  • The core time dependent dijkstra algorithm will be run on the graph
  • The result will be returned

The input to a time-dependent shortest path problem is a directed network G = (N,A) and an arrival time function aij(t) for every arc  (i, j) ∈ A. The quantity aij(t) gives the time of arrival at j if one departs from i at time t. It is assumed that aij(t) ≥ t.
The function aij(t)−t gives the travel time along arc (i, j) if one departs at time t.

If aij(t) is non-decreasing for all (i, j) ∈ A, we say that G is a FIFO network, since in this case commodities will travel through arcs in a First-In-First-Out manner. If this is not the case the problem will be NP Complete. We will therefore assume that G is a FIFO network.

Let P(s, d) denote the set of paths between a source node s and a destination node d. The function EAsd(t) = min{ap(t) : p ∈P(s, d)} gives the earliest arrival time at node d if one leaves s at time t

The pseudo-code for solving the Single source – destination query is as follows:

Initialization:

For all i ∈ N\{s} : EAsi(t)←∞
EAss(t)←t
S ←N

Main Loop:

While S != ∅
Select i ∈ S minimizing EAsi(t) S ←S\{i}
For all j such that (i, j) ∈ A
EAsj(t)←min{EAsj(t), aij(EAsi(t))}

This will be basically a SQL C function for postgres. More updates to follow…

Hey! Been long time since I blogged. Just finished with my exams today.

And guess what, GSoc 2011 results are out, and my project proposal for implementation of Time Dependent Shortest Path Algorithm for pgRouting has been accepted! 🙂

Short description of the project:

This project aims at extending the pgRouting library to support time-dependent shortest path routing where the edge weights are function of time and other parameters. Unlike static scenario, where the edge weights do not change here, we assume that the weights change according to time. So, while traversing any edge, the algorithm must consider the cost of edge at that instant of time. Thus the algorithm will give the path which has least arrival time from source to destination.

It sure promises to be one exciting summer! Best thing is that the project closely overlaps with the research topic I am working on currently as part of my thesis. I will keep updating on the project of the project through-out summer. So Stay tuned!

Gate 2011 cutoff queries

February 16, 2011

Hi guys,

Gate 2011 finished off 3 days ago, and it seems a the number of people aspiring for IITs this year is HUGE!  Since the answer keys have been put up by various coaching institutes, people have a fair idea about ther GATE marks.

To my surprise, there has been unexpected traffic to my blog post  IITs and Gate Cutoff Story 2010 written way back in May 2010!  🙂 (More than 1000 hits in last 4 days.. Seriously! Nobody used to wonder here before! :P)

I am really happy to see the enthusiasm among the students to know what chance they have for getting admissions into the top Colleges in India. But I would still tell all you guys to wait before the actual GATE result is out, (which will not be until 2nd week of March!) before you really start thinking about where to take admission.

If you still have any doubts, I will be happy to answer your queries to the best of my knowledge. Please note that I am from CSE department, and dont know much about cut-offs of other departments. You are welcome to post your queries here or at the above mentioned blog post as comments!

Best Luck! 🙂

In IIT Kanpur, we call hostels – Halls of Residence. I live in Hall-4 and it is one of the most beautiful places where you can wish to live. The following quote taken directly from the new Hall-4 website.

Almost centrally located amongst the student hostels of IIT Kanpur, Hall 4 enjoys a unique repute of having most of the distinguished alumni of the institute as its ex-residents. The spirit of Hall 4 lies in its policy of social activism, intellectual contribution and the diverse tapestry of cultural fragrance. Said to possess some of the most forthright group of students, the Hall has in the past taken major social initiatives and proposed solutions to the institute regarding various issues including the proposal of a new mess model. The Hall is proud to have the student gymkhana constitution being modelled after its own constitution.

The hustle and bustle that goes on in the Hall quad goes on to late nights and sometimes even very early mornings, accompanied by sips of tea and coffee in the Hall 4 canteen. A very different and focused group of students carry on playing shots at the Billiard room, which is the only such facility in any of the student hostels of the institute. While the residents of the Hall have taken patents for their research work and contribute to various symposiums, conferences and journals in academics, an interdisciplinary camaraderie is also seen amongst the residents of the hall.

Things which I like here?

  • Mess Food – It is awesome. Before coming here I had heard stories of people describing how ugly hostel food is. Believe me, I love it here. (Specially Friday night). Have a look into the Hall 4 Mess menu. (mouth watering :P)
  • Facilities – You name any sport and you can play it here. Facilities are really awesome. Since it is the oldest hostel in IITK, it does not have the modern spacious feel to it as some of the newer halls do, but still I like it!
  • Canteen – If you ever get bored of mess food, you have the canteen! Beautifully located near the lawn, it is the perfect place to have the “DPs” after midnight! All the birthday celebrations and the GPLs are done here. Special mention to Ranjit who brings the DP and the new “Rahul”. 😛

 

PS: I will duly remove the above quotes if I am not allowed to copy the content here. Please mention it as a comment.

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!