Skip to content

GSoC 2019 GRAPH C Boost graph algorithms for pgRouting

Jump to bottom Edit New page
Hang Wu edited this page Jun 19, 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.

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

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.

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
#11 GSOC-2019 week 4 work 20 June 2019 ---

Weekly Reports

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

Week 12 (August 12th - August 18th)

Week 11 (August 5th - August 11th)

Week 10 (July 29th - August 4th)

Week 9 (July 22nd - July 28th)

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

Week 8 (July 15th - July 21st)

Week 7 (July 8th - July 14th)

Week 6 (July 1st - July 7th)

Week 5 (June 24th - June 30th)

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

Week 4 (June 17th - June 23rd)

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

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

pgRouting Project

pgRouting Project

Quick Links

Clone this wiki locally