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

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

[pgrouting-dev] 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

_______________________________________________
pgrouting-dev mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/pgrouting-dev