[pgrouting-dev] Final Report - Implement MST and Mincut

[Aditya Pratap Singh]

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.

*Title:*

Implement Minimum Spanning Tree and Min-Cut for pgRouting by the Boost
Graph Library

*Abstract:*

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
architecture.


*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.

*Links:*

Wiki:
https://github.com/pgRouting/pgrouting/wiki/GSoC-2018-MST-and-Mincut

Pull request with all the commits:
https://github.com/pgRouting/pgrouting/pull/1079

Slide:
https://docs.google.com/presentation/d/1g46CsdTEdZLpsAKNOWfI7R6A2QX6_3ycjFf1fUzMri0/edit#slide=id.g35f391192_00

Tag:
https://github.com/pgRouting/pgrouting/releases/tag/gsoc2018-apslight-lw

Repository:
https://github.com/apslight/Sample-Code

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