<div dir="ltr"><div><div><div><div><div>Hi All,<br><br></div>This is my final report for my project.<br><br></div><b>Abstract<br></b></div>I implemented 5 functions:<br><ul><li>pgr_connectedComponents - Return the connected components of an undirected graph.</li><li>pgr_strongComponents - Return the strongly connected components of a directed graph.</li><li>pgr_biconnectedComponents - Return the biconnected components of an undirected graph.</li><li>pgr_articulationPoints - Return the articulation points of an undirected graph.</li><li>pgr_bridges - Return the bridges of an undirected graph.</li></ul></div><b><br>The state of the project before my GSoC<br></b></div><div>pgRouting didn't have those functionalities before my GSoC.<br><br></div><div><b>The addition that my project brought to pgRouting<br></b></div><div>The deliverables are code, full documentation, documentation tests of those five funtions.<br><br></div><div><b>Future directions<br></b><ul><li>Optimize pgr_bridges. pgr_bridges uses a algorithm with O(E * (V + E)) complexity. Tarjan's algorithm can solve it in O(V + E).</li><li>Create unit tests(pgTAP) for those five funtions.</li><li>Implement incremental connected components (include disjoint-set) for pgRouting by BGL.</li></ul></div><div><br></div><div><b>Links to the code and documentation<br></b></div><div><b>src </b>files: <a href="https://github.com/pgRouting/pgrouting/tree/develop/src/components/src">https://github.com/pgRouting/pgrouting/tree/develop/src/components/src</a><br></div><div><b>include </b>files: <a href="https://github.com/pgRouting/pgrouting/tree/develop/include/components">https://github.com/pgRouting/pgrouting/tree/develop/include/components</a><br></div><div>documentation: <a href="https://github.com/pgRouting/pgrouting/tree/develop/doc/components">https://github.com/pgRouting/pgrouting/tree/develop/doc/components</a><br><br></div><div><b>Slides</b><br><a href="https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Connected-Components#slides">https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Connected-Components#slides</a><br><br><div style="font-size:12.8px"><span style="background-color:rgb(255,255,255)"><font color="#000000">Best Regards,<span class="gmail-m_-5595561072000667123gmail-m_6115172932349308060gmail-m_-8531828733370397470gmail-m_-699910917479251445gmail-m_-1163557783907381307gmail-m_5600837438929868284gmail-HOEnZb"><font color="#888888"><span class="gmail-m_-5595561072000667123gmail-m_6115172932349308060gmail-m_-8531828733370397470gmail-m_-699910917479251445gmail-m_-1163557783907381307gmail-m_5600837438929868284gmail-m_1933479316821658827gmail-HOEnZb"><font color="#888888"><span class="gmail-m_-5595561072000667123gmail-m_6115172932349308060gmail-m_-8531828733370397470gmail-m_-699910917479251445gmail-m_-1163557783907381307gmail-m_5600837438929868284gmail-m_1933479316821658827gmail-m_3058582502423155030gmail-HOEnZb"><font color="#888888"><span class="gmail-m_-5595561072000667123gmail-m_6115172932349308060gmail-m_-8531828733370397470gmail-m_-699910917479251445gmail-m_-1163557783907381307gmail-m_5600837438929868284gmail-m_1933479316821658827gmail-m_3058582502423155030gmail-m_-1019527961717166310gmail-HOEnZb"><font color="#888888"><span class="gmail-m_-5595561072000667123gmail-m_6115172932349308060gmail-m_-8531828733370397470gmail-m_-699910917479251445gmail-m_-1163557783907381307gmail-m_5600837438929868284gmail-m_1933479316821658827gmail-m_3058582502423155030gmail-m_-1019527961717166310gmail-m_8447578407322156433gmail-HOEnZb"><font color="#888888"><br></font></span></font></span></font></span></font></span></font></span></font></span></div><span style="background-color:rgb(255,255,255)"><font color="#000000"><span class="gmail-m_-5595561072000667123gmail-m_6115172932349308060gmail-m_-8531828733370397470gmail-m_-699910917479251445gmail-m_-1163557783907381307gmail-m_5600837438929868284gmail-HOEnZb"><font color="#888888"><span class="gmail-m_-5595561072000667123gmail-m_6115172932349308060gmail-m_-8531828733370397470gmail-m_-699910917479251445gmail-m_-1163557783907381307gmail-m_5600837438929868284gmail-m_1933479316821658827gmail-HOEnZb"><font color="#888888"><span class="gmail-m_-5595561072000667123gmail-m_6115172932349308060gmail-m_-8531828733370397470gmail-m_-699910917479251445gmail-m_-1163557783907381307gmail-m_5600837438929868284gmail-m_1933479316821658827gmail-m_3058582502423155030gmail-HOEnZb"><font color="#888888"><span class="gmail-m_-5595561072000667123gmail-m_6115172932349308060gmail-m_-8531828733370397470gmail-m_-699910917479251445gmail-m_-1163557783907381307gmail-m_5600837438929868284gmail-m_1933479316821658827gmail-m_3058582502423155030gmail-m_-1019527961717166310gmail-HOEnZb"><font color="#888888"><span class="gmail-m_-5595561072000667123gmail-m_6115172932349308060gmail-m_-8531828733370397470gmail-m_-699910917479251445gmail-m_-1163557783907381307gmail-m_5600837438929868284gmail-m_1933479316821658827gmail-m_3058582502423155030gmail-m_-1019527961717166310gmail-m_8447578407322156433gmail-HOEnZb"><font color="#888888"><span style="background-color:rgb(0,0,0)"><span></span></span><font color="#000000">Maoguang Wang</font></font></span></font></span></font></span></font></span></font></span></font></span></div></div>