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