Skip to content

GSoC 2019 GRAPH C Boost graph algorithms for pgRouting

Jump to bottom Edit New page
Hang Wu edited this page Aug 27, 2019 · 37 revisions

Table of Contents

Proposal

Brief Description

My project will focus on implementing:

  • topological sort. Topological sort is a sorting algorithm. It is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.[1]
  • transitive closure. The concept of transitive closure can be thought of as constructing a data structure that makes it possible to answer reachability questions. That is, can one get from node a to node d in one or more hops? A binary relation tells you only that node a is connected to node b, and that node b is connected to node c, etc.[2] lengauer tarjan dominator tree
  • dominator tree. A dominator tree is a tree where each node's children are those nodes it immediately dominates. Because the immediate dominator is unique, it is a tree. The start node is the root of the tree.[3]

I propose to add the above 3 algorithms into pgRouting during the GSoC period.

State of the Project Before GSoC

pgRouting currently does not have these algorithms implemented.

Topological sort is a common sorting algorithm of graph. However, a single standard function does not exist.

Floyd’s algorithm implemented in pgRouting can also answer reachability question. However, it has a higher run-time complexity. Transitive closure is required

Also lengauer tarjan dominator tree is not implemented before in pgRouting. So far, a single standard function does not exist.

Deliverables

  1. Implementation of topological sort to pgRouting.
  2. Implementation of transitive closure for pgRouting.
  3. Implementation of lengauer tarjan dominator tree for pgRouting.

Each implemented function will include relevant documentation and tests.

Timeline

First Evaluation Period (May 27th - June 23rd)

Week 1 (May 27th - June 2nd)

  • Design pgr_topological_sort() function

Week 2 (June 2nd - June 9th)

  • Create a basic skeleton for documentation and tests.

Week 3 (June 10th - June 16th)

  • Implement pgr_topological_sort() function along its helper files.
  • Basic testing.

Week 4 (June 17th - June 23rd)

  • Prepare a report for First Evaluation.

Second Evaluation Period (June 24th - July 21st)

Week 5 (June 24th - June 30th)

  • Work on feedback provided from the first evaluation.
  • Prepare documentation for pgr_topological_sort() function.

Week 6 (July 1st - July 7th)

  • Complete testing along with writing pgTap tests for pgr_topological_sort() function.

Week 7 (July 8th - July 14th)

  • Design pgr_transitive_closure() function.
  • Create a basic skeleton for documentation and tests.

Week 8 (July 15th - July 21st)

  • Begin implementation of pgr_transitive_closure() function.
  • Create a basic skeleton for documentation and tests.
  • Design pgr_lengauer_tarjan_dominator_tree() function.
  • Prepare a report for Second Evaluation.

Third Evaluation Period (July 22nd - August 18th)

Week 9 (July 22nd - July 28th)

  • Work on feedback provided from the second evaluation.
  • Complete the implementation of pgr_transitive_closure() function.Each implemented function will be delivered with the relevant documentation and tests included.

Week 10 (July 29th - August 4th)

  • Begin implementation of pgr_lengauer_tarjan_dominator_tree() function.

Week 11 (August 5th - August 11th)

  • Complete testing along with writing pgTap tests for pgr_transitive_closure() function and pgr_lengauer_tarjan_dominator_tree() function.

Week 12 (August 12th - August 18th)

  • Review, complete and finalize all documentation and tests.
  • Create a detailed final report.

PDF Version

Original Proposal Submitted to Google

Log of Pull Requests

Pull Request Description Date Status
#7 GSOC-2019 week 1 work 31 May 2019 Merged
#9 GSOC-2019 week 2 work 3 June 2019 Merged
#11 GSOC-2019 week 3 work 11 June 2019 Merged
#13 GSOC-2019 week 4 work 20 June 2019 Merged
#14 GSOC-2019 week 5 work 25 June 2019 Merged
#16 GSOC-2019 week 6 work 7 July 2019 Merged
#19 GSOC-2019 week 7 work 14 July 2019 Merged
#21 GSOC-2019 week 8 work 21 July 2019 Merged
#22 GSOC-2019 week 9 work 22 July 2019 Merged
#24 GSOC-2019 week 10 work 29 July 2019 Merged
#26 GSOC-2019 week 11 work 5 August 2019 Merged
#30 GSOC-2019 week 12 work 9 August 2019 Merged
#1238 GSOC-2019 week 12 work 15 August 2019 Merged

Weekly Reports

Third Evaluation Period (July 22nd - August 18th)

Week 12 (August 12th - August 18th)

  • What did I complete this week?
  • What am I going to achieve for next week?
  • Prepare a detailed final report.
  • Is there any blocking issue?
    • No.

