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

Hi All,

This is my final report for my project.


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

wiki: https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Connected-Components


Best Regards,

Maoguang Wang