[pgrouting-dev] Gsoc 2013

pgRouting pgrouting-dev
1

Hi Steve and Daniel ,

I have posted my proposal on Melange Gsoc system. Do have a look at it.

Waiting for feedback and suggestions.

Thanks

Mukul

2

On 4/24/2013 2:34 PM, Mukul priya wrote:

Hi Steve and Daniel ,

I have posted my proposal on Melange Gsoc system. Do have a look at it.
Waiting for feedback and suggestions.

Can you post a link to your proposal? or the text of it here also. I can never find anything in Melange or I may not have visibility to it yet as I just applied as a mentor.

Thanks,
   -Steve

3

Name:Mukul Priya

**Country:**India

School and degree: International Institute Of Information Technology-Hyderabad ,

B.Tech + Masters in computer Science And Engineering

Email:mukul2047@gmail.com

Phone:+91 9885991061

OSGeo project(s):pgRouting

Title: A partitioned approach to on demand increment graph assembly for pgRouting.

Describe your idea
1. Introduction

pgRouting has been working towards providing routing functionality on a PostGis/PostgreSql Geo spatial

database. It already has support for shortest path algorithm like astar ,dijkstra , tdsp and trsp .But for a very

large network, routing becomes time consuming. Network partitioning is one such way which can prove to

be helpful in improving the overall time efficiency of routing querries. The main idea here is to first partition

the whole network using a Quad tree approach and when the shortest path is computed these partitions are

loaded on demand. hence , there is an on demand incremental graph generation.

The project aims at designing and implementing a Shortest Path algorithm on an on demand incremental

Graph using a network partitioning approach.

2. Background

Considering the present status where pgRouting has support for shortest path algorithm like astar etc.

Looking at their implementation details we can observe that the graph is configured dynamically for all

of them before computation.My proposal will also be on the same track and for very large networks

where the distance between source and destination can be very large , the response time will be

significantly lesser and memory wise too it will be lot more efficient. Presently they don’t use any partitioning

approach so it will prove to be a good addition to their support for shortest past algorithms.

3. The idea

There are two major components of my idea .

  • Network Partitioning

For this part we can use a quad tree approach. Say , we start with a square and a condition like maximum

number of nodes that can reside in a square . if the number of nodes in the square is greater than the max

condition we further quarter it into four squares and allot the nodes appropriately to each of them.All these

squares can be called grids and they all will be addressed uniquely using a grid cell number .Each node

will be assigned a grid cell number based on the grid they are lying inside.

We will have data structures to address edges as they can remain contained in either one grid cell

or span across a number of grid cells.the idea is to first flag such edges and store the grid cell numbers

of the grids that the edge crosses/intersects.

  • On demand graph generation and Routing.

The idea here is to first identify the grid cell initially and then fetch the edges that are associated with

that grid. These are the edges that will get appended to the present graph and the graph will keep growing

dynamically this way. we will have appropriate database tables addressing the above issue such that

we are able to fetch the required edges quickly using a database querry.

The implementation details for the above are :

we will first partition the whole graph using the quad tree approach and each node/vertex will be assigned

a grid cell number so we can have database table for the assigned nodes and edges like :

CREATE TABLE vertex{

id Node_id \ unique for each node.

cell grid_cell_number; \ the grid in which the node lies.

geometry;

}

CREATE TABLE edge {

int id ;

Int node_a;

int node_b; \ the connecting nodes

// we can have other parameters like traversal cost and return cost.

}

using the tables we can then fetch the edges form edge table using simple database querry once

we are provided with the grid cell number very easily.

In short the summary of the whole idea is :

Step1: Fetch the start node , get the related Grid cell number.

Step 2: Increment the graph by fetching all the items related to that grid.

Step3 : Check for boundary nodes ( this is done while we are partitioning) or target node .

Step 4: On hitting a boundary node

{

check if the connected grid is loaded and continue if it is

or we extend the graph with the new grid and continue with the routing;

}

or On hitting the target Node

{

stop;

}

4. Project plan

I will have about 12 weeks to implement the project. The tentative schedule is as follows:

Before 17th June : Get familiar with the development environment of pgRouting and test some demos.

week 1-2: Discuss and Define the various data structures and data table that will be required.Prepare the

Overall implementation architecture.

week 3-4- Discuss and Implement network partitioning using quad tree.

week 5-8 -Start coding for on demand graph generation and routing using Dijkstra. In between Prepare mid-term

report.

week 9 - Integration with pgrouting .

week 10-12- Testing and Bug fixing. Draft Final report and documentation.

5. Future ideas / How can your idea be expanded?

It can be integrated with other shortest path algorithms like astar etc. which pgrouitng provides.For time dependent

shortest path computation, it will greatly reduce the updating cost as we will be updating the cost of only those edges

that are contained in the grid cells that are loaded.

In route nearest neigbour querries can also be implemented using the partitioning approach.Overall we can

expand this approach to various other algorithms.

Explain how your SoC task would benefit the OSGeo member project and more generally the OSGeo Foundation as a whole:

The proposed idea will significantly improve the performance of shortest path finding algorithms.This will have a

positive effect on the user base of pgRouting. For various software paltforms or applications that are using this library ,

the response time will significantly improve.

Please provide details of general computing experience:

I generally use ubuntu ( 12.04) for all my academic purposes and windows 7 for entertainment only. I am familiar with Fedora also.

C++ is the language that i use most ( programming purposes). For implementing various course projects i have used C++ ,python ,Java and matlab.

I have no experience with hardware. The only experience that i had with networking was during my computer network course.

Please provide details of previous GIS experience:

I am a part of “Lab for Spatial Informatics” which is the only lab in India devoted to GIS applications and learning. I am familiar with and have used almost all the open source GIS platforms like Quantum , OpenJump, ILwis,Grass. We have our own rendering platform that was developed by our lab.(LSI viewer)

Please provide details of any previous involvement with GIS programming and other software programming:

I am very much familiar with Gdal/OGR as i used it extensively while implementing an outsourced project of Honeywell

Technology . I have played a lot with ESRI shape files.

Please tell us why you are interested in GIS and open source software:

I was very impressed with google earth when it was launched way back in 2004.GIS platforms like quantum and Openjump were introduced to me when i was in my second year and then i joined Lab for spatial informatics that is in our college based on my interest in this area.

open source platforms provide an opportunity to learn . The best part is you can always create or develop something that you are interested in and there are people who will always be there to help you if you are stuck.

Please tell us why you are interested in working for OSGeo and the software project you have selected:

It will be huge learning experience since i have been using platforms like Qgis , Gdal ,PostGis etc which come under Osgeo

I chose pgrouting because the algorithms that they have implemented are related to my masters topic and it will be great if i get an insight about how these were implemented on a much larger scale.

Please tell us why you are interested in your specific coding project:

Implementing routing algorithms for real world networks is actually very challenging.its a challenge to come up with good approaches so that the computation cost and response time is both reduced.

Would your application contribute to your ongoing studies/degree? If so, how?

I am pursuing my Masters and my topic is closely related to my proposal . If the results are impressive , i might get a publication in this area.

Please explain how you intend to continue being an active member of your project and/or OSGeo AFTER the summer is over:

I was always interested in open source programming but never knew where to start . GSOC provides an opportunity for beginners like me to take a dive in the area open source programming. i have other ideas like implementing IRNN ( In route nearest neighbour querries) which can be implemented within pgRouting.I have other intentions like working for bigger projects like Quantum Gis or Grass.I will be contributing to the community forum and will always try to improve things.

Do you understand this is a serious commitment, equivalent to a full-time paid summer internship or summer job?

Yes, I understand that this is a serious commitment and will try to give my best and work in a professional manner.

Do you have any known time conflicts during the official coding period? (June 17 to Sept. 27)

No .

···

On Thu, Apr 25, 2013 at 12:47 AM, Stephen Woodbridge <woodbri@swoodbridge.com> wrote:

On 4/24/2013 2:34 PM, Mukul priya wrote:

Hi Steve and Daniel ,

I have posted my proposal on Melange Gsoc system. Do have a look at it.
Waiting for feedback and suggestions.

Can you post a link to your proposal? or the text of it here also. I can never find anything in Melange or I may not have visibility to it yet as I just applied as a mentor.

Thanks,
-Steve

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

4

Hi Mukul,

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.

Are you familiar with how these are different?
http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html

Do you see why? and specifically why it matter for this project?

-Steve

On 4/24/2013 9:10 PM, Mukul priya wrote:

***Name*:Mukul Priya

*Country:*India

*School and degree*: International Institute Of Information
Technology-Hyderabad ,

                                B.Tech + Masters in computer Science And
Engineering

*Email*:mukul2047@gmail.com <mailto:mukul2047@gmail.com>

*Phone*:+91 9885991061

*OSGeo project(s*):pgRouting

*Title:* A partitioned approach to on demand increment graph assembly
for pgRouting.

*Describe your idea*
*1. Introduction*

        pgRouting has been working towards providing routing
functionality on a PostGis/PostgreSql Geo spatial

   database. It already has support for shortest path algorithm like
astar ,dijkstra , tdsp and trsp .But for a very

   large network, routing becomes time consuming. Network partitioning
is one such way which can prove to

   be helpful in improving the overall time efficiency of routing
querries. The main idea here is to first partition

   the whole network using a Quad tree approach and when the shortest
path is computed these partitions are

   loaded on demand. hence , there is an on demand incremental graph
generation.

        The project aims at designing and implementing a Shortest Path
algorithm on an on demand incremental

     Graph using a network partitioning approach.

*2. Background*

        Considering the present status where pgRouting has support for
shortest path algorithm like astar etc.

  Looking at their implementation details we can observe that the graph
is configured dynamically for all

  of them before computation.My proposal will also be on the same track
and for very large networks

  where the distance between source and destination can be very large ,
the response time will be

  significantly lesser and memory wise too it will be lot more
efficient. Presently they don't use any partitioning

  approach so it will prove to be a good addition to their support for
shortest past algorithms.

*3. The idea*

    There are two major components of my idea .

  *

    *Network Partitioning*

        For this part we can use a quad tree approach. Say , we start
with a square and a condition like maximum

        number of nodes that can reside in a square . if the number of
nodes in the square is greater than the max

        condition we further quarter it into four squares and allot the
nodes appropriately to each of them.All these

        squares can be called grids and they all will be addressed
uniquely using a grid cell number .Each node

        will be assigned a grid cell number based on the grid they are
lying inside.

               We will have data structures to address edges as they can
remain contained in either one grid cell

         or span across a number of grid cells.the idea is to first flag
such edges and store the grid cell numbers

         of the grids that the edge crosses/intersects.

  *

    *On demand graph generation and Routing.*

                The idea here is to first identify the grid cell
initially and then fetch the edges that are associated with

        that grid. These are the edges that will get appended to the
present graph and the graph will keep growing

        dynamically this way. we will have appropriate database tables
addressing the above issue such that

        we are able to fetch the required edges quickly using a
database querry.

         The implementation details for the above are :

        we will first partition the whole graph using the quad tree
approach and each node/vertex will be assigned

        a grid cell number so we can have database table for the
assigned nodes and edges like :

        CREATE TABLE vertex{

         id Node_id \\ unique for each
node.

         cell grid_cell_number; \\ the grid in which the
node lies.

          geometry;

          }

          CREATE TABLE edge {

           int id ;

           Int node_a;

            int node_b; \\ the connecting nodes

     // we can have other parameters like traversal cost and return
cost.

          }

           using the tables we can then fetch the edges form edge table
  using simple database querry once

  we are provided with the grid cell number very easily.

  In short the summary of the whole idea is :

Step1: Fetch the start node , get the related Grid cell number.

Step 2: Increment the graph by fetching all the items related to that grid.

Step3 : Check for boundary nodes ( this is done while we are
partitioning) or target node .

Step 4: On hitting a boundary node

                {

                  check if the connected grid is loaded and continue if
it is

                  or we extend the graph with the new grid and continue
with the routing;

                 }

            or On hitting the target Node

              {

                         stop;

               }

*4. Project plan*

      I will have about 12 weeks to implement the project. The tentative
schedule is as follows:

      Before 17th June : Get familiar with the development environment
of pgRouting and test some demos.

      week 1-2: Discuss and Define the various data structures and data
table that will be required.Prepare the

                      Overall implementation architecture.

      week 3-4- Discuss and Implement network partitioning using quad
tree.

      week 5-8 -Start coding for on demand graph generation and routing
using Dijkstra. In between Prepare mid-term

                        report.

      week 9 - Integration with pgrouting .

      week 10-12- Testing and Bug fixing. Draft Final report and
documentation.

*
  5. Future ideas / How can your idea be expanded? *

       It can be integrated with other shortest path algorithms like
astar etc. which pgrouitng provides.For time dependent

     shortest path computation, it will greatly reduce the updating cost
as we will be updating the cost of only those edges

     that are contained in the grid cells that are loaded.

      In route nearest neigbour querries can also be implemented using
the partitioning approach.Overall we can

      expand this approach to various other algorithms.

*Explain how your SoC task would benefit the OSGeo member project and
more generally the OSGeo Foundation as a whole:*

     The proposed idea will significantly improve the performance of
shortest path finding algorithms.This will have a

   positive effect on the user base of pgRouting. For various software
paltforms or applications that are using this library ,

   the response time will significantly improve.

*

Please provide details of general computing experience:
*

I generally use ubuntu ( 12.04) for all my academic purposes and windows
7 for entertainment only. I am familiar with Fedora also.

C++ is the language that i use most ( programming purposes). For
implementing various course projects i have used C++ ,python ,Java and
matlab.

I have no experience with hardware. The only experience that i had with
networking was during my computer network course.

*
Please provide details of previous GIS experience:*

I am a part of "Lab for Spatial Informatics" which is the only lab in
India devoted to GIS applications and learning. I am familiar with and
have used almost all the open source GIS platforms like Quantum ,
OpenJump, ILwis,Grass. We have our own rendering platform that was
developed by our lab.(LSI viewer)

*Please provide details of any previous involvement with GIS programming
and other software programming:*

I am very much familiar with Gdal/OGR as i used it extensively while
implementing an outsourced project of Honeywell

Technology . I have played a lot with ESRI shape files.

*Please tell us why you are interested in GIS and open source software:*

I was very impressed with google earth when it was launched way back in
2004.GIS platforms like quantum and Openjump were introduced to me when
i was in my second year and then i joined Lab for spatial informatics
that is in our college based on my interest in this area.

open source platforms provide an opportunity to learn . The best part is
you can always create or develop something that you are interested in
and there are people who will always be there to help you if you are stuck.

*

Please tell us why you are interested in working for OSGeo and the
software project you have selected:*

It will be huge learning experience since i have been using platforms
like Qgis , Gdal ,PostGis etc which come under Osgeo

I chose pgrouting because the algorithms that they have implemented are
related to my masters topic and it will be great if i get an insight
about how these were implemented on a much larger scale.

*Please tell us why you are interested in your specific coding project:*

Implementing routing algorithms for real world networks is actually very
challenging.its a challenge to come up with good approaches so that the
computation cost and response time is both reduced.

*Would your application contribute to your ongoing studies/degree? If
so, how?*

I am pursuing my Masters and my topic is closely related to my proposal
. If the results are impressive , i might get a publication in this area.

*Please explain how you intend to continue being an active member of
your project and/or OSGeo AFTER the summer is over:*

I was always interested in open source programming but never knew where
to start . GSOC provides an opportunity for beginners like me to take a
dive in the area open source programming. i have other ideas like
implementing IRNN ( In route nearest neighbour querries) which can be
implemented within pgRouting.I have other intentions like working for
bigger projects like Quantum Gis or Grass.I will be contributing to the
community forum and will always try to improve things.

*Do you understand this is a serious commitment, equivalent to a
full-time paid summer internship or summer job?*

Yes, I understand that this is a serious commitment and will try to give
my best and work in a professional manner.

*Do you have any known time conflicts during the official coding period?
(June 17 to Sept. 27)*

No .

On Thu, Apr 25, 2013 at 12:47 AM, Stephen Woodbridge
<woodbri@swoodbridge.com <mailto:woodbri@swoodbridge.com>> wrote:

    On 4/24/2013 2:34 PM, Mukul priya wrote:

        Hi Steve and Daniel ,

        I have posted my proposal on Melange Gsoc system. Do have a look
        at it.
        Waiting for feedback and suggestions.

    Can you post a link to your proposal? or the text of it here also. I
    can never find anything in Melange or I may not have visibility to
    it yet as I just applied as a mentor.

    Thanks,
       -Steve
    _________________________________________________
    pgrouting-dev mailing list
    pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
    http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
    <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;

_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

5

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.

Although do point out the advantages it has in real life road network and its importance to my proposal.

···

On Thu, Apr 25, 2013 at 7:43 AM, Stephen Woodbridge <woodbri@swoodbridge.com> wrote:

Hi Mukul,

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.

Are you familiar with how these are different?
http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html

Do you see why? and specifically why it matter for this project?

-Steve

On 4/24/2013 9:10 PM, Mukul priya wrote:

**Name:Mukul Priya

*Country:*India

School and degree: International Institute Of Information

Technology-Hyderabad ,

B.Tech + Masters in computer Science And
Engineering

