GSoC Ideas: 2021 - pgRouting/pgrouting GitHub Wiki

pgRouting's GSoC Ideas for 2021

This page is always work in progress, because we admit new ideas!

Table of Contents

pgRouting's GSoC Mentors:

Our mentors can mentor any project (unless otherwise stated).

name 2021 Availability Mentor Years Other
Stephen Woodbridge 2009~2014 Retired Ex-PSC
Daniel Kastl YES 2009~2020 PSC
Vicky Vergara YES 2015~2020 PSC
Rohith Reddy 2017~2018 GSoC-student 2016 + PSC
Cayetano Benavent YES 2018~2020 PSC
Vidhan Jain 2018 GSoC-student 2017
Sourabh Garg 2019 GSoC-student 2018
Aasheesh Tiwari YES (pgRoutingLayer only) 2020 GSoC-student 2018
Rahul Chauhan YES 2021 GSoC-student 2017, 2018
Ashraf Hossain YES GSoC-student 2009, 2011

Introduction

So you are interested in becoming a Google Summer of Code student, This is great! but what should you do to improve your chances of being selected? We recommend reading

Remember to be proactive

  • Pick a bug or ask for one and work on fixing it so you learn the product and development environment
  • Discuss your ideas on the pgrouting-dev list
  • The best GSoC idea is YOUR idea! something that you are really interested in developing.

We like contributions on the pgRouting's products:

  • osm2pgrouting (C++ & SQL)
  • pgRouting (C & C++ & SQL)
  • pgroutingLayers for Qgis (python 3 & SQL)

Important

  • Number of projects to be accepted is based on mentor availability
  • Review the timeline
  • Regardless of the product, in order for the mentors to consider the proposal, the pgrouting application requirements must be finished and well documented inside the proposal.
    • Help for finishing these tasks will be provided by a mentor starting from February 6 up to March 20 on Saturdays at 15:00 UTC in gitter
    • It is not forbidden that you guide each other
    • It is forbidden copy/paste from each other's proposal.
    • It is forbidden copy/paste from a past year proposal.

Summary of Ideas

To give you an idea about possible pgRouting GSoC ideas that can be worked:

# Title Description
1 Add functionality to pgRoutingLayer plugin Design & implement
2 GRAPH C++ Boost graph algorithms Set up the algorithms to be used with pgRouting
3 VRP functionality with VROOM on the database Set up the VROOM code & use it on a function
4 Test driven code improvement on current VRP functions Prepare the pgtap tests & improve existing code
5 Workshop for Jupyter Notebook Develop an interactive pgRouting workshop using Jupyter Notebook
6 Tour recommendation algorithm Implement an algorithm that recommends routes/tours

Other ideas? We are always interested in other ideas that potential students want to present. So please don't be shy, contact the pgrouting-dev mailing list and introduce yourself and your idea.

Completed in prior years

See a list of projects on pgRouting's Google Summer of Code site.

How to get started

If you're interested, you you should introduce yourself and your project idea on the pgRouting Developer mailing list. Read our wiki pages for developers and debugging and ask for help if you get stuck.

pgRouting application requirements

Task 1: Intent of application

  • Open an issue on GSoC-pgRouting repository Put the following Content inside the Issue:
- [ ] Intent of application 
- [ ] Experience with GitHub & Git
- [ ] Build locally pgRouting
- [ ] Get familiar with C++
- [ ] Get familiar with pgRouting

Task 2: Experience with GitHub & Git

Content of Issue:

