<div dir="ltr"><div><div>Thanks Steve ,I am familar with astar ,It uses a heuristic to guide itself to the destination, there was huge focus on it in our game theory course.<br><br></div>Although do point out the advantages it has in real life road network and its importance to my proposal.<br>
<br><br></div><br></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Thu, Apr 25, 2013 at 7:43 AM, Stephen Woodbridge <span dir="ltr"><<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi Mukul,<br>
<br>
This is a good write up. It largely mirrors out discussion. One thing that needs to change in this is that dijkstra should be replaced with astar.<br>
<br>
Are you familiar with how these are different?<br>
<a href="http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html" target="_blank">http://theory.stanford.edu/~<u></u>amitp/GameProgramming/<u></u>AStarComparison.html</a><br>
<br>
Do you see why? and specifically why it matter for this project?<br>
<br>
-Steve<br>
<br>
On 4/24/2013 9:10 PM, Mukul priya wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
***Name*:Mukul Priya<br>
<br>
*Country:*India<br>
<br>
*School and degree*: International Institute Of Information<div class="im"><br>
Technology-Hyderabad ,<br>
<br>
B.Tech + Masters in computer Science And<br>
Engineering<br>
<br></div>
*Email*:<a href="mailto:mukul2047@gmail.com" target="_blank">mukul2047@gmail.com</a> <mailto:<a href="mailto:mukul2047@gmail.com" target="_blank">mukul2047@gmail.com</a>><br>
<br>
*Phone*:+91 9885991061<br>
<br>
*OSGeo project(s*):pgRouting<br>
<br>
*Title:* A partitioned approach to on demand increment graph assembly<br>
for pgRouting.<br>
<br>
*Describe your idea*<br>
*1. Introduction*<div class="im"><br>
<br>
pgRouting has been working towards providing routing<br>
functionality on a PostGis/PostgreSql Geo spatial<br>
<br>
database. It already has support for shortest path algorithm like<br>
astar ,dijkstra , tdsp and trsp .But for a very<br>
<br>
large network, routing becomes time consuming. Network partitioning<br>
is one such way which can prove to<br>
<br>
be helpful in improving the overall time efficiency of routing<br>
querries. The main idea here is to first partition<br>
<br>
the whole network using a Quad tree approach and when the shortest<br>
path is computed these partitions are<br>
<br>
loaded on demand. hence , there is an on demand incremental graph<br>
generation.<br>
<br>
<br>
The project aims at designing and implementing a Shortest Path<br>
algorithm on an on demand incremental<br>
<br>
Graph using a network partitioning approach.<br>
<br>
<br>
<br></div>
*2. Background*<div class="im"><br>
<br>
Considering the present status where pgRouting has support for<br>
shortest path algorithm like astar etc.<br>
<br>
Looking at their implementation details we can observe that the graph<br>
is configured dynamically for all<br>
<br>
of them before computation.My proposal will also be on the same track<br>
and for very large networks<br>
<br>
where the distance between source and destination can be very large ,<br>
the response time will be<br>
<br>
significantly lesser and memory wise too it will be lot more<br>
efficient. Presently they don't use any partitioning<br>
<br>
approach so it will prove to be a good addition to their support for<br>
shortest past algorithms.<br>
<br>
<br></div>
*3. The idea*<div class="im"><br>
<br>
There are two major components of my idea .<br>
<br>
<br></div>
*<br>
<br>
*Network Partitioning*<div class="im"><br>
<br>
For this part we can use a quad tree approach. Say , we start<br>
with a square and a condition like maximum<br>
<br>
number of nodes that can reside in a square . if the number of<br>
nodes in the square is greater than the max<br>
<br>
condition we further quarter it into four squares and allot the<br>
nodes appropriately to each of them.All these<br>
<br>
squares can be called grids and they all will be addressed<br>
uniquely using a grid cell number .Each node<br>
<br>
will be assigned a grid cell number based on the grid they are<br>
lying inside.<br>
<br>
<br>
We will have data structures to address edges as they can<br>
remain contained in either one grid cell<br>
<br>
or span across a number of grid cells.the idea is to first flag<br>
such edges and store the grid cell numbers<br>
<br>
of the grids that the edge crosses/intersects.<br>
<br>
<br></div>
*<br>
<br>
*On demand graph generation and Routing.*<div><div class="h5"><br>
<br>
The idea here is to first identify the grid cell<br>
initially and then fetch the edges that are associated with<br>
<br>
that grid. These are the edges that will get appended to the<br>
present graph and the graph will keep growing<br>
<br>
dynamically this way. we will have appropriate database tables<br>
addressing the above issue such that<br>
<br>
we are able to fetch the required edges quickly using a<br>
database querry.<br>
<br>
<br>
The implementation details for the above are :<br>
<br>
we will first partition the whole graph using the quad tree<br>
approach and each node/vertex will be assigned<br>
<br>
a grid cell number so we can have database table for the<br>
assigned nodes and edges like :<br>
<br>
CREATE TABLE vertex{<br>
<br>
id Node_id \\ unique for each<br>
node.<br>
<br>
cell grid_cell_number; \\ the grid in which the<br>
node lies.<br>
<br>
geometry;<br>
<br>
}<br>
<br>
<br>
CREATE TABLE edge {<br>
<br>
int id ;<br>
<br>
Int node_a;<br>
<br>
int node_b; \\ the connecting nodes<br>
<br>
// we can have other parameters like traversal cost and return<br>
cost.<br>
<br>
}<br>
<br>
using the tables we can then fetch the edges form edge table<br>
using simple database querry once<br>
<br>
we are provided with the grid cell number very easily.<br>
<br>
In short the summary of the whole idea is :<br>
<br>
<br>
Step1: Fetch the start node , get the related Grid cell number.<br>
<br>
<br>
Step 2: Increment the graph by fetching all the items related to that grid.<br>
<br>
<br>
Step3 : Check for boundary nodes ( this is done while we are<br>
partitioning) or target node .<br>
<br>
Step 4: On hitting a boundary node<br>
<br>
{<br>
<br>
check if the connected grid is loaded and continue if<br>
it is<br>
<br>
or we extend the graph with the new grid and continue<br>
with the routing;<br>
<br>
}<br>
<br>
or On hitting the target Node<br>
<br>
{<br>
<br>
stop;<br>
<br>
}<br>
<br>
<br>
<br></div></div>
*4. Project plan*<div class="im"><br>
<br>
I will have about 12 weeks to implement the project. The tentative<br>
schedule is as follows:<br>
<br>
Before 17th June : Get familiar with the development environment<br>
of pgRouting and test some demos.<br>
<br>
week 1-2: Discuss and Define the various data structures and data<br>
table that will be required.Prepare the<br>
<br>
Overall implementation architecture.<br>
<br>
<br>
week 3-4- Discuss and Implement network partitioning using quad<br>
tree.<br>
<br>
week 5-8 -Start coding for on demand graph generation and routing<br>
using Dijkstra. In between Prepare mid-term<br>
<br>
report.<br>
<br>
<br>
week 9 - Integration with pgrouting .<br>
<br>
week 10-12- Testing and Bug fixing. Draft Final report and<br>
documentation.<br>
<br>
<br></div>
*<br>
5. Future ideas / How can your idea be expanded? *<div class="im"><br>
<br>
<br>
It can be integrated with other shortest path algorithms like<br>
astar etc. which pgrouitng provides.For time dependent<br>
<br>
shortest path computation, it will greatly reduce the updating cost<br>
as we will be updating the cost of only those edges<br>
<br>
that are contained in the grid cells that are loaded.<br>
<br>
In route nearest neigbour querries can also be implemented using<br>
the partitioning approach.Overall we can<br>
<br>
expand this approach to various other algorithms.<br>
<br></div>
*Explain how your SoC task would benefit the OSGeo member project and<br>
more generally the OSGeo Foundation as a whole:*<div class="im"><br>
<br>
The proposed idea will significantly improve the performance of<br>
shortest path finding algorithms.This will have a<br>
<br>
positive effect on the user base of pgRouting. For various software<br>
paltforms or applications that are using this library ,<br>
<br>
the response time will significantly improve.<br>
<br>
*<br>
<br>
Please provide details of general computing experience:<br>
*<br>
<br>
<br>
I generally use ubuntu ( 12.04) for all my academic purposes and windows<br>
7 for entertainment only. I am familiar with Fedora also.<br>
<br>
C++ is the language that i use most ( programming purposes). For<br>
implementing various course projects i have used C++ ,python ,Java and<br>
matlab.<br>
<br>
<br>
I have no experience with hardware. The only experience that i had with<br>
networking was during my computer network course.<br>
<br></div>
*<br>
Please provide details of previous GIS experience:*<div class="im"><br>
<br>
<br>
I am a part of "Lab for Spatial Informatics" which is the only lab in<br>
India devoted to GIS applications and learning. I am familiar with and<br>
have used almost all the open source GIS platforms like Quantum ,<br>
OpenJump, ILwis,Grass. We have our own rendering platform that was<br>
developed by our lab.(LSI viewer)<br>
<br></div>
*Please provide details of any previous involvement with GIS programming<br>
and other software programming:*<div class="im"><br>
<br>
<br>
I am very much familiar with Gdal/OGR as i used it extensively while<br>
implementing an outsourced project of Honeywell<br>
<br>
Technology . I have played a lot with ESRI shape files.<br>
<br></div>
*Please tell us why you are interested in GIS and open source software:*<div class="im"><br>
<br>
<br>
I was very impressed with google earth when it was launched way back in<br>
2004.GIS platforms like quantum and Openjump were introduced to me when<br>
i was in my second year and then i joined Lab for spatial informatics<br>
that is in our college based on my interest in this area.<br>
<br>
<br>
open source platforms provide an opportunity to learn . The best part is<br>
you can always create or develop something that you are interested in<br>
and there are people who will always be there to help you if you are stuck.<br>
<br>
*<br>
<br>
Please tell us why you are interested in working for OSGeo and the<br></div>
software project you have selected:*<div class="im"><br>
<br>
<br>
It will be huge learning experience since i have been using platforms<br>
like Qgis , Gdal ,PostGis etc which come under Osgeo<br>
<br>
<br>
I chose pgrouting because the algorithms that they have implemented are<br>
related to my masters topic and it will be great if i get an insight<br>
about how these were implemented on a much larger scale.<br>
<br></div>
*Please tell us why you are interested in your specific coding project:*<div class="im"><br>
<br>
<br>
Implementing routing algorithms for real world networks is actually very<br>
challenging.its a challenge to come up with good approaches so that the<br>
computation cost and response time is both reduced.<br>
<br></div>
*Would your application contribute to your ongoing studies/degree? If<br>
so, how?*<div class="im"><br>
<br>
I am pursuing my Masters and my topic is closely related to my proposal<br>
. If the results are impressive , i might get a publication in this area.<br>
<br>
<br></div>
*Please explain how you intend to continue being an active member of<br>
your project and/or OSGeo AFTER the summer is over:*<div class="im"><br>
<br>
<br>
I was always interested in open source programming but never knew where<br>
to start . GSOC provides an opportunity for beginners like me to take a<br>
dive in the area open source programming. i have other ideas like<br>
implementing IRNN ( In route nearest neighbour querries) which can be<br>
implemented within pgRouting.I have other intentions like working for<br>
bigger projects like Quantum Gis or Grass.I will be contributing to the<br>
community forum and will always try to improve things.<br>
<br></div>
*Do you understand this is a serious commitment, equivalent to a<br>
full-time paid summer internship or summer job?*<div class="im"><br>
<br>
<br>
Yes, I understand that this is a serious commitment and will try to give<br>
my best and work in a professional manner.<br>
<br>
<br></div>
*Do you have any known time conflicts during the official coding period?<br>
(June 17 to Sept. 27)*<div class="im"><br>
<br>
<br>
No .<br>
<br>
<br>
<br>
<br>
<br>
On Thu, Apr 25, 2013 at 12:47 AM, Stephen Woodbridge<br></div><div class="im">
<<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a> <mailto:<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.<u></u>com</a>>> wrote:<br>
<br>
On 4/24/2013 2:34 PM, Mukul priya wrote:<br>
<br>
Hi Steve and Daniel ,<br>
<br>
I have posted my proposal on Melange Gsoc system. Do have a look<br>
at it.<br>
Waiting for feedback and suggestions.<br>
<br>
<br>
Can you post a link to your proposal? or the text of it here also. I<br>
can never find anything in Melange or I may not have visibility to<br>
it yet as I just applied as a mentor.<br>
<br>
Thanks,<br>
-Steve<br></div>
______________________________<u></u>___________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a> <mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.<u></u>osgeo.org</a>><br>
<a href="http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/__<u></u>mailman/listinfo/pgrouting-dev</a><br>
<<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><u></u>><div class="im"><br>
<br>
<br>
<br>
<br>
______________________________<u></u>_________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><br>
<br>
</div></blockquote><div class="HOEnZb"><div class="h5">
<br>
______________________________<u></u>_________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><br>
</div></div></blockquote></div><br></div>