Email:mukul2047@gmail.com mailto:[mukul2047@gmail.com](mailto:mukul2047@gmail.com)

Phone:+91 9885991061

OSGeo project(s):pgRouting

Title: A partitioned approach to on demand increment graph assembly
for pgRouting.

Describe your idea
1. Introduction

pgRouting has been working towards providing routing
functionality on a PostGis/PostgreSql Geo spatial

database. It already has support for shortest path algorithm like
astar ,dijkstra , tdsp and trsp .But for a very

large network, routing becomes time consuming. Network partitioning
is one such way which can prove to

be helpful in improving the overall time efficiency of routing
querries. The main idea here is to first partition

the whole network using a Quad tree approach and when the shortest
path is computed these partitions are

loaded on demand. hence , there is an on demand incremental graph
generation.

The project aims at designing and implementing a Shortest Path
algorithm on an on demand incremental

Graph using a network partitioning approach.

2. Background

Considering the present status where pgRouting has support for
shortest path algorithm like astar etc.

Looking at their implementation details we can observe that the graph
is configured dynamically for all

of them before computation.My proposal will also be on the same track
and for very large networks

where the distance between source and destination can be very large ,
the response time will be

significantly lesser and memory wise too it will be lot more
efficient. Presently they don’t use any partitioning

approach so it will prove to be a good addition to their support for
shortest past algorithms.

3. The idea

There are two major components of my idea .

Network Partitioning

For this part we can use a quad tree approach. Say , we start
with a square and a condition like maximum

number of nodes that can reside in a square . if the number of
nodes in the square is greater than the max

condition we further quarter it into four squares and allot the
nodes appropriately to each of them.All these

squares can be called grids and they all will be addressed
uniquely using a grid cell number .Each node

will be assigned a grid cell number based on the grid they are
lying inside.

We will have data structures to address edges as they can
remain contained in either one grid cell

or span across a number of grid cells.the idea is to first flag
such edges and store the grid cell numbers

of the grids that the edge crosses/intersects.

On demand graph generation and Routing.

The idea here is to first identify the grid cell
initially and then fetch the edges that are associated with

that grid. These are the edges that will get appended to the
present graph and the graph will keep growing

dynamically this way. we will have appropriate database tables
addressing the above issue such that

we are able to fetch the required edges quickly using a
database querry.

The implementation details for the above are :

we will first partition the whole graph using the quad tree
approach and each node/vertex will be assigned

a grid cell number so we can have database table for the
assigned nodes and edges like :

CREATE TABLE vertex{

id Node_id \ unique for each
node.

cell grid_cell_number; \ the grid in which the
node lies.

geometry;

}

CREATE TABLE edge {

int id ;

Int node_a;

int node_b; \ the connecting nodes

// we can have other parameters like traversal cost and return
cost.

}

using the tables we can then fetch the edges form edge table
using simple database querry once

we are provided with the grid cell number very easily.

In short the summary of the whole idea is :

Step1: Fetch the start node , get the related Grid cell number.

Step 2: Increment the graph by fetching all the items related to that grid.

Step3 : Check for boundary nodes ( this is done while we are
partitioning) or target node .

Step 4: On hitting a boundary node

{

check if the connected grid is loaded and continue if
it is

or we extend the graph with the new grid and continue
with the routing;

}

or On hitting the target Node

{

stop;

}

4. Project plan

I will have about 12 weeks to implement the project. The tentative
schedule is as follows:

Before 17th June : Get familiar with the development environment
of pgRouting and test some demos.

week 1-2: Discuss and Define the various data structures and data
table that will be required.Prepare the

Overall implementation architecture.

week 3-4- Discuss and Implement network partitioning using quad
tree.

week 5-8 -Start coding for on demand graph generation and routing
using Dijkstra. In between Prepare mid-term

report.

week 9 - Integration with pgrouting .

week 10-12- Testing and Bug fixing. Draft Final report and
documentation.

  1. Future ideas / How can your idea be expanded? *

It can be integrated with other shortest path algorithms like
astar etc. which pgrouitng provides.For time dependent

shortest path computation, it will greatly reduce the updating cost
as we will be updating the cost of only those edges

that are contained in the grid cells that are loaded.

In route nearest neigbour querries can also be implemented using
the partitioning approach.Overall we can

expand this approach to various other algorithms.

Explain how your SoC task would benefit the OSGeo member project and
more generally the OSGeo Foundation as a whole:

The proposed idea will significantly improve the performance of
shortest path finding algorithms.This will have a

positive effect on the user base of pgRouting. For various software
paltforms or applications that are using this library ,

the response time will significantly improve.

Please provide details of general computing experience:
*

I generally use ubuntu ( 12.04) for all my academic purposes and windows
7 for entertainment only. I am familiar with Fedora also.

C++ is the language that i use most ( programming purposes). For
implementing various course projects i have used C++ ,python ,Java and
matlab.

I have no experience with hardware. The only experience that i had with
networking was during my computer network course.

Please provide details of previous GIS experience:*

I am a part of “Lab for Spatial Informatics” which is the only lab in
India devoted to GIS applications and learning. I am familiar with and
have used almost all the open source GIS platforms like Quantum ,
OpenJump, ILwis,Grass. We have our own rendering platform that was
developed by our lab.(LSI viewer)

Please provide details of any previous involvement with GIS programming
and other software programming:

I am very much familiar with Gdal/OGR as i used it extensively while
implementing an outsourced project of Honeywell

Technology . I have played a lot with ESRI shape files.

Please tell us why you are interested in GIS and open source software:

I was very impressed with google earth when it was launched way back in
2004.GIS platforms like quantum and Openjump were introduced to me when
i was in my second year and then i joined Lab for spatial informatics
that is in our college based on my interest in this area.

open source platforms provide an opportunity to learn . The best part is
you can always create or develop something that you are interested in
and there are people who will always be there to help you if you are stuck.

Please tell us why you are interested in working for OSGeo and the

software project you have selected:*

It will be huge learning experience since i have been using platforms
like Qgis , Gdal ,PostGis etc which come under Osgeo

I chose pgrouting because the algorithms that they have implemented are
related to my masters topic and it will be great if i get an insight
about how these were implemented on a much larger scale.

Please tell us why you are interested in your specific coding project:

Implementing routing algorithms for real world networks is actually very
challenging.its a challenge to come up with good approaches so that the
computation cost and response time is both reduced.

Would your application contribute to your ongoing studies/degree? If
so, how?

I am pursuing my Masters and my topic is closely related to my proposal
. If the results are impressive , i might get a publication in this area.

Please explain how you intend to continue being an active member of
your project and/or OSGeo AFTER the summer is over:

I was always interested in open source programming but never knew where
to start . GSOC provides an opportunity for beginners like me to take a
dive in the area open source programming. i have other ideas like
implementing IRNN ( In route nearest neighbour querries) which can be
implemented within pgRouting.I have other intentions like working for
bigger projects like Quantum Gis or Grass.I will be contributing to the
community forum and will always try to improve things.

Do you understand this is a serious commitment, equivalent to a
full-time paid summer internship or summer job?

Yes, I understand that this is a serious commitment and will try to give
my best and work in a professional manner.

Do you have any known time conflicts during the official coding period?
(June 17 to Sept. 27)

No .

On Thu, Apr 25, 2013 at 12:47 AM, Stephen Woodbridge

<woodbri@swoodbridge.com mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)> wrote:

On 4/24/2013 2:34 PM, Mukul priya wrote:

Hi Steve and Daniel ,

I have posted my proposal on Melange Gsoc system. Do have a look
at it.
Waiting for feedback and suggestions.

Can you post a link to your proposal? or the text of it here also. I
can never find anything in Melange or I may not have visibility to
it yet as I just applied as a mentor.

Thanks,
-Steve

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

6

On 4/25/2013 12:26 AM, Mukul priya wrote:

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.

Although do point out the advantages it has in real life road network
and its importance to my proposal.

How much of the network do you have to explore using each algorithm?
How does this impact the number of grids you have to load?
How does this impact your proposal?

-Steve

On Thu, Apr 25, 2013 at 7:43 AM, Stephen Woodbridge
<woodbri@swoodbridge.com <mailto:woodbri@swoodbridge.com>> wrote:

    Hi Mukul,

    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.

    Are you familiar with how these are different?
    http://theory.stanford.edu/~__amitp/GameProgramming/__AStarComparison.html
    <http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html&gt;

    Do you see why? and specifically why it matter for this project?

    -Steve

    On 4/24/2013 9:10 PM, Mukul priya wrote:

        ***Name*:Mukul Priya

        *Country:*India

        *School and degree*: International Institute Of Information

        Technology-Hyderabad ,

                                         B.Tech + Masters in computer
        Science And
        Engineering

        *Email*:mukul2047@gmail.com <mailto:mukul2047@gmail.com>
        <mailto:mukul2047@gmail.com>

        *Phone*:+91 9885991061

        *OSGeo project(s*):pgRouting

        *Title:* A partitioned approach to on demand increment graph
        assembly
        for pgRouting.

        *Describe your idea*
        *1. Introduction*

                 pgRouting has been working towards providing routing
        functionality on a PostGis/PostgreSql Geo spatial

            database. It already has support for shortest path algorithm
        like
        astar ,dijkstra , tdsp and trsp .But for a very

            large network, routing becomes time consuming. Network
        partitioning
        is one such way which can prove to

            be helpful in improving the overall time efficiency of routing
        querries. The main idea here is to first partition

            the whole network using a Quad tree approach and when the
        shortest
        path is computed these partitions are

            loaded on demand. hence , there is an on demand incremental
        graph
        generation.

                 The project aims at designing and implementing a
        Shortest Path
        algorithm on an on demand incremental

              Graph using a network partitioning approach.

        *2. Background*

                 Considering the present status where pgRouting has
        support for
        shortest path algorithm like astar etc.

           Looking at their implementation details we can observe that
        the graph
        is configured dynamically for all

           of them before computation.My proposal will also be on the
        same track
        and for very large networks

           where the distance between source and destination can be
        very large ,
        the response time will be

           significantly lesser and memory wise too it will be lot more
        efficient. Presently they don't use any partitioning

           approach so it will prove to be a good addition to their
        support for
        shortest past algorithms.

        *3. The idea*

             There are two major components of my idea .

           *

             *Network Partitioning*

                 For this part we can use a quad tree approach. Say , we
        start
        with a square and a condition like maximum

                 number of nodes that can reside in a square . if the
        number of
        nodes in the square is greater than the max

                 condition we further quarter it into four squares and
        allot the
        nodes appropriately to each of them.All these

                 squares can be called grids and they all will be addressed
        uniquely using a grid cell number .Each node

                 will be assigned a grid cell number based on the grid
        they are
        lying inside.

                        We will have data structures to address edges as
        they can
        remain contained in either one grid cell

                  or span across a number of grid cells.the idea is to
        first flag
        such edges and store the grid cell numbers

                  of the grids that the edge crosses/intersects.

           *

             *On demand graph generation and Routing.*

                         The idea here is to first identify the grid cell
        initially and then fetch the edges that are associated with

                 that grid. These are the edges that will get appended
        to the
        present graph and the graph will keep growing

                 dynamically this way. we will have appropriate database
        tables
        addressing the above issue such that

                 we are able to fetch the required edges quickly using a
        database querry.

                  The implementation details for the above are :

                 we will first partition the whole graph using the quad tree
        approach and each node/vertex will be assigned

                 a grid cell number so we can have database table for the
        assigned nodes and edges like :

                 CREATE TABLE vertex{

                  id Node_id \\ unique
        for each
        node.

                  cell grid_cell_number; \\ the grid in
        which the
        node lies.

                   geometry;

                   }

                   CREATE TABLE edge {

                    int id ;

                    Int node_a;

                     int node_b; \\ the connecting nodes

              // we can have other parameters like traversal cost
        and return
        cost.

                   }

                    using the tables we can then fetch the edges form
        edge table
           using simple database querry once

           we are provided with the grid cell number very easily.

           In short the summary of the whole idea is :

        Step1: Fetch the start node , get the related Grid cell number.

        Step 2: Increment the graph by fetching all the items related to
        that grid.

        Step3 : Check for boundary nodes ( this is done while we are
        partitioning) or target node .

        Step 4: On hitting a boundary node

                         {

                           check if the connected grid is loaded and
        continue if
        it is

                           or we extend the graph with the new grid and
        continue
        with the routing;

                          }

                     or On hitting the target Node

                       {

                                  stop;

                        }

        *4. Project plan*

               I will have about 12 weeks to implement the project. The
        tentative
        schedule is as follows:

               Before 17th June : Get familiar with the development
        environment
        of pgRouting and test some demos.

               week 1-2: Discuss and Define the various data structures
        and data
        table that will be required.Prepare the

                               Overall implementation architecture.

               week 3-4- Discuss and Implement network partitioning
        using quad
        tree.

               week 5-8 -Start coding for on demand graph generation and
        routing
        using Dijkstra. In between Prepare mid-term

                                 report.

               week 9 - Integration with pgrouting .

               week 10-12- Testing and Bug fixing. Draft Final report and
        documentation.

        *
           5. Future ideas / How can your idea be expanded? *

                It can be integrated with other shortest path algorithms
        like
        astar etc. which pgrouitng provides.For time dependent

              shortest path computation, it will greatly reduce the
        updating cost
        as we will be updating the cost of only those edges

              that are contained in the grid cells that are loaded.

               In route nearest neigbour querries can also be
        implemented using
        the partitioning approach.Overall we can

               expand this approach to various other algorithms.

        *Explain how your SoC task would benefit the OSGeo member
        project and
        more generally the OSGeo Foundation as a whole:*

              The proposed idea will significantly improve the
        performance of
        shortest path finding algorithms.This will have a

            positive effect on the user base of pgRouting. For various
        software
        paltforms or applications that are using this library ,

            the response time will significantly improve.

        *

        Please provide details of general computing experience:
        *

        I generally use ubuntu ( 12.04) for all my academic purposes and
        windows
        7 for entertainment only. I am familiar with Fedora also.

        C++ is the language that i use most ( programming purposes). For
        implementing various course projects i have used C++ ,python
        ,Java and
        matlab.

        I have no experience with hardware. The only experience that i
        had with
        networking was during my computer network course.

        *
        Please provide details of previous GIS experience:*

        I am a part of "Lab for Spatial Informatics" which is the only
        lab in
        India devoted to GIS applications and learning. I am familiar
        with and
        have used almost all the open source GIS platforms like Quantum ,
        OpenJump, ILwis,Grass. We have our own rendering platform that was
        developed by our lab.(LSI viewer)

        *Please provide details of any previous involvement with GIS
        programming
        and other software programming:*

        I am very much familiar with Gdal/OGR as i used it extensively
        while
        implementing an outsourced project of Honeywell

        Technology . I have played a lot with ESRI shape files.

        *Please tell us why you are interested in GIS and open source
        software:*

        I was very impressed with google earth when it was launched way
        back in
        2004.GIS platforms like quantum and Openjump were introduced to
        me when
        i was in my second year and then i joined Lab for spatial
        informatics
        that is in our college based on my interest in this area.

        open source platforms provide an opportunity to learn . The best
        part is
        you can always create or develop something that you are
        interested in
        and there are people who will always be there to help you if you
        are stuck.

        *

        Please tell us why you are interested in working for OSGeo and the
        software project you have selected:*

        It will be huge learning experience since i have been using
        platforms
        like Qgis , Gdal ,PostGis etc which come under Osgeo

        I chose pgrouting because the algorithms that they have
        implemented are
        related to my masters topic and it will be great if i get an insight
        about how these were implemented on a much larger scale.

        *Please tell us why you are interested in your specific coding
        project:*

        Implementing routing algorithms for real world networks is
        actually very
        challenging.its a challenge to come up with good approaches so
        that the
        computation cost and response time is both reduced.

        *Would your application contribute to your ongoing
        studies/degree? If
        so, how?*

        I am pursuing my Masters and my topic is closely related to my
        proposal
        . If the results are impressive , i might get a publication in
        this area.

        *Please explain how you intend to continue being an active member of
        your project and/or OSGeo AFTER the summer is over:*

        I was always interested in open source programming but never
        knew where
        to start . GSOC provides an opportunity for beginners like me
        to take a
        dive in the area open source programming. i have other ideas like
        implementing IRNN ( In route nearest neighbour querries) which
        can be
        implemented within pgRouting.I have other intentions like
        working for
        bigger projects like Quantum Gis or Grass.I will be contributing
        to the
        community forum and will always try to improve things.

        *Do you understand this is a serious commitment, equivalent to a
        full-time paid summer internship or summer job?*

        Yes, I understand that this is a serious commitment and will try
        to give
        my best and work in a professional manner.

        *Do you have any known time conflicts during the official coding
        period?
        (June 17 to Sept. 27)*

        No .

        On Thu, Apr 25, 2013 at 12:47 AM, Stephen Woodbridge
        <woodbri@swoodbridge.com <mailto:woodbri@swoodbridge.com>
        <mailto:woodbri@swoodbridge.__com
        <mailto:woodbri@swoodbridge.com>>> wrote:

             On 4/24/2013 2:34 PM, Mukul priya wrote:

                 Hi Steve and Daniel ,

                 I have posted my proposal on Melange Gsoc system. Do
        have a look
                 at it.
                 Waiting for feedback and suggestions.

             Can you post a link to your proposal? or the text of it
        here also. I
             can never find anything in Melange or I may not have
        visibility to
             it yet as I just applied as a mentor.

             Thanks,
                -Steve
             ___________________________________________________
             pgrouting-dev mailing list
        pgrouting-dev@lists.osgeo.org
        <mailto:pgrouting-dev@lists.osgeo.org>
        <mailto:pgrouting-dev@lists.__osgeo.org
        <mailto:pgrouting-dev@lists.osgeo.org>>
        http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev&gt;
             <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;\_\_&gt;

        _________________________________________________
        pgrouting-dev mailing list
        pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
        http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;

    _________________________________________________
    pgrouting-dev mailing list
    pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
    http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
    <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;