- [ ] Fork the [GSoC-pgRouting](https://github.com/pgRouting/GSoC-pgRouting) repository
- [ ] activate issues in your fork
- [ ] open an issue in your fork and put this content on the issue
- [ ] Clone your fork repository in your computer
- [ ] Create remote named `upstream` pointing to https://github.com/pgRouting/GSoC-pgRouting
- [ ] checkout to the `develop` branch of `upstream`
- [ ] create new branch with name `<your-git-nick>-test`
- [ ] Edit `doc/src/pgRouting-introduction.rst` and put your name on contributor
- [ ] push the newly created branch with the change 
- [ ] Create a pull request to https://github.com/pgRouting/GSoC-pgRouting
- [ ] put link of the PR and of the issue on a comment on the issue you created on [GSoC-pgRouting](https://github.com/pgRouting/GSoC-pgRouting) repository

Note: The pull request will not be honored, it is just for testing your skills using git/github

Task 3: Build locally pgRouting

Create a new issue on your fork with the following content

- [ ] Install requirements
  * Look in the documentation what are the requirements
- [ ] Copy/Paste in a comment of this issue the compilation
- [ ] Put the link of this issue on a comment of the issue of task 1

Task 4: Get familiar with C++

Create a new issue on your fork with the following content:

- [ ] https://www.youtube.com/watch?v=eidEEmGLQcU
  - [ ] Make Report
- [ ] https://www.youtube.com/watch?v=u5senBJUkPc
  - [ ] Make Report
- [ ] https://www.youtube.com/watch?v=YnWhqhNdYyk
  - [ ] Make Report
- [ ] https://www.youtube.com/watch?v=1OEu9C51K2A
  - [ ] Make Report
- [ ] https://www.youtube.com/watch?v=xnqTKD8uD64
  - [ ] Make Report
- [ ] https://www.youtube.com/watch?v=86xWVb4XIyE
  - [ ] Make Report
- [ ] Put the link of this issue on a comment of the issue of task 1

View the videos and make a:

  • one page
  • hand written report of each one, Take a picture and add the picture of the report in a comment

Task 5: Get familiar with pgRouting

Create a new issue on your fork with the following content

- [ ] Follow the [workshop](https://workshop.pgrouting.org/2.6/en/index.html) up to chapter 8
- [ ] Use OSGeoLive or your own computer
- [ ] Instead of `city_routing` use `<your-git-nick>-routing`
- [ ] Make a 3 screenshots of your work, make sure that `<your-git-nick>-routing` is visible
- [ ] Put the link of this issue on a comment of the issue of task 1

Adding a section to your proposal

The section must contain the links to the 5 issues and to the pull request

Details of Ideas

Details of idea 1

Add functionality ot the pgRoutingLayer

Currently there are only this supported functions

The latest documentation has many more functions that can be added to the pgRoutingLayer plugin.

Many of the functions work in a similar way. For example the pgr_fooCost work similarly

In your proposal:

  • You will determine at least 3 similar functions that are not yet implemented on pgRoutingLayer.
  • Include reasons of why you think the functions are similar.
  • The details of the idea will be in the form of Proposed User's Documentation.

Notes:

From this list of installed functions ignore the ones that start with _ those are internal functions and are not API to the user of pgRouting.

Consider that at the expected products at the end of GSoC are:

  • Self Documented Code
  • User's Documentation
  • Comments on code when needed

Languages needed for this idea: python3, SQL

Details of idea 2

From Boost Graph 1.56 which in 3.2 will be our official minimum version. On section 22 (Algorithms) There is a list of algorithms from where:

  • Sparse Matrix Ordering Algorithms
  • Graph Metrics
  • and many more sections Have algorithms not yet implemented on pgRouting

For the proposal choose One Algorithm that is not yet implemented on pgRouting The proposal must include:

  • All requirements from GSoC
  • All requirements from OSGeo
  • The details of the algorithm need to have
    • Section: Testing data
    • Section: Proposed Documentation

Consider that at the expected products at the end of GSoC are:

  • Self Documented Code
  • User's Documentation
  • Simple pgtap tests

Section: testing data

The section must have the following statements

  • Link to the Boost example
  • CREATE
  • INSERT
  • SELECT
  • A drawing representing the created graph (can me hand made as Graphs do not have geometries)

That will allow mentors to test data

Section: Proposed Documentation

Try to make it look like a pgRouting function documentation

Notes

Normally the Boost algorithms come with an example, base your proposal on that example's graph Example: From You would need to CREATE TABLE foo ... and INSERT INTO foo ... a PostgreSQL/pgRouting representation of the graph in the example (remember that on C/C++ counting start from 0, but on PostgreSQL counting start from 1)

      Pair edges[14] = { Pair(0,3), //a-d    in PostgreSQL -> (1,4)
                     Pair(0,5),  //a-f
                     Pair(1,2),  //b-c
...
                     Pair(5,7),  //f-h
                     Pair(6,7) }; //g-h

Then test that the query can be executed and give a result with pgr_dijkstra:

SELECT * FROM pgr_dijkstra('SELECT * FROM foo', 1, 7);

.

Details of idea 3

VRP functionality with VROOM on the database

VROOM is a "well known" project for VRP problem The use of the heuristics used by VROOM using data from the database is of great interest.

In your proposal:

  • You will use VROOM terminology and port it into a function design in the vrpRouting extension
  • The details of the idea will be in the form of Proposed User's Documentation.
  • Be clear of the limits of the proposal.
  • To make your pgtap tests use a 5 pick & deliver set of orders from the li & lim benchmark tests. Get the smallest test lc101.txt port the information to a suitable graph. You can use a graph tool of your preference to plot the nodes, their position and join with a line the pickup with the delivery.

Notes:

From this list of installed functions ignore the ones that start with _ those are internal functions and are not API to the user of pgRouting.

Consider that at the expected products at the end of GSoC are:

  • Self Documented Code (SQL, C, C++)
  • User's Documentation
  • Comments on code when needed

Languages needed for this idea: C/C++/SQL

Details of idea 4

Test driven code improvement on current VRP functions

In your proposal:

  • You will use VROOM terminology and port it into a test driven function design in the vrpRouting extension.
  • The focus will be to improve vrp_pgr_pickDeliver function, with a different name & parameters names & types using VROOM terminology
  • The details of the idea will be in the form of Proposed User's Documentation.
  • A first stage is to create the pgtap tests that will drive the SQL code functionality, and the fixes on the existing base code that will make the tests pass
  • Consider
    • date/time types as part of your design.
    • To make your pgtap tests use a 5 pick & deliver set of orders from the li & lim benchmark tests. Get the smallest test lc101.txt port the information to a suitable graph. You can use a graph tool of your preference to plot the nodes, their position and join with a line the pickup with the delivery.

Notes:

From this list of installed functions ignore the ones that start with _ those are internal functions and are not API to the user of pgRouting.

Consider that at the expected products at the end of GSoC are:

  • pgtap tests that will drive the development of the code
  • Self Documented Code (SQL, C, C++)
  • User's Documentation
  • Comments on code when needed

Languages needed for this idea: C/C++/SQL

Details of idea 5

Develop an interactive pgRouting workshop using Jupyter Notebook

Jupyter Notebooks are a popular tool to do interactive computing across dozens of programming languages.

The Jupyter Notebook is an open-source web application that allows you to create and share documents that contain live code, equations, visualizations and narrative text. This makes it an interesting candidate to learn pgRouting as an alternative to the existing workshop.

In your proposal:

  • Give an overview of the workshop content, the data used, the software used, etc.
  • Demonstrate that you have practical experience with Jupyter Notebooks and that you know how to run interactive SQL queries on PostgreSQL/PostGIS/pgRouting.
  • The details of the idea will be in the form of Proposed User's Documentation.
  • Be clear of the limits of the proposal.

Notes:

From this list of installed functions ignore the ones that start with _ those are internal functions and are not API to the user of pgRouting.

Consider that at the expected products at the end of GSoC are:

  • A Jupyter Notebook with an interactive workshop to learn pgRouting
  • Notebook ready to be published and shared
  • User's documentation

Details of idea 6

Tour recommendation algorithm

Think of a use case, where you want to know get a route/tour recommendation of a certain time/length/etc.., for example to do a sightseeing tour, a jogging/cycling course, a patrol route or something similar. This can be a round tour with same start and end point, or the start point can be different from the end point of the tour.

In your proposal:

  • Provide the design of the tour recommendation algorithm and a plan of the implementation
  • Research about existing implementations, research papers, etc. and document it.
  • The details of the idea will be in the form of Proposed User's Documentation.
  • Be clear of the limits of the proposal.

Notes:

Talk with Vicky and Daniel as Georepublic has implemented such an algorithm for a customer use case, so we can discuss with you about your idea.

Consider that at the expected products at the end of GSoC are:

  • Self Documented Code (SQL, C, C++)
  • User's Documentation
  • Comments on code when needed

Languages needed for this idea: C/C++/SQL