<div dir="ltr">Hello everyone,<br><div>I'm Aditya Pratap Singh and this is my final report.<br>I am very happy to work with you all and learned a lot from my mentors.</div><div><br></div><div><b><font size="4">Title:</font></b><br></div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div>Implement Minimum Spanning Tree and Min-Cut for pgRouting by the Boost Graph Library</div><div><br></div></blockquote><div><b><font size="4">Abstract:</font></b></div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div>A Minimum Spanning Tree in an undirected connected weighted graph is a spanning tree of minimum weight. For this I had implemented two functions that are Prim Algorithm and Kruskal Algorithm.</div></blockquote><div><br></div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div>Finding the minimum cut of an edge weighted graph is a fundamental algorithmic problem. Stoer–Wagner algorithm is a recursive algorithm to solve the minimum cut problem in undirected weighted graphs with non-negative weights. I had implemented Min-Cut by Stoer Wagner function.</div></blockquote><div><br><b><font size="4">Implemented function:</font></b></div><div><ul><li>pgr_prim()</li></ul></div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div>                  Returns the minimum spanning tree of graph using Prim algorithm. Ideally graph should be undirected and connected but I made signature which can work on unconnected graph also.</div></blockquote><div><ul><li>pgr_kruskal()</li></ul></div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div>                  Returns the minimum spanning tree of graph using Kruskal algorithm on undirected graph.</div></blockquote><div><ul><li> pgr_stoerWagner()</li></ul></div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div>                  Returns the weight of the min-cut of graph using Stoer Wagner algorithm. Function determines a min-cut and the min-cut weight of a connected, undirected graph.</div></blockquote><div><br><b><font size="4">The state before my GSoC</font></b></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div>pgRouting didn’t have the functionality of minimum spanning tree and min-cut. So, I implemented these function in my GSoC period.</div></blockquote><div><br><b><font size="4">The addition that my project brought to pgRouting</font></b></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div>The deliverable are code, full documentation, documentation tests and pgTAP of those three functions.</div></blockquote><div><br><b><font size="4">Pending Work:</font></b></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div>After implementing these function I went for implementation of Random Spanning Tree. It’s C++ code is working but it is not working in pgRouting architecture.</div></blockquote><div><br><b><font size="4">Future Directions:</font></b></div><div><ul><li>Implement full functionality of random spanning tree in pgRouting architecture and its documentation and test and pgTAP.</li><li>Implement algorithm for Common Spanning Trees of Two Graphs using boost graph library.</li></ul><b><font size="4">Links:</font></b></div><div><br><span style="font-size:small;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">Wiki: </span><br style="font-size:small;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial"><a href="https://github.com/pgRouting/pgrouting/wiki/GSoC-2018-MST-and-Mincut" style="color:rgb(17,85,204);font-size:small;background-color:rgb(255,255,255)" target="_blank">https://github.com/pgRouting/pgrouting/wiki/GSoC-2018-MST-and-Mincut</a><br style="font-size:small;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial"><br><span style="font-size:small;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">Pull request with all the commits:</span><br style="font-size:small;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial"><a href="https://github.com/pgRouting/pgrouting/pull/1079" style="color:rgb(17,85,204);font-size:small;background-color:rgb(255,255,255)" target="_blank">https://github.com/pgRouting/pgrouting/pull/1079</a><br style="font-size:small;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial"><br>Slide:<br><a href="https://docs.google.com/presentation/d/1g46CsdTEdZLpsAKNOWfI7R6A2QX6_3ycjFf1fUzMri0/edit#slide=id.g35f391192_00" target="_blank">https://docs.google.com/presentation/d/1g46CsdTEdZLpsAKNOWfI7R6A2QX6_3ycjFf1fUzMri0/edit#slide=id.g35f391192_00</a><br><br></div><div>Tag:<br><a href="https://github.com/pgRouting/pgrouting/releases/tag/gsoc2018-apslight-lw" target="_blank">https://github.com/pgRouting/pgrouting/releases/tag/gsoc2018-apslight-lw</a><br><br>Repository:<br><a href="https://github.com/apslight/Sample-Code" target="_blank">https://github.com/apslight/Sample-Code</a><br><br>Best regard,<br>Aditya Pratap Singh<br>IIT BBS, India</div></div>