_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

7

How much of the network do you have to explore using each algorithm?

This will be reduced significantly while using Astar as we will have a fair bit of idea about the direction towards which we should proceed.

How does this impact the number of grids you have to load?

Once we have an idea about the direction towards which we should proceed , only those grids will be loaded. This will result in loading of less number of grids.

How does this impact your proposal?

The basic motivation behind the proposal is to make shortest path computation faster. Number of database querry will be reduced as we will be fetching lesser number of grids. This will have a positive effect on computation time.

···

On Thu, Apr 25, 2013 at 7:07 PM, Stephen Woodbridge <woodbri@swoodbridge.com> wrote:

On 4/25/2013 12:26 AM, Mukul priya wrote:

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.

Although do point out the advantages it has in real life road network
and its importance to my proposal.

How much of the network do you have to explore using each algorithm?
How does this impact the number of grids you have to load?
How does this impact your proposal?

-Steve

On Thu, Apr 25, 2013 at 7:43 AM, Stephen Woodbridge

<woodbri@swoodbridge.com mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)> wrote:

Hi Mukul,

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.

Are you familiar with how these are different?

http://theory.stanford.edu/~__amitp/GameProgramming/__AStarComparison.html
<http://theory.stanford.edu/%7Eamitp/GameProgramming/AStarComparison.html>

Do you see why? and specifically why it matter for this project?

-Steve

On 4/24/2013 9:10 PM, Mukul priya wrote:

**Name:Mukul Priya

*Country:*India

School and degree: International Institute Of Information

Technology-Hyderabad ,

B.Tech + Masters in computer
Science And
Engineering

Email:mukul2047@gmail.com mailto:[mukul2047@gmail.com](mailto:mukul2047@gmail.com)

<mailto:mukul2047@gmail.com mailto:[mukul2047@gmail.com](mailto:mukul2047@gmail.com)>

Phone:+91 9885991061

OSGeo project(s):pgRouting

Title: A partitioned approach to on demand increment graph
assembly
for pgRouting.

Describe your idea
1. Introduction

pgRouting has been working towards providing routing
functionality on a PostGis/PostgreSql Geo spatial

database. It already has support for shortest path algorithm
like
astar ,dijkstra , tdsp and trsp .But for a very

large network, routing becomes time consuming. Network
partitioning
is one such way which can prove to

be helpful in improving the overall time efficiency of routing
querries. The main idea here is to first partition

the whole network using a Quad tree approach and when the
shortest
path is computed these partitions are

loaded on demand. hence , there is an on demand incremental
graph
generation.

The project aims at designing and implementing a
Shortest Path
algorithm on an on demand incremental

Graph using a network partitioning approach.

2. Background

Considering the present status where pgRouting has
support for
shortest path algorithm like astar etc.

Looking at their implementation details we can observe that
the graph
is configured dynamically for all

of them before computation.My proposal will also be on the
same track
and for very large networks

where the distance between source and destination can be
very large ,
the response time will be

significantly lesser and memory wise too it will be lot more
efficient. Presently they don’t use any partitioning

approach so it will prove to be a good addition to their
support for
shortest past algorithms.

3. The idea

There are two major components of my idea .

Network Partitioning

For this part we can use a quad tree approach. Say , we
start
with a square and a condition like maximum

number of nodes that can reside in a square . if the
number of
nodes in the square is greater than the max

condition we further quarter it into four squares and
allot the
nodes appropriately to each of them.All these

squares can be called grids and they all will be addressed
uniquely using a grid cell number .Each node

will be assigned a grid cell number based on the grid
they are
lying inside.

We will have data structures to address edges as
they can
remain contained in either one grid cell

or span across a number of grid cells.the idea is to
first flag
such edges and store the grid cell numbers

of the grids that the edge crosses/intersects.

On demand graph generation and Routing.

The idea here is to first identify the grid cell
initially and then fetch the edges that are associated with

that grid. These are the edges that will get appended
to the
present graph and the graph will keep growing

dynamically this way. we will have appropriate database
tables
addressing the above issue such that

we are able to fetch the required edges quickly using a
database querry.

The implementation details for the above are :

we will first partition the whole graph using the quad tree
approach and each node/vertex will be assigned

a grid cell number so we can have database table for the
assigned nodes and edges like :

CREATE TABLE vertex{

id Node_id \ unique
for each
node.

cell grid_cell_number; \ the grid in
which the
node lies.

geometry;

}

CREATE TABLE edge {

int id ;

Int node_a;

int node_b; \ the connecting nodes

// we can have other parameters like traversal cost
and return
cost.

}

using the tables we can then fetch the edges form
edge table
using simple database querry once

we are provided with the grid cell number very easily.

In short the summary of the whole idea is :

Step1: Fetch the start node , get the related Grid cell number.

Step 2: Increment the graph by fetching all the items related to
that grid.

Step3 : Check for boundary nodes ( this is done while we are
partitioning) or target node .

Step 4: On hitting a boundary node

{

check if the connected grid is loaded and
continue if
it is

or we extend the graph with the new grid and
continue
with the routing;

}

or On hitting the target Node

{

stop;

}

4. Project plan

I will have about 12 weeks to implement the project. The
tentative
schedule is as follows:

Before 17th June : Get familiar with the development
environment
of pgRouting and test some demos.

week 1-2: Discuss and Define the various data structures
and data
table that will be required.Prepare the

Overall implementation architecture.

week 3-4- Discuss and Implement network partitioning
using quad
tree.

week 5-8 -Start coding for on demand graph generation and
routing
using Dijkstra. In between Prepare mid-term

report.

week 9 - Integration with pgrouting .

week 10-12- Testing and Bug fixing. Draft Final report and
documentation.

  1. Future ideas / How can your idea be expanded? *

It can be integrated with other shortest path algorithms
like
astar etc. which pgrouitng provides.For time dependent

shortest path computation, it will greatly reduce the
updating cost
as we will be updating the cost of only those edges

that are contained in the grid cells that are loaded.

In route nearest neigbour querries can also be
implemented using
the partitioning approach.Overall we can

expand this approach to various other algorithms.

Explain how your SoC task would benefit the OSGeo member
project and
more generally the OSGeo Foundation as a whole:

The proposed idea will significantly improve the
performance of
shortest path finding algorithms.This will have a

positive effect on the user base of pgRouting. For various
software
paltforms or applications that are using this library ,

the response time will significantly improve.

Please provide details of general computing experience:
*

I generally use ubuntu ( 12.04) for all my academic purposes and
windows
7 for entertainment only. I am familiar with Fedora also.

C++ is the language that i use most ( programming purposes). For
implementing various course projects i have used C++ ,python
,Java and
matlab.

I have no experience with hardware. The only experience that i
had with
networking was during my computer network course.

Please provide details of previous GIS experience:*

I am a part of “Lab for Spatial Informatics” which is the only
lab in
India devoted to GIS applications and learning. I am familiar
with and
have used almost all the open source GIS platforms like Quantum ,
OpenJump, ILwis,Grass. We have our own rendering platform that was
developed by our lab.(LSI viewer)

Please provide details of any previous involvement with GIS
programming
and other software programming:

I am very much familiar with Gdal/OGR as i used it extensively
while
implementing an outsourced project of Honeywell

Technology . I have played a lot with ESRI shape files.

Please tell us why you are interested in GIS and open source
software:

I was very impressed with google earth when it was launched way
back in
2004.GIS platforms like quantum and Openjump were introduced to
me when
i was in my second year and then i joined Lab for spatial
informatics
that is in our college based on my interest in this area.

open source platforms provide an opportunity to learn . The best
part is
you can always create or develop something that you are
interested in
and there are people who will always be there to help you if you
are stuck.

Please tell us why you are interested in working for OSGeo and the
software project you have selected:*

It will be huge learning experience since i have been using
platforms
like Qgis , Gdal ,PostGis etc which come under Osgeo

I chose pgrouting because the algorithms that they have
implemented are
related to my masters topic and it will be great if i get an insight
about how these were implemented on a much larger scale.

Please tell us why you are interested in your specific coding
project:

Implementing routing algorithms for real world networks is
actually very
challenging.its a challenge to come up with good approaches so
that the
computation cost and response time is both reduced.

Would your application contribute to your ongoing
studies/degree? If
so, how?

I am pursuing my Masters and my topic is closely related to my
proposal
. If the results are impressive , i might get a publication in
this area.

Please explain how you intend to continue being an active member of
your project and/or OSGeo AFTER the summer is over:

I was always interested in open source programming but never
knew where
to start . GSOC provides an opportunity for beginners like me
to take a
dive in the area open source programming. i have other ideas like
implementing IRNN ( In route nearest neighbour querries) which
can be
implemented within pgRouting.I have other intentions like
working for
bigger projects like Quantum Gis or Grass.I will be contributing
to the
community forum and will always try to improve things.

Do you understand this is a serious commitment, equivalent to a
full-time paid summer internship or summer job?

Yes, I understand that this is a serious commitment and will try
to give
my best and work in a professional manner.

Do you have any known time conflicts during the official coding
period?
(June 17 to Sept. 27)

No .

On Thu, Apr 25, 2013 at 12:47 AM, Stephen Woodbridge
<woodbri@swoodbridge.com mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)

<mailto:woodbri@swoodbridge.__com

mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)>> wrote:

On 4/24/2013 2:34 PM, Mukul priya wrote:

Hi Steve and Daniel ,

I have posted my proposal on Melange Gsoc system. Do
have a look
at it.
Waiting for feedback and suggestions.

Can you post a link to your proposal? or the text of it
here also. I
can never find anything in Melange or I may not have
visibility to
it yet as I just applied as a mentor.

Thanks,
-Steve

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)

<mailto:pgrouting-dev@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)>
http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>
<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

8

On 4/25/2013 11:06 AM, Mukul priya wrote:

How much of the network do you have to explore using each algorithm?

This will be reduced significantly while using Astar as we will have a
fair bit of idea about the direction towards which we should proceed.

How does this impact the number of grids you have to load?

Once we have an idea about the direction towards which we should proceed
, only those grids will be loaded. This will result in loading of less
number of grids.

How does this impact your proposal?
The basic motivation behind the proposal is to make shortest path
computation faster. Number of database querry will be reduced as we will
be fetching lesser number of grids. This will have a positive effect on
computation time.

Right, so in your proposal, you want to be clear that the benefit will be achieved using astar or another algorithm with a heuristic and not dijkstra. I understand that "shortest path" is a generic reference to all of these algorithms, but the only ones that will benefit from this approach will be ones with a heuristic that allow us to explore only a subset the overall bounding box of edges that we might otherwise use as input. So it is best to be clear on these points.

-Steve

