[SoC] GSoC 2017 - Week 12 Report - Implement Connected Components Algorithms for pgRouting by the Boost Graph Library

[Maoguang Wang]

Hi All,

This is my final report for my project.


*Abstract*
I implemented 5 functions:

   - pgr_connectedComponents - Return the connected components of an
   undirected graph.
   - pgr_strongComponents - Return the strongly connected components of a
   directed graph.
   - pgr_biconnectedComponents - Return the biconnected components of an
   undirected graph.
   - pgr_articulationPoints - Return the articulation points of an
   undirected graph.
   - pgr_bridges - Return the bridges of an undirected graph.



*The state of the project before my GSoC*
pgRouting didn't have those functionalities before my GSoC.


*The addition that my project brought to pgRouting*
The deliverables are code, full documentation, documentation tests of those
five funtions.


*Future directions*

   - Optimize pgr_bridges. pgr_bridges uses a algorithm with O(E * (V + E))
   complexity. Tarjan's algorithm can solve it in O(V + E).
   - Create unit tests(pgTAP) for those five funtions.
   - Implement incremental connected components (include disjoint-set) for
   pgRouting by BGL.



*Links to the code and documentation*
*src *files:
https://github.com/pgRouting/pgrouting/tree/develop/src/components/src
*include *files:
https://github.com/pgRouting/pgrouting/tree/develop/include/components
documentation:
https://github.com/pgRouting/pgrouting/tree/develop/doc/components

*Slides*
https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Connected-Components#slides

Best Regards,
Maoguang Wang
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/soc/attachments/20170820/d0fc28b1/attachment.html>