[SoC] GSoC 2017 - Week 12 Report - Implement Connected Components Algorithms for pgRouting by the Boost Graph Library
Maoguang Wang
xjtumg1007 at gmail.com
Sun Aug 20 00:52:59 PDT 2017
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>
More information about the SoC
mailing list