[SoC] GSoC 2019 - Final Report - GRAPH C Boost graph algorithms for pgRouting

[Hang Wu]

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:*
   - *Wiki:*
   https://github.com/pgRouting/pgrouting/wiki/GSoC-2019-GRAPH-C---Boost-graph-algorithms-for-pgRouting
   - *Last Pull Request:* https://github.com/pgRouting/pgrouting/pull/1238
   - *Code Documentation:*
      - Topological Sort (pgr_topologicalSort) - http://docs.pgrouting.org/dev/en/pgr_topologicalSort.html
      - Transitive Closure (pgr_transitiveClosure) - http://docs.pgrouting.org/dev/en/pgr_transitiveClosure.html
   - *Slide:* https://docs.google.com/presentation/d/e/2PACX-1vSz6R0yP5qCcVA8hdV6eE_okREzebolAJ95Oq5AvRFmn_I9SMd_kFVvz3HpuQP6_nL28c3PfL5XQyeO/pub?start=false&loop=false&delayms=3000
   - *Tag:* https://github.com/pgRouting/GSoC-pgRouting/releases/tag/GSoC-nike0good-2019
   - *Video:* https://www.youtube.com/watch?v=NnlXh0gB3yg
   - *Image:* https://drive.google.com/file/d/1OecaowmgdcRP97zH9eQwt3zkO4Ov_Shw/view

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/soc/attachments/20190826/17206626/attachment.html>