On Thu, Apr 25, 2013 at 7:07 PM, Stephen Woodbridge
<woodbri@swoodbridge.com <mailto:woodbri@swoodbridge.com>> wrote:

    On 4/25/2013 12:26 AM, Mukul priya wrote:

        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.

        Although do point out the advantages it has in real life road
        network
        and its importance to my proposal.

    How much of the network do you have to explore using each algorithm?
    How does this impact the number of grids you have to load?
    How does this impact your proposal?

    -Steve

        On Thu, Apr 25, 2013 at 7:43 AM, Stephen Woodbridge
        <woodbri@swoodbridge.com <mailto:woodbri@swoodbridge.com>
        <mailto:woodbri@swoodbridge.__com
        <mailto:woodbri@swoodbridge.com>>> wrote:

             Hi Mukul,

             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.

             Are you familiar with how these are different?
        http://theory.stanford.edu/~____amitp/GameProgramming/____AStarComparison.html
        <http://theory.stanford.edu/~__amitp/GameProgramming/__AStarComparison.html&gt;

        <http://theory.stanford.edu/%\_\_7Eamitp/GameProgramming/\_\_AStarComparison\.html
        <http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html&gt;&gt;

             Do you see why? and specifically why it matter for this
        project?

             -Steve

             On 4/24/2013 9:10 PM, Mukul priya wrote:

                 ***Name*:Mukul Priya

                 *Country:*India

                 *School and degree*: International Institute Of Information

                 Technology-Hyderabad ,

                                                  B.Tech + Masters in
        computer
                 Science And
                 Engineering

                 *Email*:mukul2047@gmail.com
        <mailto:mukul2047@gmail.com> <mailto:mukul2047@gmail.com
        <mailto:mukul2047@gmail.com>>
                 <mailto:mukul2047@gmail.com
        <mailto:mukul2047@gmail.com> <mailto:mukul2047@gmail.com
        <mailto:mukul2047@gmail.com>>>

                 *Phone*:+91 9885991061

                 *OSGeo project(s*):pgRouting

                 *Title:* A partitioned approach to on demand increment
        graph
                 assembly
                 for pgRouting.

                 *Describe your idea*
                 *1. Introduction*

                          pgRouting has been working towards providing
        routing
                 functionality on a PostGis/PostgreSql Geo spatial

                     database. It already has support for shortest path
        algorithm
                 like
                 astar ,dijkstra , tdsp and trsp .But for a very

                     large network, routing becomes time consuming. Network
                 partitioning
                 is one such way which can prove to

                     be helpful in improving the overall time efficiency
        of routing
                 querries. The main idea here is to first partition

                     the whole network using a Quad tree approach and
        when the
                 shortest
                 path is computed these partitions are

                     loaded on demand. hence , there is an on demand
        incremental
                 graph
                 generation.

                          The project aims at designing and implementing a
                 Shortest Path
                 algorithm on an on demand incremental

                       Graph using a network partitioning approach.

                 *2. Background*

                          Considering the present status where pgRouting has
                 support for
                 shortest path algorithm like astar etc.

                    Looking at their implementation details we can
        observe that
                 the graph
                 is configured dynamically for all

                    of them before computation.My proposal will also be
        on the
                 same track
                 and for very large networks

                    where the distance between source and destination
        can be
                 very large ,
                 the response time will be

                    significantly lesser and memory wise too it will be
        lot more
                 efficient. Presently they don't use any partitioning

                    approach so it will prove to be a good addition to their
                 support for
                 shortest past algorithms.

                 *3. The idea*

                      There are two major components of my idea .

                    *

                      *Network Partitioning*

                          For this part we can use a quad tree approach.
        Say , we
                 start
                 with a square and a condition like maximum

                          number of nodes that can reside in a square .
        if the
                 number of
                 nodes in the square is greater than the max

                          condition we further quarter it into four
        squares and
                 allot the
                 nodes appropriately to each of them.All these

                          squares can be called grids and they all will
        be addressed
                 uniquely using a grid cell number .Each node

                          will be assigned a grid cell number based on
        the grid
                 they are
                 lying inside.

                                 We will have data structures to address
        edges as
                 they can
                 remain contained in either one grid cell

                           or span across a number of grid cells.the
        idea is to
                 first flag
                 such edges and store the grid cell numbers

                           of the grids that the edge crosses/intersects.

                    *

                      *On demand graph generation and Routing.*

                                  The idea here is to first identify the
        grid cell
                 initially and then fetch the edges that are associated with

                          that grid. These are the edges that will get
        appended
                 to the
                 present graph and the graph will keep growing

                          dynamically this way. we will have appropriate
        database
                 tables
                 addressing the above issue such that

                          we are able to fetch the required edges
        quickly using a
                 database querry.

                           The implementation details for the above are :

                          we will first partition the whole graph using
        the quad tree
                 approach and each node/vertex will be assigned

                          a grid cell number so we can have database
        table for the
                 assigned nodes and edges like :

                          CREATE TABLE vertex{

                           id Node_id \\
          unique
                 for each
                 node.

                           cell grid_cell_number; \\ the
        grid in
                 which the
                 node lies.

                            geometry;

                            }

                            CREATE TABLE edge {

                             int id ;

                             Int node_a;

                              int node_b; \\ the connecting nodes

                       // we can have other parameters like
        traversal cost
                 and return
                 cost.

                            }

                             using the tables we can then fetch the
        edges form
                 edge table
                    using simple database querry once

                    we are provided with the grid cell number very easily.

                    In short the summary of the whole idea is :

                 Step1: Fetch the start node , get the related Grid cell
        number.

                 Step 2: Increment the graph by fetching all the items
        related to
                 that grid.

                 Step3 : Check for boundary nodes ( this is done while
        we are
                 partitioning) or target node .

                 Step 4: On hitting a boundary node

                                  {

                                    check if the connected grid is
        loaded and
                 continue if
                 it is

                                    or we extend the graph with the new
        grid and
                 continue
                 with the routing;

                                   }

                              or On hitting the target Node

                                {

                                           stop;

                                 }

                 *4. Project plan*

                        I will have about 12 weeks to implement the
        project. The
                 tentative
                 schedule is as follows:

                        Before 17th June : Get familiar with the development
                 environment
                 of pgRouting and test some demos.

                        week 1-2: Discuss and Define the various data
        structures
                 and data
                 table that will be required.Prepare the

                                        Overall implementation
          architecture.

                        week 3-4- Discuss and Implement network
        partitioning
                 using quad
                 tree.

                        week 5-8 -Start coding for on demand graph
        generation and
                 routing
                 using Dijkstra. In between Prepare mid-term

                                          report.

                        week 9 - Integration with pgrouting .

                        week 10-12- Testing and Bug fixing. Draft Final
        report and
                 documentation.

                 *
                    5. Future ideas / How can your idea be expanded? *

                         It can be integrated with other shortest path
        algorithms
                 like
                 astar etc. which pgrouitng provides.For time dependent

                       shortest path computation, it will greatly reduce the
                 updating cost
                 as we will be updating the cost of only those edges

                       that are contained in the grid cells that are loaded.

                        In route nearest neigbour querries can also be
                 implemented using
                 the partitioning approach.Overall we can

                        expand this approach to various other algorithms.

                 *Explain how your SoC task would benefit the OSGeo member
                 project and
                 more generally the OSGeo Foundation as a whole:*

                       The proposed idea will significantly improve the
                 performance of
                 shortest path finding algorithms.This will have a

                     positive effect on the user base of pgRouting. For
        various
                 software
                 paltforms or applications that are using this library ,

                     the response time will significantly improve.

                 *

                 Please provide details of general computing experience:
                 *

                 I generally use ubuntu ( 12.04) for all my academic
        purposes and
                 windows
                 7 for entertainment only. I am familiar with Fedora also.

                 C++ is the language that i use most ( programming
        purposes). For
                 implementing various course projects i have used C++
        ,python
                 ,Java and
                 matlab.

                 I have no experience with hardware. The only experience
        that i
                 had with
                 networking was during my computer network course.

                 *
                 Please provide details of previous GIS experience:*

                 I am a part of "Lab for Spatial Informatics" which is
        the only
                 lab in
                 India devoted to GIS applications and learning. I am
        familiar
                 with and
                 have used almost all the open source GIS platforms like
        Quantum ,
                 OpenJump, ILwis,Grass. We have our own rendering
        platform that was
                 developed by our lab.(LSI viewer)

                 *Please provide details of any previous involvement
        with GIS
                 programming
                 and other software programming:*

                 I am very much familiar with Gdal/OGR as i used it
        extensively
                 while
                 implementing an outsourced project of Honeywell

                 Technology . I have played a lot with ESRI shape files.

                 *Please tell us why you are interested in GIS and open
        source
                 software:*

                 I was very impressed with google earth when it was
        launched way
                 back in
                 2004.GIS platforms like quantum and Openjump were
        introduced to
                 me when
                 i was in my second year and then i joined Lab for spatial
                 informatics
                 that is in our college based on my interest in this area.

                 open source platforms provide an opportunity to learn .
        The best
                 part is
                 you can always create or develop something that you are
                 interested in
                 and there are people who will always be there to help
        you if you
                 are stuck.

                 *

                 Please tell us why you are interested in working for
        OSGeo and the
                 software project you have selected:*

                 It will be huge learning experience since i have been
        using
                 platforms
                 like Qgis , Gdal ,PostGis etc which come under Osgeo

                 I chose pgrouting because the algorithms that they have
                 implemented are
                 related to my masters topic and it will be great if i
        get an insight
                 about how these were implemented on a much larger scale.

                 *Please tell us why you are interested in your specific
        coding
                 project:*

                 Implementing routing algorithms for real world networks is
                 actually very
                 challenging.its a challenge to come up with good
        approaches so
                 that the
                 computation cost and response time is both reduced.

                 *Would your application contribute to your ongoing
                 studies/degree? If
                 so, how?*

                 I am pursuing my Masters and my topic is closely
        related to my
                 proposal
                 . If the results are impressive , i might get a
        publication in
                 this area.

                 *Please explain how you intend to continue being an
        active member of
                 your project and/or OSGeo AFTER the summer is over:*

                 I was always interested in open source programming but
        never
                 knew where
                 to start . GSOC provides an opportunity for beginners
        like me
                 to take a
                 dive in the area open source programming. i have other
        ideas like
                 implementing IRNN ( In route nearest neighbour
        querries) which
                 can be
                 implemented within pgRouting.I have other intentions like
                 working for
                 bigger projects like Quantum Gis or Grass.I will be
        contributing
                 to the
                 community forum and will always try to improve things.

                 *Do you understand this is a serious commitment,
        equivalent to a
                 full-time paid summer internship or summer job?*

                 Yes, I understand that this is a serious commitment and
        will try
                 to give
                 my best and work in a professional manner.

                 *Do you have any known time conflicts during the
        official coding
                 period?
                 (June 17 to Sept. 27)*

                 No .

                 On Thu, Apr 25, 2013 at 12:47 AM, Stephen Woodbridge
                 <woodbri@swoodbridge.com
        <mailto:woodbri@swoodbridge.com>
        <mailto:woodbri@swoodbridge.__com <mailto:woodbri@swoodbridge.com>>
                 <mailto:woodbri@swoodbridge.
        <mailto:woodbri@swoodbridge.>____com

                 <mailto:woodbri@swoodbridge.__com
        <mailto:woodbri@swoodbridge.com>>>> wrote:

                      On 4/24/2013 2:34 PM, Mukul priya wrote:

                          Hi Steve and Daniel ,

                          I have posted my proposal on Melange Gsoc
        system. Do
                 have a look
                          at it.
                          Waiting for feedback and suggestions.

                      Can you post a link to your proposal? or the text
        of it
                 here also. I
                      can never find anything in Melange or I may not have
                 visibility to
                      it yet as I just applied as a mentor.

                      Thanks,
                         -Steve
                      _____________________________________________________

                      pgrouting-dev mailing list
        pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
                 <mailto:pgrouting-dev@lists.__osgeo.org
        <mailto:pgrouting-dev@lists.osgeo.org>>
                 <mailto:pgrouting-dev@lists.
        <mailto:pgrouting-dev@lists.>____osgeo.org <http://osgeo.org>
                 <mailto:pgrouting-dev@lists.__osgeo.org
        <mailto:pgrouting-dev@lists.osgeo.org>>>
        http://lists.osgeo.org/______mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev&gt;

        <http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev&gt;\_\_&gt;

          <http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev&gt;

        <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;\_\_&gt;\_\_&gt;

                 ___________________________________________________
                 pgrouting-dev mailing list
        pgrouting-dev@lists.osgeo.org
        <mailto:pgrouting-dev@lists.osgeo.org>
        <mailto:pgrouting-dev@lists.__osgeo.org
        <mailto:pgrouting-dev@lists.osgeo.org>>
        http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev&gt;

        <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;\_\_&gt;

             ___________________________________________________
             pgrouting-dev mailing list
        pgrouting-dev@lists.osgeo.org
        <mailto:pgrouting-dev@lists.osgeo.org>
        <mailto:pgrouting-dev@lists.__osgeo.org
        <mailto:pgrouting-dev@lists.osgeo.org>>
        http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev&gt;
             <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;\_\_&gt;

        _________________________________________________
        pgrouting-dev mailing list
        pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
        http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;

    _________________________________________________
    pgrouting-dev mailing list
    pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
    http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
    <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;

_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

9

Thanks Steve will add a few lines to my proposal explaining the reason behind opting Astar.

Mukul

···

On Thu, Apr 25, 2013 at 8:55 PM, Stephen Woodbridge <woodbri@swoodbridge.com> wrote:

On 4/25/2013 11:06 AM, Mukul priya wrote:

How much of the network do you have to explore using each algorithm?

This will be reduced significantly while using Astar as we will have a
fair bit of idea about the direction towards which we should proceed.

How does this impact the number of grids you have to load?

Once we have an idea about the direction towards which we should proceed
, only those grids will be loaded. This will result in loading of less
number of grids.

How does this impact your proposal?
The basic motivation behind the proposal is to make shortest path
computation faster. Number of database querry will be reduced as we will
be fetching lesser number of grids. This will have a positive effect on
computation time.

Right, so in your proposal, you want to be clear that the benefit will be achieved using astar or another algorithm with a heuristic and not dijkstra. I understand that “shortest path” is a generic reference to all of these algorithms, but the only ones that will benefit from this approach will be ones with a heuristic that allow us to explore only a subset the overall bounding box of edges that we might otherwise use as input. So it is best to be clear on these points.

-Steve

On Thu, Apr 25, 2013 at 7:07 PM, Stephen Woodbridge

<woodbri@swoodbridge.com mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)> wrote:

On 4/25/2013 12:26 AM, Mukul priya wrote:

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.

Although do point out the advantages it has in real life road
network
and its importance to my proposal.

How much of the network do you have to explore using each algorithm?
How does this impact the number of grids you have to load?
How does this impact your proposal?

-Steve

On Thu, Apr 25, 2013 at 7:43 AM, Stephen Woodbridge
<woodbri@swoodbridge.com mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)

<mailto:woodbri@swoodbridge.__com
mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)>> wrote:

Hi Mukul,

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.

Are you familiar with how these are different?

http://theory.stanford.edu/~____amitp/GameProgramming/____AStarComparison.html
<http://theory.stanford.edu/%7E__amitp/GameProgramming/__AStarComparison.html>

<http://theory.stanford.edu/%__7Eamitp/GameProgramming/__AStarComparison.html

<http://theory.stanford.edu/%7Eamitp/GameProgramming/AStarComparison.html>>

Do you see why? and specifically why it matter for this
project?

-Steve

On 4/24/2013 9:10 PM, Mukul priya wrote:

**Name:Mukul Priya

*Country:*India

School and degree: International Institute Of Information

Technology-Hyderabad ,

B.Tech + Masters in
computer
Science And
Engineering

Email:mukul2047@gmail.com
mailto:[mukul2047@gmail.com](mailto:mukul2047@gmail.com) <mailto:mukul2047@gmail.com
mailto:[mukul2047@gmail.com](mailto:mukul2047@gmail.com)>
<mailto:mukul2047@gmail.com
mailto:[mukul2047@gmail.com](mailto:mukul2047@gmail.com) <mailto:mukul2047@gmail.com
mailto:[mukul2047@gmail.com](mailto:mukul2047@gmail.com)>>

Phone:+91 9885991061

OSGeo project(s):pgRouting

Title: A partitioned approach to on demand increment
graph
assembly
for pgRouting.

Describe your idea
1. Introduction

pgRouting has been working towards providing
routing
functionality on a PostGis/PostgreSql Geo spatial

database. It already has support for shortest path
algorithm
like
astar ,dijkstra , tdsp and trsp .But for a very

large network, routing becomes time consuming. Network
partitioning
is one such way which can prove to

be helpful in improving the overall time efficiency
of routing
querries. The main idea here is to first partition

the whole network using a Quad tree approach and
when the
shortest
path is computed these partitions are

loaded on demand. hence , there is an on demand
incremental
graph
generation.

The project aims at designing and implementing a
Shortest Path
algorithm on an on demand incremental

Graph using a network partitioning approach.

2. Background

Considering the present status where pgRouting has
support for
shortest path algorithm like astar etc.

Looking at their implementation details we can
observe that
the graph
is configured dynamically for all

of them before computation.My proposal will also be
on the
same track
and for very large networks

where the distance between source and destination
can be
very large ,
the response time will be

significantly lesser and memory wise too it will be
lot more
efficient. Presently they don’t use any partitioning

approach so it will prove to be a good addition to their
support for
shortest past algorithms.

3. The idea

There are two major components of my idea .

Network Partitioning

For this part we can use a quad tree approach.
Say , we
start
with a square and a condition like maximum

number of nodes that can reside in a square .
if the
number of
nodes in the square is greater than the max

condition we further quarter it into four
squares and
allot the
nodes appropriately to each of them.All these

squares can be called grids and they all will
be addressed
uniquely using a grid cell number .Each node

will be assigned a grid cell number based on
the grid
they are
lying inside.

We will have data structures to address
edges as
they can
remain contained in either one grid cell

or span across a number of grid cells.the
idea is to
first flag
such edges and store the grid cell numbers

of the grids that the edge crosses/intersects.

On demand graph generation and Routing.

The idea here is to first identify the
grid cell
initially and then fetch the edges that are associated with

that grid. These are the edges that will get
appended
to the
present graph and the graph will keep growing

dynamically this way. we will have appropriate
database
tables
addressing the above issue such that

we are able to fetch the required edges
quickly using a
database querry.

The implementation details for the above are :

we will first partition the whole graph using
the quad tree
approach and each node/vertex will be assigned

a grid cell number so we can have database
table for the
assigned nodes and edges like :

CREATE TABLE vertex{

id Node_id \
unique
for each
node.

cell grid_cell_number; \ the
grid in
which the
node lies.

geometry;

}

CREATE TABLE edge {

int id ;

Int node_a;

int node_b; \ the connecting nodes

// we can have other parameters like
traversal cost
and return
cost.

}

using the tables we can then fetch the
edges form
edge table
using simple database querry once

we are provided with the grid cell number very easily.

In short the summary of the whole idea is :

Step1: Fetch the start node , get the related Grid cell
number.

Step 2: Increment the graph by fetching all the items
related to
that grid.

Step3 : Check for boundary nodes ( this is done while
we are
partitioning) or target node .

Step 4: On hitting a boundary node

{

check if the connected grid is
loaded and
continue if
it is

or we extend the graph with the new
grid and
continue
with the routing;

}

or On hitting the target Node

{

stop;

}

4. Project plan

I will have about 12 weeks to implement the
project. The
tentative
schedule is as follows:

Before 17th June : Get familiar with the development
environment
of pgRouting and test some demos.

week 1-2: Discuss and Define the various data
structures
and data
table that will be required.Prepare the

Overall implementation
architecture.

week 3-4- Discuss and Implement network
partitioning
using quad
tree.

week 5-8 -Start coding for on demand graph
generation and
routing
using Dijkstra. In between Prepare mid-term

report.

week 9 - Integration with pgrouting .

week 10-12- Testing and Bug fixing. Draft Final
report and
documentation.

  1. Future ideas / How can your idea be expanded? *

It can be integrated with other shortest path
algorithms
like
astar etc. which pgrouitng provides.For time dependent

shortest path computation, it will greatly reduce the
updating cost
as we will be updating the cost of only those edges

that are contained in the grid cells that are loaded.

In route nearest neigbour querries can also be
implemented using
the partitioning approach.Overall we can

expand this approach to various other algorithms.

Explain how your SoC task would benefit the OSGeo member
project and
more generally the OSGeo Foundation as a whole:

The proposed idea will significantly improve the
performance of
shortest path finding algorithms.This will have a

positive effect on the user base of pgRouting. For
various
software
paltforms or applications that are using this library ,

the response time will significantly improve.

Please provide details of general computing experience:
*

I generally use ubuntu ( 12.04) for all my academic
purposes and
windows
7 for entertainment only. I am familiar with Fedora also.

C++ is the language that i use most ( programming
purposes). For
implementing various course projects i have used C++
,python
,Java and
matlab.

I have no experience with hardware. The only experience
that i
had with
networking was during my computer network course.

Please provide details of previous GIS experience:*

I am a part of “Lab for Spatial Informatics” which is
the only
lab in
India devoted to GIS applications and learning. I am
familiar
with and
have used almost all the open source GIS platforms like
Quantum ,
OpenJump, ILwis,Grass. We have our own rendering
platform that was
developed by our lab.(LSI viewer)

Please provide details of any previous involvement
with GIS
programming
and other software programming:

I am very much familiar with Gdal/OGR as i used it
extensively
while
implementing an outsourced project of Honeywell

Technology . I have played a lot with ESRI shape files.

Please tell us why you are interested in GIS and open
source
software:

I was very impressed with google earth when it was
launched way
back in
2004.GIS platforms like quantum and Openjump were
introduced to
me when
i was in my second year and then i joined Lab for spatial
informatics
that is in our college based on my interest in this area.

open source platforms provide an opportunity to learn .
The best
part is
you can always create or develop something that you are
interested in
and there are people who will always be there to help
you if you
are stuck.

Please tell us why you are interested in working for
OSGeo and the
software project you have selected:*

It will be huge learning experience since i have been
using
platforms
like Qgis , Gdal ,PostGis etc which come under Osgeo

I chose pgrouting because the algorithms that they have
implemented are
related to my masters topic and it will be great if i
get an insight
about how these were implemented on a much larger scale.

Please tell us why you are interested in your specific
coding
project:

Implementing routing algorithms for real world networks is
actually very
challenging.its a challenge to come up with good
approaches so
that the
computation cost and response time is both reduced.

Would your application contribute to your ongoing
studies/degree? If
so, how?

I am pursuing my Masters and my topic is closely
related to my
proposal
. If the results are impressive , i might get a
publication in
this area.