Week 11 (August 5th - August 11th)

  • What did I complete this week?
    • Merged a pull request with the changes made. (#26
    • Complete the rest part of pgr_transitive_closure() function.
    • Do code quality check and fix errors.
  • What am I going to achieve for next week?
    • Debug.
    • Prepare for integrating everything to main repository.
    • Review, complete and finalize all documentation and tests.
    • Create a detailed final report.
  • Is there any blocking issue?
    • No.

Week 10 (July 29th - August 4th)

  • What did I complete this week?
    • Merged a pull request with the changes made. (#24
    • Learned the changes of the project.
    • Learned how to do code quality check.
    • Kept designing pgr_transitive_closure() function.
  • What am I going to achieve for next week?
    • Do code quality check and fix errors.
    • Complete the rest part of pgr_transitive_closure() function.
    • Write pgr_lengauer_tarjan_dominator_tree() function.
  • Is there any blocking issue?
    • No.

Week 9 (July 22nd - July 28th)

  • What did I complete this week?
    • Merged a pull request with the changes made. (#22
    • Complete the second evaluation.
    • Keep designing pgr_transitive_closure() function.
  • What am I going to achieve for next week?
    • Complete the implementation of pgr_transitive_closure() function.
    • Create a basic skeleton for documentation and tests for pgr_transitive_closure() function.
    • Begin implementation of pgr_lengauer_tarjan_dominator_tree() function.
  • Is there any blocking issue?
    • No.

Second Evaluation Period (June 24th - July 21st)

Week 8 (July 15th - July 21st)

  • What did I complete this week?
    • Merged a pull request with the changes made. (#21
    • Keep designing pgr_transitive_closure() function.
    • Learn how to debug via log.
  • What am I going to achieve for next week?
    • Complete the implementation of pgr_transitive_closure() function.
  • Is there any blocking issue?
    • No.

Week 7 (July 8th - July 14th)

  • What did I complete this week?
    • Merged a pull request with the changes made. (#19
    • Design pgr_transitive_closure() function.
    • Fix bugs of fucntion pgr_topologicalSort().
  • What am I going to achieve for next week?
    • Begin implementation of pgr_transitive_closure() function.
    • Create a basic skeleton for documentation and tests.
    • Design pgr_lengauer_tarjan_dominator_tree() function.
    • Prepare a report for Second Evaluation.
  • Is there any blocking issue?
    • Should I create a new branch for the new function? If yes, which branch should I make the branch from, 'toposort' or 'upstream/develop'?

Week 6 (July 1st - July 7th)

  • What did I complete this week?
    • Merged a pull request with the changes made. (#16
    • Completed document for pgr_topologicalSort.
  • What am I going to achieve for next week?
    • Design pgr_transitive_closure() function.
  • Is there any blocking issue?
    • No.

Week 5 (June 24th - June 30th)

  • What did I complete this week?
    • Modified the test.
    • Fixed bugs of pgr_topologicalSort.
    • Merged a pull request with the changes made. (#14
    • Completed a report for First Evaluation.
    • Finally set up the right configuration.
  • What am I going to achieve for next week?
    • Writing the rest of documents and help files of pgr_topologicalSort.
  • Is there any blocking issue?
    • No.

First Evaluation Period (May 27th - June 23rd)

Week 4 (June 17th - June 23rd)

  • What did I complete this week?
    • Modified the test.
    • Merged a pull request with the changes made. (#13
  • What am I going to achieve for next week?
    • Keep writing document and help files of pgr_topologicalSort.
    • Complete a report for First Evaluation.
  • Is there any blocking issue?
    • Now I confront problems on compiling pgrouting function.
    • So far, I could not compile my function and got a log of errors. I found that many of other existing functions' tests also return failed. I am not sure whether the problem is caused by my configuration or not. Also I could not find the package ' postgresql-server-dev-11' on (macport & brew & fink, OS X). I would try to find other methods to solve it.

Week 3 (June 10th - June 16th)

  • What did I complete this week?
    • Fixed errors in previous week's work.
    • Added the pgtap and test files.
    • Merged a pull request with the changes made. (#11
    • Tested function pgr_topologicalSort.
  • What am I going to achieve for next week?
    • Complete document and help files of pgr_topologicalSort.
    • Prepare a report for First Evaluation.
  • Is there any blocking issue?
    • No.

Week 2 (June 2nd - June 9th)

  • What did I complete this week?
    • Added the pgr_topologicalSort.hpp (C++ File).
    • Fixed minor errors in previous week's work.
    • Read the boost document in order to implement design the function.
    • Added the pgtap and test files.
    • Merged a pull request with the changes made. (#9)
    • Changed the function name to cammel case.
    • Learned to signed commit.
  • What am I going to achieve for next week?
    • Implement pgr_topological_sort() function along its helper files.
  • Is there any blocking issue?
    • So far, algorithm-tester.pl does not work well on my desktop. It keeps return the error that my function(xxx) is not existed even I compiled other functions. I will try to figure out the reason next week.

Week 1 (May 27th - June 2nd)

  • What did I complete this week?
    • Created a development branch named toposort to implement the pgr_topologicalSort function.
    • Added C, C++ and SQL files to define the function signature. These files allow calling the function pgr_topologicalSort() but return an empty result without processing the input data for now.
    • Made a pull request. (#5)
    • Learned to make a pull request signed.
  • What am I going to achieve for next week?
    • Implement the algorithm of the function pgr_topologicalSort. In the function's current state, It accepts the input data but does not process the data and will return an empty output.
    • Create a basic skeleton for documentation and tests for pgr_topologicalSort.
  • Is there any blocking issue?
    • No.

Community Bonding Period (May 6th - May 27th)

  • Set up the development environment.
  • Interact with mentors, introduce myself to the community and actively get involved in the discussion.
  • Set up a wiki page to keep track of weekly progress.
  • Add a wiki link to OSGeo's accepted students wiki page.
  • Introduce myself and my project on OSGeo's SOC mailing list.
  • Get familiar with pgRouting’s development style. Understand expected coding, documentation and testing standards set by pgRouting.
  • Develop a better understanding of PostgreSQL, PostGIS, Pl/pgSQL and how they interact with pgRouting.
  • Learn to create unit tests using pgTap.
  • Implement simple dummy functions to better understand pgRouting.

Pre-Bonding Period (March 25th - April 9th)

References

  1. "Topological sorting From Wikipedia, the free encyclopedia", https://en.wikipedia.org/wiki/Topological_sorting

  2. "transitive closure From Wikipedia, the free encyclopedia", https://en.wikipedia.org/wiki/Transitive_closure

  3. "Dominator_(graph_theory)#Algorithms From Wikipedia, the free encyclopedia.", https://en.wikipedia.org/wiki/Dominator_(graph_theory)#Algorithms

  4. "DAG From th7.com", https://m.baidu.com/tc?from=bd_graph_mm_tc&srd=1&dict=20&src=http%3A%2F%2Fwww.th7.cn%2Fweb%2Fjs%2F201608%2F179332.shtml&sec=1554819720&di=302233a63ff9bbd4

  5. "lengtarj Persudo code & implement figuresa", https://www.cl.cam.ac.uk/~mr10/lengtarj.pdf

  6. "pgr_bdDijkstra Documentation", https://docs.pgrouting.org/dev/en/pgr_bdDijkstra.html

  7. "pgRouting Sample Data", https://docs.pgrouting.org/dev/en/sampledata.html

Final Report

(The below report was sent to the GSoC mailing list of OSGeo which can be found here)

Hi all,

My name is Hang Wu. And this is my final report for my GSoC project. :)

Title: GSoC 2019 GRAPH C Boost graph algorithms for pgRouting

Organization: pgRouting under OSGeo

Abstract: My project will focus on implementing:

  • topological sort. Topological sort is a sorting algorithm. It is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.
  • transitive closure. The concept of transitive closure can be thought of as constructing a data structure that makes it possible to answer reachability questions. That is, can one get from node a to node d in one or more hops? A binary relation tells you only that node a is connected to node b, and that node b is connected to node c, etc. By using C Boost graph algorithms, these problems can be solved with lesser time complexity. I have added Topological Sort algorithm and Transitive Closure algorithms to pgRouting during this GSoC period.

Implemented functions:

  • pgr_topologicalSort
  • pgr_transitiveClosure

State of the art before the project: PgRouting didn't have above functionalities before my GSoC.

Addition that my project brought to pgRouting: The deliverables are code, documentation, documentation tests, pgTap of above functions.

Future Directions:

  • Due to time constraints, the mentors decided that the third planned function was not to be developed. But the two developed functions are going to be included in the next release of pgRouting as experimental functions.
  • Design the third function, pgr_lengauer_tarjan_dominator_tree().

Links:

I am so glad to have such an interesting and exciting adventure with all of you. Thanks for all your support! I will be happy if my codes help you.

Best Regards, Hang Wu

Contact: https://discourse.osgeo.org/c/pgrouting/pgrouting-dev

pgRouting Project

pgRouting Project

Quick Links

Clone this wiki locally