<div style="line-height:1.7;color:#000000;font-size:14px;font-family:Arial"><div style="line-height:1.7;color:#000000;font-size:14px;font-family:Arial"><div style="line-height:1.7;color:#000000;font-size:14px;font-family:Arial"><pre>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.</pre><pre><br></pre><pre>I have added Topological Sort algorithm and Transitive Closure algorithms to</pre><pre>pgRouting during this GSoC period.
.
*Implemented functions:*
-
<pre>* pgr_topologicalSort*
</pre><div><pre>* pgr_transitiveClosure*</pre></div><div><br></div>
*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.</pre><pre> - Design the third function, pgr_lengauer_tarjan_dominator_tree().
*Links:*
- *Wiki: *
<a href="https://github.com/pgRouting/pgrouting/wiki/GSoC-2019-GRAPH-C---Boost-graph-algorithms-for-pgRouting#week-12-august-12th---august-18th-1">https://github.com/pgRouting/pgrouting/wiki/GSoC-2019-GRAPH-C---Boost-graph-algorithms-for-pgRouting</a>
- *Last Pull Request:* </pre><pre><a class="pr is-existent closed" data-issue-repo="pgRouting/GSoC-pgRouting" data-provider="github" href="https://github.com/pgRouting/GSoC-pgRouting/pull/26" data-issue="26" data-link-type="pr" target="_blank" style="text-decoration-line: none; color: rgb(231, 76, 60); outline: 0px; border-bottom: 1px dotted; cursor: pointer; padding: 0px 2px; border-radius: 2px; background-color: rgb(251, 222, 219); font-family: SourceSansLocal, source-sans-pro, "Source Sans Pro", -apple-system, Roboto, "pt sans", calibri, sans-serif; font-size: 16px; white-space: normal;">pgRouting/GSoC-pgRouting#26</a><br style="font-family: SourceSansLocal, source-sans-pro, "Source Sans Pro", -apple-system, Roboto, "pt sans", calibri, sans-serif; font-size: 16px; white-space: normal; background-color: rgba(240, 240, 240, 0.3);"><a class="pr is-existent closed" data-issue-repo="pgRouting/GSoC-pgRouting" data-provider="github" href="https://github.com/pgRouting/GSoC-pgRouting/pull/30" data-issue="30" data-link-type="pr" target="_blank" style="text-decoration-line: none; color: rgb(231, 76, 60); border-bottom: 1px dotted; cursor: pointer; padding: 0px 2px; border-radius: 2px; background-color: rgb(251, 222, 219); font-family: SourceSansLocal, source-sans-pro, "Source Sans Pro", -apple-system, Roboto, "pt sans", calibri, sans-serif; font-size: 16px; white-space: normal;">pgRouting/GSoC-pgRouting#30</a></pre><pre><a href="https://github.com/pgRouting/pgrouting/pull/1238">https://github.com/pgRouting/pgrouting/pull/1238</a></pre><pre> - *Slide: *
<a href="https://docs.google.com/presentation/d/1WsnhuOhcsl_SADo3AO8VFO3hIAXuLxIHhrGsAMDfOKY/edit?usp=sharing">https://docs.google.com/presentation/d/e/2PACX-1vSz6R0yP5qCcVA8hdV6eE_okREzebolAJ95Oq5AvRFmn_I9SMd_kFVvz3HpuQP6_nL28c3PfL5XQyeO/pub?start=false&loop=false&delayms=3000</a>
<pre> - *Tag:* <a href="https://github.com/pgRouting/pgrouting/tree/gsoc2018-XJTUmg-lw">https://github.com/pgRouting/GSoC-pgRouting/releases/tag/GSoC-nike0good-2019</a>
</pre><div><pre> - *Video:* <a href="https://github.com/pgRouting/pgrouting/tree/gsoc2018-XJTUmg-lw">https://www.youtube.com/watch?v=NnlXh0gB3yg</a>
</pre></div><div><br></div>
Best Regards,
Hang Wu</pre></div></div></div><br><br><span title="neteasefooter"><p> </p></span>