[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: *

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. The concept of transitive closure can be thought of as constructing a data structure that makes it possible to answer reachability questions. 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:* 
pgRouting/GSoC-pgRouting#26
pgRouting/GSoC-pgRouting#30
https://github.com/pgRouting/pgrouting/pull/1238
   - *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


Best Regards, Hang Wu
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/soc/attachments/20190826/1c48f5be/attachment.html>