Please explain how you intend to continue being an
active member of
your project and/or OSGeo AFTER the summer is over:

I was always interested in open source programming but
never
knew where
to start . GSOC provides an opportunity for beginners
like me
to take a
dive in the area open source programming. i have other
ideas like
implementing IRNN ( In route nearest neighbour
querries) which
can be
implemented within pgRouting.I have other intentions like
working for
bigger projects like Quantum Gis or Grass.I will be
contributing
to the
community forum and will always try to improve things.

Do you understand this is a serious commitment,
equivalent to a
full-time paid summer internship or summer job?

Yes, I understand that this is a serious commitment and
will try
to give
my best and work in a professional manner.

Do you have any known time conflicts during the
official coding
period?
(June 17 to Sept. 27)

No .

On Thu, Apr 25, 2013 at 12:47 AM, Stephen Woodbridge
<woodbri@swoodbridge.com
mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)
<mailto:woodbri@swoodbridge.__com mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)>

<mailto:woodbri@swoodbridge.
mailto:[woodbri@swoodbridge](mailto:woodbri@swoodbridge).____com

<mailto:woodbri@swoodbridge.__com
mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)>>> wrote:

On 4/24/2013 2:34 PM, Mukul priya wrote:

Hi Steve and Daniel ,

I have posted my proposal on Melange Gsoc
system. Do
have a look
at it.
Waiting for feedback and suggestions.

Can you post a link to your proposal? or the text
of it
here also. I
can never find anything in Melange or I may not have
visibility to
it yet as I just applied as a mentor.

Thanks,
-Steve

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
<mailto:pgrouting-dev@lists.__osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)>

<mailto:pgrouting-dev@lists.
mailto:[pgrouting-dev@lists](mailto:pgrouting-dev@lists).____osgeo.org <http://osgeo.org>
<mailto:pgrouting-dev@lists.__osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)>>
http://lists.osgeo.org/______mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev>

<http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>__>

<http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>

<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>>>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
<mailto:pgrouting-dev@lists.__osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)>
http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>

<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>__>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
<mailto:pgrouting-dev@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)>
http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>
<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

10

Hi steve , i have edited my proposal based on our previous discussion ( added some lines about Astar) .meanwhile do suggest if there is scope of some improvement .

Thanks

Mukul

···

On Thu, Apr 25, 2013 at 11:22 PM, Mukul priya <mukul2047@gmail.com> wrote:

Thanks Steve will add a few lines to my proposal explaining the reason behind opting Astar.

Mukul

On Thu, Apr 25, 2013 at 8:55 PM, Stephen Woodbridge <woodbri@swoodbridge.com> wrote:

On 4/25/2013 11:06 AM, Mukul priya wrote:

How much of the network do you have to explore using each algorithm?

This will be reduced significantly while using Astar as we will have a
fair bit of idea about the direction towards which we should proceed.

How does this impact the number of grids you have to load?

Once we have an idea about the direction towards which we should proceed
, only those grids will be loaded. This will result in loading of less
number of grids.

How does this impact your proposal?
The basic motivation behind the proposal is to make shortest path
computation faster. Number of database querry will be reduced as we will
be fetching lesser number of grids. This will have a positive effect on
computation time.

Right, so in your proposal, you want to be clear that the benefit will be achieved using astar or another algorithm with a heuristic and not dijkstra. I understand that “shortest path” is a generic reference to all of these algorithms, but the only ones that will benefit from this approach will be ones with a heuristic that allow us to explore only a subset the overall bounding box of edges that we might otherwise use as input. So it is best to be clear on these points.

-Steve

On Thu, Apr 25, 2013 at 7:07 PM, Stephen Woodbridge

<woodbri@swoodbridge.com mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)> wrote:

On 4/25/2013 12:26 AM, Mukul priya wrote:

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.

Although do point out the advantages it has in real life road
network
and its importance to my proposal.

How much of the network do you have to explore using each algorithm?
How does this impact the number of grids you have to load?
How does this impact your proposal?

-Steve

On Thu, Apr 25, 2013 at 7:43 AM, Stephen Woodbridge
<woodbri@swoodbridge.com mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)

<mailto:woodbri@swoodbridge.__com
mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)>> wrote:

Hi Mukul,

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.

Are you familiar with how these are different?

http://theory.stanford.edu/~____amitp/GameProgramming/____AStarComparison.html
<http://theory.stanford.edu/%7E__amitp/GameProgramming/__AStarComparison.html>

<http://theory.stanford.edu/%__7Eamitp/GameProgramming/__AStarComparison.html

<http://theory.stanford.edu/%7Eamitp/GameProgramming/AStarComparison.html>>

Do you see why? and specifically why it matter for this
project?

-Steve

On 4/24/2013 9:10 PM, Mukul priya wrote:

**Name:Mukul Priya

*Country:*India

School and degree: International Institute Of Information

Technology-Hyderabad ,

B.Tech + Masters in
computer
Science And
Engineering

Email:mukul2047@gmail.com
mailto:[mukul2047@gmail.com](mailto:mukul2047@gmail.com) <mailto:mukul2047@gmail.com
mailto:[mukul2047@gmail.com](mailto:mukul2047@gmail.com)>
<mailto:mukul2047@gmail.com
mailto:[mukul2047@gmail.com](mailto:mukul2047@gmail.com) <mailto:mukul2047@gmail.com
mailto:[mukul2047@gmail.com](mailto:mukul2047@gmail.com)>>

Phone:+91 9885991061

OSGeo project(s):pgRouting

Title: A partitioned approach to on demand increment
graph
assembly
for pgRouting.

Describe your idea
1. Introduction

pgRouting has been working towards providing
routing
functionality on a PostGis/PostgreSql Geo spatial

database. It already has support for shortest path
algorithm
like
astar ,dijkstra , tdsp and trsp .But for a very

large network, routing becomes time consuming. Network
partitioning
is one such way which can prove to

be helpful in improving the overall time efficiency
of routing
querries. The main idea here is to first partition

the whole network using a Quad tree approach and
when the
shortest
path is computed these partitions are

loaded on demand. hence , there is an on demand
incremental
graph
generation.

The project aims at designing and implementing a
Shortest Path
algorithm on an on demand incremental

Graph using a network partitioning approach.

2. Background

Considering the present status where pgRouting has
support for
shortest path algorithm like astar etc.

Looking at their implementation details we can
observe that
the graph
is configured dynamically for all

of them before computation.My proposal will also be
on the
same track
and for very large networks

where the distance between source and destination
can be
very large ,
the response time will be

significantly lesser and memory wise too it will be
lot more
efficient. Presently they don’t use any partitioning

approach so it will prove to be a good addition to their
support for
shortest past algorithms.

3. The idea

There are two major components of my idea .

Network Partitioning

For this part we can use a quad tree approach.
Say , we
start
with a square and a condition like maximum

number of nodes that can reside in a square .
if the
number of
nodes in the square is greater than the max

condition we further quarter it into four
squares and
allot the
nodes appropriately to each of them.All these

squares can be called grids and they all will
be addressed
uniquely using a grid cell number .Each node

will be assigned a grid cell number based on
the grid
they are
lying inside.

We will have data structures to address
edges as
they can
remain contained in either one grid cell

or span across a number of grid cells.the
idea is to
first flag
such edges and store the grid cell numbers

of the grids that the edge crosses/intersects.

On demand graph generation and Routing.

The idea here is to first identify the
grid cell
initially and then fetch the edges that are associated with

that grid. These are the edges that will get
appended
to the
present graph and the graph will keep growing

dynamically this way. we will have appropriate
database
tables
addressing the above issue such that

we are able to fetch the required edges
quickly using a
database querry.

The implementation details for the above are :

we will first partition the whole graph using
the quad tree
approach and each node/vertex will be assigned

a grid cell number so we can have database
table for the
assigned nodes and edges like :

CREATE TABLE vertex{

id Node_id \
unique
for each
node.

cell grid_cell_number; \ the
grid in
which the
node lies.

geometry;

}

CREATE TABLE edge {

int id ;

Int node_a;

int node_b; \ the connecting nodes

// we can have other parameters like
traversal cost
and return
cost.

}

using the tables we can then fetch the
edges form
edge table
using simple database querry once

we are provided with the grid cell number very easily.

In short the summary of the whole idea is :

Step1: Fetch the start node , get the related Grid cell
number.

Step 2: Increment the graph by fetching all the items
related to
that grid.

Step3 : Check for boundary nodes ( this is done while
we are
partitioning) or target node .

Step 4: On hitting a boundary node

{

check if the connected grid is
loaded and
continue if
it is

or we extend the graph with the new
grid and
continue
with the routing;

}

or On hitting the target Node

{

stop;

}

4. Project plan

I will have about 12 weeks to implement the
project. The
tentative
schedule is as follows:

Before 17th June : Get familiar with the development
environment
of pgRouting and test some demos.

week 1-2: Discuss and Define the various data
structures
and data
table that will be required.Prepare the

Overall implementation
architecture.

week 3-4- Discuss and Implement network
partitioning
using quad
tree.

week 5-8 -Start coding for on demand graph
generation and
routing
using Dijkstra. In between Prepare mid-term

report.

week 9 - Integration with pgrouting .

week 10-12- Testing and Bug fixing. Draft Final
report and
documentation.

  1. Future ideas / How can your idea be expanded? *

It can be integrated with other shortest path
algorithms
like
astar etc. which pgrouitng provides.For time dependent

shortest path computation, it will greatly reduce the
updating cost
as we will be updating the cost of only those edges

that are contained in the grid cells that are loaded.

In route nearest neigbour querries can also be
implemented using
the partitioning approach.Overall we can

expand this approach to various other algorithms.

Explain how your SoC task would benefit the OSGeo member
project and
more generally the OSGeo Foundation as a whole:

The proposed idea will significantly improve the
performance of
shortest path finding algorithms.This will have a

positive effect on the user base of pgRouting. For
various
software
paltforms or applications that are using this library ,

the response time will significantly improve.

Please provide details of general computing experience:
*

I generally use ubuntu ( 12.04) for all my academic
purposes and
windows
7 for entertainment only. I am familiar with Fedora also.

C++ is the language that i use most ( programming
purposes). For
implementing various course projects i have used C++
,python
,Java and
matlab.

I have no experience with hardware. The only experience
that i
had with
networking was during my computer network course.

Please provide details of previous GIS experience:*

I am a part of “Lab for Spatial Informatics” which is
the only
lab in
India devoted to GIS applications and learning. I am
familiar
with and
have used almost all the open source GIS platforms like
Quantum ,
OpenJump, ILwis,Grass. We have our own rendering
platform that was
developed by our lab.(LSI viewer)

Please provide details of any previous involvement
with GIS
programming
and other software programming:

I am very much familiar with Gdal/OGR as i used it
extensively
while
implementing an outsourced project of Honeywell

Technology . I have played a lot with ESRI shape files.

Please tell us why you are interested in GIS and open
source
software:

I was very impressed with google earth when it was
launched way
back in
2004.GIS platforms like quantum and Openjump were
introduced to
me when
i was in my second year and then i joined Lab for spatial
informatics
that is in our college based on my interest in this area.

open source platforms provide an opportunity to learn .
The best
part is
you can always create or develop something that you are
interested in
and there are people who will always be there to help
you if you
are stuck.

Please tell us why you are interested in working for
OSGeo and the
software project you have selected:*

It will be huge learning experience since i have been
using
platforms
like Qgis , Gdal ,PostGis etc which come under Osgeo

I chose pgrouting because the algorithms that they have
implemented are
related to my masters topic and it will be great if i
get an insight
about how these were implemented on a much larger scale.

Please tell us why you are interested in your specific
coding
project:

Implementing routing algorithms for real world networks is
actually very
challenging.its a challenge to come up with good
approaches so
that the
computation cost and response time is both reduced.

Would your application contribute to your ongoing
studies/degree? If
so, how?

I am pursuing my Masters and my topic is closely
related to my
proposal
. If the results are impressive , i might get a
publication in
this area.

Please explain how you intend to continue being an
active member of
your project and/or OSGeo AFTER the summer is over:

I was always interested in open source programming but
never
knew where
to start . GSOC provides an opportunity for beginners
like me
to take a
dive in the area open source programming. i have other
ideas like
implementing IRNN ( In route nearest neighbour
querries) which
can be
implemented within pgRouting.I have other intentions like
working for
bigger projects like Quantum Gis or Grass.I will be
contributing
to the
community forum and will always try to improve things.

Do you understand this is a serious commitment,
equivalent to a
full-time paid summer internship or summer job?

Yes, I understand that this is a serious commitment and
will try
to give
my best and work in a professional manner.

Do you have any known time conflicts during the
official coding
period?
(June 17 to Sept. 27)

No .

On Thu, Apr 25, 2013 at 12:47 AM, Stephen Woodbridge
<woodbri@swoodbridge.com
mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)
<mailto:woodbri@swoodbridge.__com mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)>

<mailto:woodbri@swoodbridge.
mailto:[woodbri@swoodbridge](mailto:woodbri@swoodbridge).____com

<mailto:woodbri@swoodbridge.__com
mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)>>> wrote:

On 4/24/2013 2:34 PM, Mukul priya wrote:

Hi Steve and Daniel ,

I have posted my proposal on Melange Gsoc
system. Do
have a look
at it.
Waiting for feedback and suggestions.

Can you post a link to your proposal? or the text
of it
here also. I
can never find anything in Melange or I may not have
visibility to
it yet as I just applied as a mentor.

Thanks,
-Steve

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
<mailto:pgrouting-dev@lists.__osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)>

<mailto:pgrouting-dev@lists.
mailto:[pgrouting-dev@lists](mailto:pgrouting-dev@lists).____osgeo.org <http://osgeo.org>
<mailto:pgrouting-dev@lists.__osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)>>
http://lists.osgeo.org/______mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev>

<http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>__>

<http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>

<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>>>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
<mailto:pgrouting-dev@lists.__osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)>
http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>

<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>__>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
<mailto:pgrouting-dev@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)>
http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>
<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

11

Hi Mukul,

I think your proposal looks good. Daniel may have some additional comment. At this point if you have time, you might want to start with getting a github account, forking the pgrouting project, making sure you can build the existing project and install it under pg 9.2.

Regarding the Astar algorithm, you might want to look at implementing your own algorithm unless you want to try and work with the existing Boost code as this might be easier in the long run. Either way some research now, might help you with your planning later. This would allow you to work out all the basics of working in our environment and give you a head start. In the past the most successful and less stressed projects have been those that took an interest early on as these details can be frustrating and time consuming. This is totally at you option because the proposal has not been accepted yet.

Thank you putting together an interesting proposal that would add value to the project.

-Steve

On 4/27/2013 6:29 AM, Mukul priya wrote:

Hi steve , i have edited my proposal based on our previous discussion (
added some lines about Astar) .meanwhile do suggest if there is scope of
some improvement .

Thanks

Mukul

