[SoC] Final Report - Implement MST and Mincut
Aditya Pratap Singh
adityapratap.singh28 at gmail.com
Mon Aug 13 06:05:35 PDT 2018
I'm Aditya Pratap Singh and this is my final report.
I am very happy to work with you all and learned a lot from my mentors.
Implement Minimum Spanning Tree and Min-Cut for pgRouting by the Boost
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.
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.
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.
Returns the minimum spanning tree of graph using Kruskal
algorithm on undirected graph.
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.
*The state before my GSoC*
pgRouting didn’t have the functionality of minimum spanning tree and
min-cut. So, I implemented these function in my GSoC period.
*The addition that my project brought to pgRouting*
The deliverable are code, full documentation, documentation tests and pgTAP
of those three functions.
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
- Implement full functionality of random spanning tree in pgRouting
architecture and its documentation and test and pgTAP.
- Implement algorithm for Common Spanning Trees of Two Graphs using
boost graph library.
Pull request with all the commits:
Aditya Pratap Singh
IIT BBS, India
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the SoC