[SoC] Final Report - Implement MST and Mincut

Aditya Pratap Singh adityapratap.singh28 at gmail.com
Mon Aug 13 06:05:35 PDT 2018

Hello everyone,
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
Graph Library


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.

*Implemented function:*

   - pgr_prim()

                  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.

   - pgr_kruskal()

                  Returns the minimum spanning tree of graph using Kruskal
algorithm on undirected graph.

   -  pgr_stoerWagner()

                  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.

*Pending Work:*

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

*Future Directions:*

   - 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:




Best regard,
Aditya Pratap Singh
IIT BBS, India
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/soc/attachments/20180813/9c560703/attachment.html>

More information about the SoC mailing list