On Thu, Apr 25, 2013 at 11:22 PM, Mukul priya <mukul2047@gmail.com
<mailto:mukul2047@gmail.com>> wrote:

    Thanks Steve will add a few lines to my proposal explaining the
    reason behind opting Astar.

    Mukul

    On Thu, Apr 25, 2013 at 8:55 PM, Stephen Woodbridge
    <woodbri@swoodbridge.com <mailto:woodbri@swoodbridge.com>> wrote:

        On 4/25/2013 11:06 AM, Mukul priya wrote:

            How much of the network do you have to explore using each
            algorithm?

            This will be reduced significantly while using Astar as we
            will have a
            fair bit of idea about the direction towards which we should
            proceed.

            How does this impact the number of grids you have to load?

            Once we have an idea about the direction towards which we
            should proceed
            , only those grids will be loaded. This will result in
            loading of less
            number of grids.

            How does this impact your proposal?
            The basic motivation behind the proposal is to make shortest
            path
            computation faster. Number of database querry will be
            reduced as we will
            be fetching lesser number of grids. This will have a
            positive effect on
            computation time.

        Right, so in your proposal, you want to be clear that the
        benefit will be achieved using astar or another algorithm with a
        heuristic and not dijkstra. I understand that "shortest path" is
        a generic reference to all of these algorithms, but the only
        ones that will benefit from this approach will be ones with a
        heuristic that allow us to explore only a subset the overall
        bounding box of edges that we might otherwise use as input. So
        it is best to be clear on these points.

        -Steve

            On Thu, Apr 25, 2013 at 7:07 PM, Stephen Woodbridge
            <woodbri@swoodbridge.com <mailto:woodbri@swoodbridge.com>
            <mailto:woodbri@swoodbridge.__com
            <mailto:woodbri@swoodbridge.com>>> wrote:

                 On 4/25/2013 12:26 AM, Mukul priya wrote:

                     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.

                     Although do point out the advantages it has in real
            life road
                     network
                     and its importance to my proposal.

                 How much of the network do you have to explore using
            each algorithm?
                 How does this impact the number of grids you have to load?
                 How does this impact your proposal?

                 -Steve

                     On Thu, Apr 25, 2013 at 7:43 AM, Stephen Woodbridge
                     <woodbri@swoodbridge.com
            <mailto:woodbri@swoodbridge.com>
            <mailto:woodbri@swoodbridge.__com
            <mailto:woodbri@swoodbridge.com>>
                     <mailto:woodbri@swoodbridge.
            <mailto:woodbri@swoodbridge.>____com
                     <mailto:woodbri@swoodbridge.__com
            <mailto:woodbri@swoodbridge.com>>>> wrote:

                          Hi Mukul,

                          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.

                          Are you familiar with how these are different?
            http://theory.stanford.edu/~______amitp/GameProgramming/______AStarComparison.html
            <http://theory.stanford.edu/~____amitp/GameProgramming/____AStarComparison.html&gt;

            <http://theory.stanford.edu/%\_\_7E\_\_amitp/GameProgramming/\_\_\_\_AStarComparison\.html
            <http://theory.stanford.edu/~__amitp/GameProgramming/__AStarComparison.html&gt;&gt;

            <http://theory.stanford.edu/%\_\_\_\_7Eamitp/GameProgramming/\_\_\_\_AStarComparison\.html
            <http://theory.stanford.edu/%\_\_7Eamitp/GameProgramming/\_\_AStarComparison\.html&gt;

            <http://theory.stanford.edu/%\_\_7Eamitp/GameProgramming/\_\_AStarComparison\.html
            <http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html&gt;&gt;&gt;

                          Do you see why? and specifically why it matter
            for this
                     project?

                          -Steve

                          On 4/24/2013 9:10 PM, Mukul priya wrote:

                              ***Name*:Mukul Priya

                              *Country:*India

                              *School and degree*: International
            Institute Of Information

                              Technology-Hyderabad ,

                                                               B.Tech +
            Masters in
                     computer
                              Science And
                              Engineering

                              *Email*:mukul2047@gmail.com
            <mailto:mukul2047@gmail.com>
                     <mailto:mukul2047@gmail.com
            <mailto:mukul2047@gmail.com>> <mailto:mukul2047@gmail.com
            <mailto:mukul2047@gmail.com>
                     <mailto:mukul2047@gmail.com
            <mailto:mukul2047@gmail.com>>>
                              <mailto:mukul2047@gmail.com
            <mailto:mukul2047@gmail.com>
                     <mailto:mukul2047@gmail.com
            <mailto:mukul2047@gmail.com>> <mailto:mukul2047@gmail.com
            <mailto:mukul2047@gmail.com>
                     <mailto:mukul2047@gmail.com
            <mailto:mukul2047@gmail.com>>>>

                              *Phone*:+91 9885991061

                              *OSGeo project(s*):pgRouting

                              *Title:* A partitioned approach to on
            demand increment
                     graph
                              assembly
                              for pgRouting.

                              *Describe your idea*
                              *1. Introduction*

                                       pgRouting has been working
            towards providing
                     routing
                              functionality on a PostGis/PostgreSql Geo
            spatial

                                  database. It already has support for
            shortest path
                     algorithm
                              like
                              astar ,dijkstra , tdsp and trsp .But for a
            very

                                  large network, routing becomes time
            consuming. Network
                              partitioning
                              is one such way which can prove to

                                  be helpful in improving the overall
            time efficiency
                     of routing
                              querries. The main idea here is to first
            partition

                                  the whole network using a Quad tree
            approach and
                     when the
                              shortest
                              path is computed these partitions are

                                  loaded on demand. hence , there is an
            on demand
                     incremental
                              graph
                              generation.

                                       The project aims at designing and
            implementing a
                              Shortest Path
                              algorithm on an on demand incremental

                                    Graph using a network partitioning
            approach.

                              *2. Background*

                                       Considering the present status
            where pgRouting has
                              support for
                              shortest path algorithm like astar etc.

                                 Looking at their implementation details
            we can
                     observe that
                              the graph
                              is configured dynamically for all

                                 of them before computation.My proposal
            will also be
                     on the
                              same track
                              and for very large networks

                                 where the distance between source and
            destination
                     can be
                              very large ,
                              the response time will be

                                 significantly lesser and memory wise
            too it will be
                     lot more
                              efficient. Presently they don't use any
            partitioning

                                 approach so it will prove to be a good
            addition to their
                              support for
                              shortest past algorithms.

                              *3. The idea*

                                   There are two major components of my
            idea .

                                 *

                                   *Network Partitioning*

                                       For this part we can use a quad
            tree approach.
                     Say , we
                              start
                              with a square and a condition like maximum

                                       number of nodes that can reside
            in a square .
                     if the
                              number of
                              nodes in the square is greater than the max

                                       condition we further quarter it
            into four
                     squares and
                              allot the
                              nodes appropriately to each of them.All these

                                       squares can be called grids and
            they all will
                     be addressed
                              uniquely using a grid cell number .Each node

                                       will be assigned a grid cell
            number based on
                     the grid
                              they are
                              lying inside.

                                              We will have data
            structures to address
                     edges as
                              they can
                              remain contained in either one grid cell

                                        or span across a number of grid
            cells.the
                     idea is to
                              first flag
                              such edges and store the grid cell numbers

                                        of the grids that the edge
            crosses/intersects.

                                 *

                                   *On demand graph generation and Routing.*

                                               The idea here is to first
            identify the
                     grid cell
                              initially and then fetch the edges that
            are associated with

                                       that grid. These are the edges
            that will get
                     appended
                              to the
                              present graph and the graph will keep growing

                                       dynamically this way. we will
            have appropriate
                     database
                              tables
                              addressing the above issue such that

                                       we are able to fetch the required
            edges
                     quickly using a
                              database querry.

                                        The implementation details for
            the above are :

                                       we will first partition the whole
            graph using
                     the quad tree
                              approach and each node/vertex will be assigned

                                       a grid cell number so we can have
              database
                     table for the
                              assigned nodes and edges like :

                                       CREATE TABLE vertex{

                                        id Node_id
                     \\
                       unique
                              for each
                              node.

                                        cell grid_cell_number;
                 \\ the
                     grid in
                              which the
                              node lies.

                                         geometry;

                                         }

                                         CREATE TABLE edge {

                                          int id ;

                                          Int node_a;

                                           int node_b; \\ the
            connecting nodes

                                    // we can have other parameters like
                     traversal cost
                              and return
                              cost.

                                         }

                                          using the tables we can then
            fetch the
                     edges form
                              edge table
                                 using simple database querry once

                                 we are provided with the grid cell
            number very easily.

                                 In short the summary of the whole idea is :

                              Step1: Fetch the start node , get the
            related Grid cell
                     number.

                              Step 2: Increment the graph by fetching
            all the items
                     related to
                              that grid.

                              Step3 : Check for boundary nodes ( this
            is done while
                     we are
                              partitioning) or target node .

                              Step 4: On hitting a boundary node

                                               {

                                                 check if the connected
            grid is
                     loaded and
                              continue if
                              it is

                                                 or we extend the graph
            with the new
                     grid and
                              continue
                              with the routing;

                                                }

                                           or On hitting the target Node

                                             {

                                                        stop;

                                              }

                              *4. Project plan*

                                     I will have about 12 weeks to
            implement the
                     project. The
                              tentative
                              schedule is as follows:

                                     Before 17th June : Get familiar
            with the development
                              environment
                              of pgRouting and test some demos.

                                     week 1-2: Discuss and Define the
            various data
                     structures
                              and data
                              table that will be required.Prepare the

                                                     Overall implementation
                       architecture.

                                     week 3-4- Discuss and Implement
            network
                     partitioning
                              using quad
                              tree.

                                     week 5-8 -Start coding for on
            demand graph
                     generation and
                              routing
                              using Dijkstra. In between Prepare mid-term

                                                       report.

                                     week 9 - Integration with pgrouting .

                                     week 10-12- Testing and Bug fixing.
            Draft Final
                     report and
                              documentation.

                              *
                                 5. Future ideas / How can your idea be
            expanded? *

                                      It can be integrated with other
            shortest path
                     algorithms
                              like
                              astar etc. which pgrouitng provides.For
            time dependent

                                    shortest path computation, it will
            greatly reduce the
                              updating cost
                              as we will be updating the cost of only
            those edges

                                    that are contained in the grid cells
            that are loaded.

                                     In route nearest neigbour querries
            can also be
                              implemented using
                              the partitioning approach.Overall we can

                                     expand this approach to various
            other algorithms.

                              *Explain how your SoC task would benefit
            the OSGeo member
                              project and
                              more generally the OSGeo Foundation as a
            whole:*

                                    The proposed idea will significantly
            improve the
                              performance of
                              shortest path finding algorithms.This will
            have a

                                  positive effect on the user base of
            pgRouting. For
                     various
                              software
                              paltforms or applications that are using
            this library ,

                                  the response time will significantly
            improve.

                              *

                              Please provide details of general
            computing experience:
                              *

                              I generally use ubuntu ( 12.04) for all my
            academic
                     purposes and
                              windows
                              7 for entertainment only. I am familiar
            with Fedora also.

                              C++ is the language that i use most (
            programming
                     purposes). For
                              implementing various course projects i
            have used C++
                     ,python
                              ,Java and
                              matlab.

                              I have no experience with hardware. The
            only experience
                     that i
                              had with
                              networking was during my computer network
            course.

                              *
                              Please provide details of previous GIS
            experience:*

                              I am a part of "Lab for Spatial
            Informatics" which is
                     the only
                              lab in
                              India devoted to GIS applications and
            learning. I am
                     familiar
                              with and
                              have used almost all the open source GIS
            platforms like
                     Quantum ,
                              OpenJump, ILwis,Grass. We have our own
            rendering
                     platform that was
                              developed by our lab.(LSI viewer)

                              *Please provide details of any previous
            involvement
                     with GIS
                              programming
                              and other software programming:*

                              I am very much familiar with Gdal/OGR as
            i used it
                     extensively
                              while
                              implementing an outsourced project of
            Honeywell

                              Technology . I have played a lot with ESRI
            shape files.

                              *Please tell us why you are interested in
            GIS and open
                     source
                              software:*

                              I was very impressed with google earth
            when it was
                     launched way
                              back in
                              2004.GIS platforms like quantum and
            Openjump were
                     introduced to
                              me when
                              i was in my second year and then i joined
            Lab for spatial
                              informatics
                              that is in our college based on my
            interest in this area.

                              open source platforms provide an
            opportunity to learn .
                     The best
                              part is
                              you can always create or develop something
            that you are
                              interested in
                              and there are people who will always be
            there to help
                     you if you
                              are stuck.

                              *

                              Please tell us why you are interested in
            working for
                     OSGeo and the
                              software project you have selected:*

                              It will be huge learning experience since
            i have been
                     using
                              platforms
                              like Qgis , Gdal ,PostGis etc which come
            under Osgeo

                              I chose pgrouting because the algorithms
            that they have
                              implemented are
                              related to my masters topic and it will be
            great if i
                     get an insight
                              about how these were implemented on a much
            larger scale.

                              *Please tell us why you are interested in
            your specific
                     coding
                              project:*

                              Implementing routing algorithms for real
            world networks is
                              actually very
                              challenging.its a challenge to come up
            with good
                     approaches so
                              that the
                              computation cost and response time is both
            reduced.

                              *Would your application contribute to your
            ongoing
                              studies/degree? If
                              so, how?*

                              I am pursuing my Masters and my topic is
            closely
                     related to my
                              proposal
                              . If the results are impressive , i might
            get a
                     publication in
                              this area.

                              *Please explain how you intend to continue
            being an
                     active member of
                              your project and/or OSGeo AFTER the summer
            is over:*

                              I was always interested in open source
            programming but
                     never
                              knew where
                              to start . GSOC provides an opportunity
            for beginners
                     like me
                              to take a
                              dive in the area open source programming.
            i have other
                     ideas like
                              implementing IRNN ( In route nearest neighbour
                     querries) which
                              can be
                              implemented within pgRouting.I have other
            intentions like
                              working for
                              bigger projects like Quantum Gis or
            Grass.I will be
                     contributing
                              to the
                              community forum and will always try to
            improve things.

                              *Do you understand this is a serious
            commitment,
                     equivalent to a
                              full-time paid summer internship or summer
            job?*

                              Yes, I understand that this is a serious
            commitment and
                     will try
                              to give
                              my best and work in a professional manner.

                              *Do you have any known time conflicts
            during the
                     official coding
                              period?
                              (June 17 to Sept. 27)*

                              No .

                              On Thu, Apr 25, 2013 at 12:47 AM, Stephen
            Woodbridge
                              <woodbri@swoodbridge.com
            <mailto:woodbri@swoodbridge.com>
                     <mailto:woodbri@swoodbridge.__com
            <mailto:woodbri@swoodbridge.com>>
                     <mailto:woodbri@swoodbridge.
            <mailto:woodbri@swoodbridge.>____com
            <mailto:woodbri@swoodbridge.__com
            <mailto:woodbri@swoodbridge.com>>>
                              <mailto:woodbri@swoodbridge
            <mailto:woodbri@swoodbridge>.
                     <mailto:woodbri@swoodbridge
            <mailto:woodbri@swoodbridge>.>______com

                              <mailto:woodbri@swoodbridge.
            <mailto:woodbri@swoodbridge.>____com
                     <mailto:woodbri@swoodbridge.__com
            <mailto:woodbri@swoodbridge.com>>>>> wrote:

                                   On 4/24/2013 2:34 PM, Mukul priya wrote:

                                       Hi Steve and Daniel ,

                                       I have posted my proposal on
            Melange Gsoc
                     system. Do
                              have a look
                                       at it.
                                       Waiting for feedback and suggestions.

                                   Can you post a link to your proposal?
            or the text
                     of it
                              here also. I
                                   can never find anything in Melange or
            I may not have
                              visibility to
                                   it yet as I just applied as a mentor.

                                   Thanks,
                                      -Steve

            _______________________________________________________

                                   pgrouting-dev mailing list
            pgrouting-dev@lists.osgeo.org
            <mailto:pgrouting-dev@lists.osgeo.org>
            <mailto:pgrouting-dev@lists.__osgeo.org
            <mailto:pgrouting-dev@lists.osgeo.org>>
                              <mailto:pgrouting-dev@lists.
            <mailto:pgrouting-dev@lists.>____osgeo.org <http://osgeo.org>
                     <mailto:pgrouting-dev@lists.__osgeo.org
            <mailto:pgrouting-dev@lists.osgeo.org>>>
                              <mailto:pgrouting-dev@lists
            <mailto:pgrouting-dev@lists>.
                     <mailto:pgrouting-dev@lists
            <mailto:pgrouting-dev@lists>.>______osgeo.org
            <http://osgeo.org> <http://osgeo.org>
                              <mailto:pgrouting-dev@lists.
            <mailto:pgrouting-dev@lists.>____osgeo.org <http://osgeo.org>
                     <mailto:pgrouting-dev@lists.__osgeo.org
            <mailto:pgrouting-dev@lists.osgeo.org>>>>
            http://lists.osgeo.org/________mailman/listinfo/pgrouting-dev <http://lists.osgeo.org/______mailman/listinfo/pgrouting-dev&gt;

            <http://lists.osgeo.org/______mailman/listinfo/pgrouting-dev
            <http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev&gt;\_\_&gt;

            <http://lists.osgeo.org/______mailman/listinfo/pgrouting-dev
            <http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev&gt;

            <http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
            <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev&gt;\_\_&gt;\_\_&gt;

            <http://lists.osgeo.org/______mailman/listinfo/pgrouting-dev
            <http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev&gt;

            <http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
            <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev&gt;\_\_&gt;

            <http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
            <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev&gt;

            <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
            <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;\_\_&gt;\_\_&gt;\_\_&gt;

              _____________________________________________________
                              pgrouting-dev mailing list
            pgrouting-dev@lists.osgeo.org
            <mailto:pgrouting-dev@lists.osgeo.org>
                     <mailto:pgrouting-dev@lists.__osgeo.org
            <mailto:pgrouting-dev@lists.osgeo.org>>
                     <mailto:pgrouting-dev@lists.
            <mailto:pgrouting-dev@lists.>____osgeo.org <http://osgeo.org>
                     <mailto:pgrouting-dev@lists.__osgeo.org
            <mailto:pgrouting-dev@lists.osgeo.org>>>
            http://lists.osgeo.org/______mailman/listinfo/pgrouting-dev
            <http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev&gt;

            <http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
            <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev&gt;\_\_&gt;

            <http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
            <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev&gt;

            <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
            <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;\_\_&gt;\_\_&gt;

              _____________________________________________________
                          pgrouting-dev mailing list
            pgrouting-dev@lists.osgeo.org
            <mailto:pgrouting-dev@lists.osgeo.org>
                     <mailto:pgrouting-dev@lists.__osgeo.org
            <mailto:pgrouting-dev@lists.osgeo.org>>
                     <mailto:pgrouting-dev@lists.
            <mailto:pgrouting-dev@lists.>____osgeo.org <http://osgeo.org>
                     <mailto:pgrouting-dev@lists.__osgeo.org
            <mailto:pgrouting-dev@lists.osgeo.org>>>
            http://lists.osgeo.org/______mailman/listinfo/pgrouting-dev
            <http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev&gt;

            <http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
            <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev&gt;\_\_&gt;

              <http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
            <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev&gt;

            <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
            <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;\_\_&gt;\_\_&gt;

                     ___________________________________________________
                     pgrouting-dev mailing list
            pgrouting-dev@lists.osgeo.org
            <mailto:pgrouting-dev@lists.osgeo.org>
            <mailto:pgrouting-dev@lists.__osgeo.org
            <mailto:pgrouting-dev@lists.osgeo.org>>
            http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
            <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev&gt;

            <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
            <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;\_\_&gt;

                 ___________________________________________________
                 pgrouting-dev mailing list
            pgrouting-dev@lists.osgeo.org
            <mailto:pgrouting-dev@lists.osgeo.org>
            <mailto:pgrouting-dev@lists.__osgeo.org
            <mailto:pgrouting-dev@lists.osgeo.org>>
            http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
            <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev&gt;

            <http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
            <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;\_\_&gt;

            _________________________________________________
            pgrouting-dev mailing list
            pgrouting-dev@lists.osgeo.org
            <mailto:pgrouting-dev@lists.osgeo.org>
            http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
            <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;

        _________________________________________________
        pgrouting-dev mailing list
        pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
        http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
        <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;

_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

12

Thanks Steve . i will go through the steps that you have mentioned once i am free from all my academic commitments by the end of this month ( in 2-3 days at max).

-Mukul

···

On Sat, Apr 27, 2013 at 6:59 PM, Stephen Woodbridge <woodbri@swoodbridge.com> wrote:

Hi Mukul,

I think your proposal looks good. Daniel may have some additional comment. At this point if you have time, you might want to start with getting a github account, forking the pgrouting project, making sure you can build the existing project and install it under pg 9.2.

Regarding the Astar algorithm, you might want to look at implementing your own algorithm unless you want to try and work with the existing Boost code as this might be easier in the long run. Either way some research now, might help you with your planning later. This would allow you to work out all the basics of working in our environment and give you a head start. In the past the most successful and less stressed projects have been those that took an interest early on as these details can be frustrating and time consuming. This is totally at you option because the proposal has not been accepted yet.

Thank you putting together an interesting proposal that would add value to the project.

-Steve

On 4/27/2013 6:29 AM, Mukul priya wrote:

Hi steve , i have edited my proposal based on our previous discussion (
added some lines about Astar) .meanwhile do suggest if there is scope of
some improvement .

Thanks

Mukul

On Thu, Apr 25, 2013 at 11:22 PM, Mukul priya <mukul2047@gmail.com

mailto:[mukul2047@gmail.com](mailto:mukul2047@gmail.com)> wrote:

Thanks Steve will add a few lines to my proposal explaining the
reason behind opting Astar.

Mukul

On Thu, Apr 25, 2013 at 8:55 PM, Stephen Woodbridge

<woodbri@swoodbridge.com mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)> wrote:

On 4/25/2013 11:06 AM, Mukul priya wrote:

How much of the network do you have to explore using each
algorithm?

This will be reduced significantly while using Astar as we
will have a
fair bit of idea about the direction towards which we should
proceed.

How does this impact the number of grids you have to load?

Once we have an idea about the direction towards which we
should proceed
, only those grids will be loaded. This will result in
loading of less
number of grids.

How does this impact your proposal?
The basic motivation behind the proposal is to make shortest
path
computation faster. Number of database querry will be
reduced as we will
be fetching lesser number of grids. This will have a
positive effect on
computation time.

Right, so in your proposal, you want to be clear that the
benefit will be achieved using astar or another algorithm with a
heuristic and not dijkstra. I understand that “shortest path” is
a generic reference to all of these algorithms, but the only
ones that will benefit from this approach will be ones with a
heuristic that allow us to explore only a subset the overall
bounding box of edges that we might otherwise use as input. So
it is best to be clear on these points.

-Steve

On Thu, Apr 25, 2013 at 7:07 PM, Stephen Woodbridge
<woodbri@swoodbridge.com mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)

<mailto:woodbri@swoodbridge.__com
mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)>> wrote:

On 4/25/2013 12:26 AM, Mukul priya wrote:

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.

Although do point out the advantages it has in real
life road
network
and its importance to my proposal.

How much of the network do you have to explore using
each algorithm?
How does this impact the number of grids you have to load?
How does this impact your proposal?

-Steve

On Thu, Apr 25, 2013 at 7:43 AM, Stephen Woodbridge
<woodbri@swoodbridge.com
mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)
<mailto:woodbri@swoodbridge.__com
mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)>

<mailto:woodbri@swoodbridge.
mailto:[woodbri@swoodbridge](mailto:woodbri@swoodbridge).____com
<mailto:woodbri@swoodbridge.__com
mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)>>> wrote:

Hi Mukul,

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.

Are you familiar with how these are different?

http://theory.stanford.edu/~______amitp/GameProgramming/______AStarComparison.html
<http://theory.stanford.edu/%7E____amitp/GameProgramming/____AStarComparison.html>

<http://theory.stanford.edu/%__7E__amitp/GameProgramming/____AStarComparison.html
<http://theory.stanford.edu/%7E__amitp/GameProgramming/__AStarComparison.html>>

<http://theory.stanford.edu/%____7Eamitp/GameProgramming/____AStarComparison.html
<http://theory.stanford.edu/%__7Eamitp/GameProgramming/__AStarComparison.html>

<http://theory.stanford.edu/%__7Eamitp/GameProgramming/__AStarComparison.html
<http://theory.stanford.edu/%7Eamitp/GameProgramming/AStarComparison.html>>>

Do you see why? and specifically why it matter
for this
project?

-Steve

On 4/24/2013 9:10 PM, Mukul priya wrote:

**Name:Mukul Priya

*Country:*India

School and degree: International
Institute Of Information

Technology-Hyderabad ,

B.Tech +
Masters in
computer
Science And
Engineering

Email:mukul2047@gmail.com
mailto:[mukul2047@gmail.com](mailto:mukul2047@gmail.com)
<mailto:mukul2047@gmail.com
mailto:[mukul2047@gmail.com](mailto:mukul2047@gmail.com)> <mailto:mukul2047@gmail.com
mailto:[mukul2047@gmail.com](mailto:mukul2047@gmail.com)
<mailto:mukul2047@gmail.com
mailto:[mukul2047@gmail.com](mailto:mukul2047@gmail.com)>>
<mailto:mukul2047@gmail.com
mailto:[mukul2047@gmail.com](mailto:mukul2047@gmail.com)
<mailto:mukul2047@gmail.com
mailto:[mukul2047@gmail.com](mailto:mukul2047@gmail.com)> <mailto:mukul2047@gmail.com
mailto:[mukul2047@gmail.com](mailto:mukul2047@gmail.com)
<mailto:mukul2047@gmail.com
mailto:[mukul2047@gmail.com](mailto:mukul2047@gmail.com)>>>

Phone:+91 9885991061

OSGeo project(s):pgRouting

Title: A partitioned approach to on
demand increment
graph
assembly
for pgRouting.

Describe your idea
1. Introduction

pgRouting has been working
towards providing
routing
functionality on a PostGis/PostgreSql Geo
spatial

database. It already has support for
shortest path
algorithm
like
astar ,dijkstra , tdsp and trsp .But for a
very

large network, routing becomes time
consuming. Network
partitioning
is one such way which can prove to

be helpful in improving the overall
time efficiency
of routing
querries. The main idea here is to first
partition

the whole network using a Quad tree
approach and
when the
shortest
path is computed these partitions are

loaded on demand. hence , there is an
on demand
incremental
graph
generation.

The project aims at designing and
implementing a
Shortest Path
algorithm on an on demand incremental

Graph using a network partitioning
approach.

2. Background

Considering the present status
where pgRouting has
support for
shortest path algorithm like astar etc.

Looking at their implementation details
we can
observe that
the graph
is configured dynamically for all

of them before computation.My proposal
will also be
on the
same track
and for very large networks

where the distance between source and
destination
can be
very large ,
the response time will be

significantly lesser and memory wise
too it will be
lot more
efficient. Presently they don’t use any
partitioning

approach so it will prove to be a good
addition to their
support for
shortest past algorithms.

3. The idea

There are two major components of my
idea .

Network Partitioning

For this part we can use a quad
tree approach.
Say , we
start
with a square and a condition like maximum

number of nodes that can reside
in a square .
if the
number of
nodes in the square is greater than the max

condition we further quarter it
into four
squares and
allot the
nodes appropriately to each of them.All these

squares can be called grids and
they all will
be addressed
uniquely using a grid cell number .Each node

will be assigned a grid cell
number based on
the grid
they are
lying inside.

We will have data
structures to address
edges as
they can
remain contained in either one grid cell

or span across a number of grid
cells.the
idea is to
first flag
such edges and store the grid cell numbers

of the grids that the edge
crosses/intersects.

On demand graph generation and Routing.

The idea here is to first
identify the
grid cell
initially and then fetch the edges that
are associated with

that grid. These are the edges
that will get
appended
to the
present graph and the graph will keep growing

dynamically this way. we will
have appropriate
database
tables
addressing the above issue such that

we are able to fetch the required
edges
quickly using a
database querry.

The implementation details for
the above are :

we will first partition the whole
graph using
the quad tree
approach and each node/vertex will be assigned

a grid cell number so we can have
database
table for the
assigned nodes and edges like :

CREATE TABLE vertex{

id Node_id
\
unique
for each
node.

cell grid_cell_number;
\ the
grid in
which the
node lies.

geometry;

}

CREATE TABLE edge {

int id ;

Int node_a;

int node_b; \ the
connecting nodes

// we can have other parameters like
traversal cost
and return
cost.

}

using the tables we can then
fetch the
edges form
edge table
using simple database querry once

we are provided with the grid cell
number very easily.

In short the summary of the whole idea is :

Step1: Fetch the start node , get the
related Grid cell
number.

Step 2: Increment the graph by fetching
all the items
related to
that grid.

Step3 : Check for boundary nodes ( this
is done while
we are
partitioning) or target node .

Step 4: On hitting a boundary node

{

check if the connected
grid is
loaded and
continue if
it is

or we extend the graph
with the new
grid and
continue
with the routing;

}

or On hitting the target Node

{

stop;

}

4. Project plan

I will have about 12 weeks to
implement the
project. The
tentative
schedule is as follows:

Before 17th June : Get familiar
with the development
environment
of pgRouting and test some demos.

week 1-2: Discuss and Define the
various data
structures
and data
table that will be required.Prepare the

Overall implementation
architecture.

week 3-4- Discuss and Implement
network
partitioning
using quad
tree.

week 5-8 -Start coding for on
demand graph
generation and
routing
using Dijkstra. In between Prepare mid-term

report.

week 9 - Integration with pgrouting .

week 10-12- Testing and Bug fixing.
Draft Final
report and
documentation.

  1. Future ideas / How can your idea be
    expanded? *

It can be integrated with other
shortest path
algorithms
like
astar etc. which pgrouitng provides.For
time dependent

shortest path computation, it will
greatly reduce the
updating cost
as we will be updating the cost of only
those edges

that are contained in the grid cells
that are loaded.

In route nearest neigbour querries
can also be
implemented using
the partitioning approach.Overall we can

expand this approach to various
other algorithms.

Explain how your SoC task would benefit
the OSGeo member
project and
more generally the OSGeo Foundation as a
whole:

The proposed idea will significantly
improve the
performance of
shortest path finding algorithms.This will
have a

positive effect on the user base of
pgRouting. For
various
software
paltforms or applications that are using
this library ,

the response time will significantly
improve.

Please provide details of general
computing experience:
*

I generally use ubuntu ( 12.04) for all my
academic
purposes and
windows
7 for entertainment only. I am familiar
with Fedora also.

C++ is the language that i use most (
programming
purposes). For
implementing various course projects i
have used C++
,python
,Java and
matlab.

I have no experience with hardware. The
only experience
that i
had with
networking was during my computer network
course.

Please provide details of previous GIS
experience:*

I am a part of “Lab for Spatial
Informatics” which is
the only
lab in
India devoted to GIS applications and
learning. I am
familiar
with and
have used almost all the open source GIS
platforms like
Quantum ,
OpenJump, ILwis,Grass. We have our own
rendering
platform that was
developed by our lab.(LSI viewer)

Please provide details of any previous
involvement
with GIS
programming
and other software programming:

I am very much familiar with Gdal/OGR as
i used it
extensively
while
implementing an outsourced project of
Honeywell

Technology . I have played a lot with ESRI
shape files.

Please tell us why you are interested in
GIS and open
source
software:

I was very impressed with google earth
when it was
launched way
back in
2004.GIS platforms like quantum and
Openjump were
introduced to
me when
i was in my second year and then i joined
Lab for spatial
informatics
that is in our college based on my
interest in this area.

open source platforms provide an
opportunity to learn .
The best
part is
you can always create or develop something
that you are
interested in
and there are people who will always be
there to help
you if you
are stuck.

Please tell us why you are interested in
working for
OSGeo and the
software project you have selected:*

It will be huge learning experience since
i have been
using
platforms
like Qgis , Gdal ,PostGis etc which come
under Osgeo

I chose pgrouting because the algorithms
that they have
implemented are
related to my masters topic and it will be
great if i
get an insight
about how these were implemented on a much
larger scale.

Please tell us why you are interested in
your specific
coding
project:

Implementing routing algorithms for real
world networks is
actually very
challenging.its a challenge to come up
with good
approaches so
that the
computation cost and response time is both
reduced.

Would your application contribute to your
ongoing
studies/degree? If
so, how?

I am pursuing my Masters and my topic is
closely
related to my
proposal
. If the results are impressive , i might
get a
publication in
this area.

Please explain how you intend to continue
being an
active member of
your project and/or OSGeo AFTER the summer
is over:

I was always interested in open source
programming but
never
knew where
to start . GSOC provides an opportunity
for beginners
like me
to take a
dive in the area open source programming.
i have other
ideas like
implementing IRNN ( In route nearest neighbour
querries) which
can be
implemented within pgRouting.I have other
intentions like
working for
bigger projects like Quantum Gis or
Grass.I will be
contributing
to the
community forum and will always try to
improve things.

Do you understand this is a serious
commitment,
equivalent to a
full-time paid summer internship or summer
job?

Yes, I understand that this is a serious
commitment and
will try
to give
my best and work in a professional manner.

Do you have any known time conflicts
during the
official coding
period?
(June 17 to Sept. 27)

No .

On Thu, Apr 25, 2013 at 12:47 AM, Stephen
Woodbridge
<woodbri@swoodbridge.com
mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)
<mailto:woodbri@swoodbridge.__com
mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)>
<mailto:woodbri@swoodbridge.
mailto:[woodbri@swoodbridge](mailto:woodbri@swoodbridge).____com
<mailto:woodbri@swoodbridge.__com
mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)>>

<mailto:woodbri@swoodbridge
mailto:[woodbri@swoodbridge](mailto:woodbri@swoodbridge).
<mailto:woodbri@swoodbridge
mailto:[woodbri@swoodbridge](mailto:woodbri@swoodbridge).>______com

<mailto:woodbri@swoodbridge.
mailto:[woodbri@swoodbridge](mailto:woodbri@swoodbridge).____com
<mailto:woodbri@swoodbridge.__com
mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)>>>> wrote:

On 4/24/2013 2:34 PM, Mukul priya wrote:

Hi Steve and Daniel ,

I have posted my proposal on
Melange Gsoc
system. Do
have a look
at it.
Waiting for feedback and suggestions.

Can you post a link to your proposal?
or the text
of it
here also. I
can never find anything in Melange or
I may not have
visibility to
it yet as I just applied as a mentor.

Thanks,
-Steve

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
<mailto:pgrouting-dev@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)>
<mailto:pgrouting-dev@lists.
mailto:[pgrouting-dev@lists](mailto:pgrouting-dev@lists).____osgeo.org <http://osgeo.org>
<mailto:pgrouting-dev@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)>>

<mailto:pgrouting-dev@lists
mailto:[pgrouting-dev@lists](mailto:pgrouting-dev@lists).
<mailto:pgrouting-dev@lists
mailto:[pgrouting-dev@lists](mailto:pgrouting-dev@lists).>______osgeo.org
<http://osgeo.org> <http://osgeo.org>

<mailto:pgrouting-dev@lists.
mailto:[pgrouting-dev@lists](mailto:pgrouting-dev@lists).____osgeo.org <http://osgeo.org>
<mailto:pgrouting-dev@lists.__osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)>>>

http://lists.osgeo.org/________mailman/listinfo/pgrouting-dev <http://lists.osgeo.org/______mailman/listinfo/pgrouting-dev>

<http://lists.osgeo.org/______mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev>__>

<http://lists.osgeo.org/______mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev>

<http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev

<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>>>

<http://lists.osgeo.org/______mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev>

<http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>__>

<http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>

<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>>>__>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
<mailto:pgrouting-dev@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)>
<mailto:pgrouting-dev@lists.
mailto:[pgrouting-dev@lists](mailto:pgrouting-dev@lists).____osgeo.org <http://osgeo.org>
<mailto:pgrouting-dev@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)>>
http://lists.osgeo.org/______mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev>

<http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>__>

<http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>

<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>>>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
<mailto:pgrouting-dev@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)>
<mailto:pgrouting-dev@lists.
mailto:[pgrouting-dev@lists](mailto:pgrouting-dev@lists).____osgeo.org <http://osgeo.org>
<mailto:pgrouting-dev@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)>>
http://lists.osgeo.org/______mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev>

<http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>__>

<http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>

<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>>>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
<mailto:pgrouting-dev@lists.__osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)>
http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>

<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>__>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
<mailto:pgrouting-dev@lists.__osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)>
http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>

<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>__>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

13

Hi steve ,

I have forked the pgrouting project and cloned it to my local machine. My git username is “mukulpriya”. i will get through the installation process and post doubts in case i get stuck somewhere.

regards,

mukul

···

On Sat, Apr 27, 2013 at 7:32 PM, Mukul priya <mukul2047@gmail.com> wrote:

Thanks Steve . i will go through the steps that you have mentioned once i am free from all my academic commitments by the end of this month ( in 2-3 days at max).

-Mukul

On Sat, Apr 27, 2013 at 6:59 PM, Stephen Woodbridge <woodbri@swoodbridge.com> wrote:

Hi Mukul,

I think your proposal looks good. Daniel may have some additional comment. At this point if you have time, you might want to start with getting a github account, forking the pgrouting project, making sure you can build the existing project and install it under pg 9.2.

Regarding the Astar algorithm, you might want to look at implementing your own algorithm unless you want to try and work with the existing Boost code as this might be easier in the long run. Either way some research now, might help you with your planning later. This would allow you to work out all the basics of working in our environment and give you a head start. In the past the most successful and less stressed projects have been those that took an interest early on as these details can be frustrating and time consuming. This is totally at you option because the proposal has not been accepted yet.

Thank you putting together an interesting proposal that would add value to the project.

-Steve

On 4/27/2013 6:29 AM, Mukul priya wrote:

Hi steve , i have edited my proposal based on our previous discussion (
added some lines about Astar) .meanwhile do suggest if there is scope of
some improvement .

Thanks

Mukul

On Thu, Apr 25, 2013 at 11:22 PM, Mukul priya <mukul2047@gmail.com

mailto:[mukul2047@gmail.com](mailto:mukul2047@gmail.com)> wrote:

Thanks Steve will add a few lines to my proposal explaining the
reason behind opting Astar.

Mukul

On Thu, Apr 25, 2013 at 8:55 PM, Stephen Woodbridge

<woodbri@swoodbridge.com mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)> wrote:

On 4/25/2013 11:06 AM, Mukul priya wrote:

How much of the network do you have to explore using each
algorithm?

This will be reduced significantly while using Astar as we
will have a
fair bit of idea about the direction towards which we should
proceed.

How does this impact the number of grids you have to load?

Once we have an idea about the direction towards which we
should proceed
, only those grids will be loaded. This will result in
loading of less
number of grids.

How does this impact your proposal?
The basic motivation behind the proposal is to make shortest
path
computation faster. Number of database querry will be
reduced as we will
be fetching lesser number of grids. This will have a
positive effect on
computation time.

Right, so in your proposal, you want to be clear that the
benefit will be achieved using astar or another algorithm with a
heuristic and not dijkstra. I understand that “shortest path” is
a generic reference to all of these algorithms, but the only
ones that will benefit from this approach will be ones with a
heuristic that allow us to explore only a subset the overall
bounding box of edges that we might otherwise use as input. So
it is best to be clear on these points.

-Steve

On Thu, Apr 25, 2013 at 7:07 PM, Stephen Woodbridge
<woodbri@swoodbridge.com mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)

<mailto:woodbri@swoodbridge.__com
mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)>> wrote:

On 4/25/2013 12:26 AM, Mukul priya wrote:

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.

Although do point out the advantages it has in real
life road
network
and its importance to my proposal.

How much of the network do you have to explore using
each algorithm?
How does this impact the number of grids you have to load?
How does this impact your proposal?

-Steve

On Thu, Apr 25, 2013 at 7:43 AM, Stephen Woodbridge
<woodbri@swoodbridge.com
mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)
<mailto:woodbri@swoodbridge.__com
mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)>

<mailto:woodbri@swoodbridge.
mailto:[woodbri@swoodbridge](mailto:woodbri@swoodbridge).____com
<mailto:woodbri@swoodbridge.__com
mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)>>> wrote:

Hi Mukul,

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.

Are you familiar with how these are different?

http://theory.stanford.edu/~______amitp/GameProgramming/______AStarComparison.html
<http://theory.stanford.edu/%7E____amitp/GameProgramming/____AStarComparison.html>

<http://theory.stanford.edu/%__7E__amitp/GameProgramming/____AStarComparison.html
<http://theory.stanford.edu/%7E__amitp/GameProgramming/__AStarComparison.html>>

<http://theory.stanford.edu/%____7Eamitp/GameProgramming/____AStarComparison.html
<http://theory.stanford.edu/%__7Eamitp/GameProgramming/__AStarComparison.html>

<http://theory.stanford.edu/%__7Eamitp/GameProgramming/__AStarComparison.html
<http://theory.stanford.edu/%7Eamitp/GameProgramming/AStarComparison.html>>>

Do you see why? and specifically why it matter
for this
project?

-Steve

On 4/24/2013 9:10 PM, Mukul priya wrote:

**Name:Mukul Priya

*Country:*India

School and degree: International
Institute Of Information

Technology-Hyderabad ,

B.Tech +
Masters in
computer
Science And
Engineering

Email:mukul2047@gmail.com
mailto:[mukul2047@gmail.com](mailto:mukul2047@gmail.com)
<mailto:mukul2047@gmail.com
mailto:[mukul2047@gmail.com](mailto:mukul2047@gmail.com)> <mailto:mukul2047@gmail.com
mailto:[mukul2047@gmail.com](mailto:mukul2047@gmail.com)
<mailto:mukul2047@gmail.com
mailto:[mukul2047@gmail.com](mailto:mukul2047@gmail.com)>>
<mailto:mukul2047@gmail.com
mailto:[mukul2047@gmail.com](mailto:mukul2047@gmail.com)
<mailto:mukul2047@gmail.com
mailto:[mukul2047@gmail.com](mailto:mukul2047@gmail.com)> <mailto:mukul2047@gmail.com
mailto:[mukul2047@gmail.com](mailto:mukul2047@gmail.com)
<mailto:mukul2047@gmail.com
mailto:[mukul2047@gmail.com](mailto:mukul2047@gmail.com)>>>

Phone:+91 9885991061

OSGeo project(s):pgRouting

Title: A partitioned approach to on
demand increment
graph
assembly
for pgRouting.

Describe your idea
1. Introduction

pgRouting has been working
towards providing
routing
functionality on a PostGis/PostgreSql Geo
spatial

database. It already has support for
shortest path
algorithm
like
astar ,dijkstra , tdsp and trsp .But for a
very

large network, routing becomes time
consuming. Network
partitioning
is one such way which can prove to

be helpful in improving the overall
time efficiency
of routing
querries. The main idea here is to first
partition

the whole network using a Quad tree
approach and
when the
shortest
path is computed these partitions are

loaded on demand. hence , there is an
on demand
incremental
graph
generation.

The project aims at designing and
implementing a
Shortest Path
algorithm on an on demand incremental

Graph using a network partitioning
approach.

2. Background

Considering the present status
where pgRouting has
support for
shortest path algorithm like astar etc.

Looking at their implementation details
we can
observe that
the graph
is configured dynamically for all

of them before computation.My proposal
will also be
on the
same track
and for very large networks

where the distance between source and
destination
can be
very large ,
the response time will be

significantly lesser and memory wise
too it will be
lot more
efficient. Presently they don’t use any
partitioning

approach so it will prove to be a good
addition to their
support for
shortest past algorithms.

3. The idea

There are two major components of my
idea .

Network Partitioning

For this part we can use a quad
tree approach.
Say , we
start
with a square and a condition like maximum

number of nodes that can reside
in a square .
if the
number of
nodes in the square is greater than the max

condition we further quarter it
into four
squares and
allot the
nodes appropriately to each of them.All these

squares can be called grids and
they all will
be addressed
uniquely using a grid cell number .Each node

will be assigned a grid cell
number based on
the grid
they are
lying inside.

We will have data
structures to address
edges as
they can
remain contained in either one grid cell

or span across a number of grid
cells.the
idea is to
first flag
such edges and store the grid cell numbers

of the grids that the edge
crosses/intersects.

On demand graph generation and Routing.

The idea here is to first
identify the
grid cell
initially and then fetch the edges that
are associated with

that grid. These are the edges
that will get
appended
to the
present graph and the graph will keep growing

dynamically this way. we will
have appropriate
database
tables
addressing the above issue such that

we are able to fetch the required
edges
quickly using a
database querry.

The implementation details for
the above are :

we will first partition the whole
graph using
the quad tree
approach and each node/vertex will be assigned

a grid cell number so we can have
database
table for the
assigned nodes and edges like :

CREATE TABLE vertex{

id Node_id
\
unique
for each
node.

cell grid_cell_number;
\ the
grid in
which the
node lies.

geometry;

}

CREATE TABLE edge {

int id ;

Int node_a;

int node_b; \ the
connecting nodes

// we can have other parameters like
traversal cost
and return
cost.

}

using the tables we can then
fetch the
edges form
edge table
using simple database querry once

we are provided with the grid cell
number very easily.

In short the summary of the whole idea is :

Step1: Fetch the start node , get the
related Grid cell
number.

Step 2: Increment the graph by fetching
all the items
related to
that grid.

Step3 : Check for boundary nodes ( this
is done while
we are
partitioning) or target node .

Step 4: On hitting a boundary node

{

check if the connected
grid is
loaded and
continue if
it is

or we extend the graph
with the new
grid and
continue
with the routing;

}

or On hitting the target Node

{

stop;

}

4. Project plan

I will have about 12 weeks to
implement the
project. The
tentative
schedule is as follows:

Before 17th June : Get familiar
with the development
environment
of pgRouting and test some demos.

week 1-2: Discuss and Define the
various data
structures
and data
table that will be required.Prepare the

Overall implementation
architecture.

week 3-4- Discuss and Implement
network
partitioning
using quad
tree.

week 5-8 -Start coding for on
demand graph
generation and
routing
using Dijkstra. In between Prepare mid-term

report.

week 9 - Integration with pgrouting .

week 10-12- Testing and Bug fixing.
Draft Final
report and
documentation.

  1. Future ideas / How can your idea be
    expanded? *

It can be integrated with other
shortest path
algorithms
like
astar etc. which pgrouitng provides.For
time dependent

shortest path computation, it will
greatly reduce the
updating cost
as we will be updating the cost of only
those edges

that are contained in the grid cells
that are loaded.

In route nearest neigbour querries
can also be
implemented using
the partitioning approach.Overall we can

expand this approach to various
other algorithms.

Explain how your SoC task would benefit
the OSGeo member
project and
more generally the OSGeo Foundation as a
whole:

The proposed idea will significantly
improve the
performance of
shortest path finding algorithms.This will
have a

positive effect on the user base of
pgRouting. For
various
software
paltforms or applications that are using
this library ,

the response time will significantly
improve.

Please provide details of general
computing experience:
*

I generally use ubuntu ( 12.04) for all my
academic
purposes and
windows
7 for entertainment only. I am familiar
with Fedora also.

C++ is the language that i use most (
programming
purposes). For
implementing various course projects i
have used C++
,python
,Java and
matlab.

I have no experience with hardware. The
only experience
that i
had with
networking was during my computer network
course.

Please provide details of previous GIS
experience:*

I am a part of “Lab for Spatial
Informatics” which is
the only
lab in
India devoted to GIS applications and
learning. I am
familiar
with and
have used almost all the open source GIS
platforms like
Quantum ,
OpenJump, ILwis,Grass. We have our own
rendering
platform that was
developed by our lab.(LSI viewer)

Please provide details of any previous
involvement
with GIS
programming
and other software programming:

I am very much familiar with Gdal/OGR as
i used it
extensively
while
implementing an outsourced project of
Honeywell

Technology . I have played a lot with ESRI
shape files.

Please tell us why you are interested in
GIS and open
source
software:

I was very impressed with google earth
when it was
launched way
back in
2004.GIS platforms like quantum and
Openjump were
introduced to
me when
i was in my second year and then i joined
Lab for spatial
informatics
that is in our college based on my
interest in this area.

open source platforms provide an
opportunity to learn .
The best
part is
you can always create or develop something
that you are
interested in
and there are people who will always be
there to help
you if you
are stuck.

Please tell us why you are interested in
working for
OSGeo and the
software project you have selected:*

It will be huge learning experience since
i have been
using
platforms
like Qgis , Gdal ,PostGis etc which come
under Osgeo

I chose pgrouting because the algorithms
that they have
implemented are
related to my masters topic and it will be
great if i
get an insight
about how these were implemented on a much
larger scale.

Please tell us why you are interested in
your specific
coding
project:

Implementing routing algorithms for real
world networks is
actually very
challenging.its a challenge to come up
with good
approaches so
that the
computation cost and response time is both
reduced.

Would your application contribute to your
ongoing
studies/degree? If
so, how?

I am pursuing my Masters and my topic is
closely
related to my
proposal
. If the results are impressive , i might
get a
publication in
this area.

Please explain how you intend to continue
being an
active member of
your project and/or OSGeo AFTER the summer
is over:

I was always interested in open source
programming but
never
knew where
to start . GSOC provides an opportunity
for beginners
like me
to take a
dive in the area open source programming.
i have other
ideas like
implementing IRNN ( In route nearest neighbour
querries) which
can be
implemented within pgRouting.I have other
intentions like
working for
bigger projects like Quantum Gis or
Grass.I will be
contributing
to the
community forum and will always try to
improve things.

Do you understand this is a serious
commitment,
equivalent to a
full-time paid summer internship or summer
job?

Yes, I understand that this is a serious
commitment and
will try
to give
my best and work in a professional manner.

Do you have any known time conflicts
during the
official coding
period?
(June 17 to Sept. 27)

No .

On Thu, Apr 25, 2013 at 12:47 AM, Stephen
Woodbridge
<woodbri@swoodbridge.com
mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)
<mailto:woodbri@swoodbridge.__com
mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)>
<mailto:woodbri@swoodbridge.
mailto:[woodbri@swoodbridge](mailto:woodbri@swoodbridge).____com
<mailto:woodbri@swoodbridge.__com
mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)>>

<mailto:woodbri@swoodbridge
mailto:[woodbri@swoodbridge](mailto:woodbri@swoodbridge).
<mailto:woodbri@swoodbridge
mailto:[woodbri@swoodbridge](mailto:woodbri@swoodbridge).>______com

<mailto:woodbri@swoodbridge.
mailto:[woodbri@swoodbridge](mailto:woodbri@swoodbridge).____com
<mailto:woodbri@swoodbridge.__com
mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)>>>> wrote:

On 4/24/2013 2:34 PM, Mukul priya wrote:

Hi Steve and Daniel ,

I have posted my proposal on
Melange Gsoc
system. Do
have a look
at it.
Waiting for feedback and suggestions.

Can you post a link to your proposal?
or the text
of it
here also. I
can never find anything in Melange or
I may not have
visibility to
it yet as I just applied as a mentor.

Thanks,
-Steve

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
<mailto:pgrouting-dev@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)>
<mailto:pgrouting-dev@lists.
mailto:[pgrouting-dev@lists](mailto:pgrouting-dev@lists).____osgeo.org <http://osgeo.org>
<mailto:pgrouting-dev@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)>>

<mailto:pgrouting-dev@lists
mailto:[pgrouting-dev@lists](mailto:pgrouting-dev@lists).
<mailto:pgrouting-dev@lists
mailto:[pgrouting-dev@lists](mailto:pgrouting-dev@lists).>______osgeo.org
<http://osgeo.org> <http://osgeo.org>

<mailto:pgrouting-dev@lists.
mailto:[pgrouting-dev@lists](mailto:pgrouting-dev@lists).____osgeo.org <http://osgeo.org>
<mailto:pgrouting-dev@lists.__osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)>>>

http://lists.osgeo.org/________mailman/listinfo/pgrouting-dev <http://lists.osgeo.org/______mailman/listinfo/pgrouting-dev>

<http://lists.osgeo.org/______mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev>__>

<http://lists.osgeo.org/______mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev>

<http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev

<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>>>

<http://lists.osgeo.org/______mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev>

<http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>__>

<http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>

<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>>>__>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
<mailto:pgrouting-dev@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)>
<mailto:pgrouting-dev@lists.
mailto:[pgrouting-dev@lists](mailto:pgrouting-dev@lists).____osgeo.org <http://osgeo.org>
<mailto:pgrouting-dev@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)>>
http://lists.osgeo.org/______mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev>

<http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>__>

<http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>

<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>>>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
<mailto:pgrouting-dev@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)>
<mailto:pgrouting-dev@lists.
mailto:[pgrouting-dev@lists](mailto:pgrouting-dev@lists).____osgeo.org <http://osgeo.org>
<mailto:pgrouting-dev@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)>>
http://lists.osgeo.org/______mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev>

<http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>__>

<http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>

<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>>>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
<mailto:pgrouting-dev@lists.__osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)>
http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>

<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>__>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
<mailto:pgrouting-dev@lists.__osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)>
http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>

<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>__>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org mailto:[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev